Hill Climbing搜索算法应用于旅行商

Question

假设我们给了7个城市A,B,C,D,E,F,G,我们有一个开始状态ABCDEFGA,有一些成本'x',我不明白这个节点的孩子会是什么.意思是怎么样爬山算法的第二次迭代会继续进行吗？

作为开始状态的节点ABCDEFGA是否有6个孩子？就像在

第二次迭代是ACBDEFGA,ADCBEFGA,AECDBFGA,AFCDEBGA,AGCDEFBA？

第三次迭代:假设在第二次迭代中选择了ADCBEFGA,那么第三次迭代是否会与所有其他城市交换城市"C"等等？

我想知道我对算法的理解是否正确.

Answer 1

Hill Climbing算法非常适合寻找局部最优并通过改变当前状态的一小部分来获得更好(在这种情况下,更短)的路径.

如何实施小改动以找到更好的解决方案取决于您.假设你想简单地切换两个节点,只保留结果,如果它比你当前的解决方案更好.

只需将第二个城镇与其他城镇交换,即可获得以下信息:

# first iteration
start: ABCDEFGA
next: ACBDEFGA, ADCBEFGA, AECDBFGA, AFCDEBGA, AGCDEFBA

# second iteration
start: ADCBEFGA
next: ACDBEFGA, ABCDEFGA, AECBDFGA, AFCBEDGA, AGCBEFDA

您可能希望检查每种可能性的适用性并保持最佳状态.然后重申,直到下一个可能性都不比你当前的状态好.您需要为每次迭代不断使用相同的算法.

您可以在第一次迭代时切换第二个城市,在第二次迭代时切换第三个城市,在第三次迭代时切换第四个等等,但请确保循环并继续这种交换方式,并在到达结束时不要停止.我建议坚持使用一个位置并与其他位置交换但最终无论你如何解决这个问题,你最终都会获得不同的次优答案.