问题标签 [hill-climbing]

我有一个奇怪的问题。谁能告诉我在哪里可以找到有关的信息，或者给我一些关于使用使用爬山方法的最短路径算法的介绍？我了解两者的基础知识，但我无法将两者放在一起。Wikipedia 有一个有趣的部分是关于通过爬山解决旅行销售人员的问题，但没有提供更深入的解释来说明如何准确地解决这个问题。

例如，爬山可以应用于旅行商问题。很容易找到访问所有城市的解决方案，但与最佳解决方案相比会很差。该算法从这样一个解决方案开始，并对其进行了一些小改进，例如切换访问两个城市的顺序。最终，获得了更好的路线。

据我了解，您应该选择任何路径，然后遍历它并在此过程中进行优化。例如，返回并从起始节点选择不同的链接并检查是否提供了更短的路径。

对不起-我没有说得很清楚。我了解如何将这个想法应用于旅行推销员。我想在最短距离算法上使用它。

我正在为 Usaco 问题“电栅栏”编写解决方案。在该问题中，您必须在大量线段中找到一个点的最佳位置，因此点-线段距离的总和尽可能小。

我有一个想法，也许可以进行爬山，并且它适用于所有测试用例。给定的分析使用了类似的方法，但没有解释为什么会这样。

因此，我仍然无法证明或反驳给定任务中局部最优的存在。我有一个想法，可以使用归纳法来完成，但我无法让它发挥作用。你能帮助我吗？

更新的定义

给定一组 (x1,y1,x2,y2) 线段，找到 (x,y) 点 P，使函数最小化：

由于某种原因，该问题仅包含一个局部最优值，因此可以使用以下过程来解决它：

问题是：为什么这不会在通往全局最优的道路上卡在某个地方？为什么没有当地的山顶可以让这种幼稚的程序屈服？

我正在尝试使用简单的爬山算法来解决旅行商问题。我想创建一个 Java 程序来做到这一点。我知道它不是最好用的，但我主要希望它看到结果，然后将结果与我还将创建的以下结果进行比较：

• 随机爬山者
• 随机重启爬山者
• 模拟退火。

无论如何回到简单的爬山算法，我已经有了这个：

这就是我所需要的吗？这段代码是否正确..？我希望程序从中读取并生成结果的文本文档中有一系列不同的数据集。

非常感谢您对此的任何帮助。

- - - 编辑 - -

我是个白痴，当我应该先在记事本中打开它时，直接在 Eclipse 中打开了 Java 文件。这是我现在得到的代码。

我一直试图了解随机爬山者一段时间，但没有任何运气。我浏览了一本关于启发式的书并得到了一个伪代码。我不明白概率函数应该是什么样子。我知道新的解决方案是随机抽取的，并基于某种概率被接受，我不知道如何编程这个概率。谢谢

伪代码 - 从如何解决它：现代启发式 - Zbugniew Michalewicz，大卫福格尔

好的，我有一个 BFS 的 Lisp 实现，我正在尝试将其转换为爬山搜索。

这是我的 BFS 代码的样子：

现在，我知道我需要扩展似乎最接近目标状态的节点，而不是像在 BFS 中那样总是扩展左节点。
我使用的图表如下所示：

我有一个转换函数可以使它与上述 BFS 实现一起工作，但现在我需要使用这种图形格式将其转换为爬山。

我只是不确定从哪里开始，并且一直在尝试无济于事。我知道我主要需要更改expand-queue函数以扩展最近的节点，但我似乎无法制作一个函数来确定哪个节点最近。

谢谢您的帮助！

我正在尝试修改现有的爬山函数，该函数采用两个节点名称（例如 A 和 E），并具有递归使用的可选参数（队列）。我正在尝试定义一个“更便宜”的函数来评估一条路径是否比另一条路径便宜。此外，我试图传递一个目标节点列表，而不是一个目标节点，该函数在到达其中一个节点时停止评估。

问题是除了我输入的起始节点和一个空列表之外，我的函数不会返回任何内容。

这是我的网络/图表和相关成本：

这是我修改后的爬山函数：

最后，这里是“成本”和“更便宜”的功能：

编辑：对不起，这里是“扩展”：

I am a little confused with Hill Climbing algorithm. I want to "run" the algorithm until i found the first solution in that tree ( "a" is initial and h and k are final states ) and it says that the numbers near the states are the heuristic values. Here's the tree:

My question : i am trying to run hill climbing on the tree, so ok we start a-> f-> g and then what ??finish(without result) , but I read that hill climbing can't go back and make a new choice(example j or e) ? Is this right ? If i can go back then how ? i mean where we change our initial choice example we choose e instead of g or j instead of f

Sorry if my question is too simple .

我已经使用随机突变爬山算法作为我正在从事的项目的一部分，但想知道使用模拟退火是否会更好，以尽量减少陷入任何局部最优的机会。

我的问题是，根据您的经验，哪一个通常更快？显然，这两种算法都有大量的应用。如果您愿意，这更像是一种广义的思考。

谢谢你。

我创建了一个爬山算法，它随机生成一个解决方案，然后复制该解决方案并对其进行一些变异，看看它是否最终得到一个更好的解决方案。如果是这样，它会保留新的解决方案并丢弃旧的解决方案。

如果我想在该算法中添加模拟退火，我是否可以从更高的突变率开始，并在每次创建新解决方案时稍微降低突变率？

我假设突变率将作为模拟退火算法的温度，对吗？

这段代码应该比较两个适应度，使用最好的一个来找到解决方案，然后在下一次迭代中使用最好的一个。但是我得到的问题是它只是使用最新的健身，无论它是更大还是更小。谁能帮我看看我的代码是否有任何错误，谢谢！

这有点难以解释，所以如果有人需要更多说明，请询问，我会发布我的整个项目，尽管我相信这个错误与这一小段代码有关：

这是SmallChange：

这是 ScalesFitness 和 ScalesSolution：