假设我们有 7 个城市 A、B、C、D、E、F、G 并且我们有一个起始状态 ABCDEFGA 和一些成本 'x' ,我不明白这个节点的子节点是什么.意味着爬山算法的第二次迭代将如何进行?
作为起始状态的节点 ABCDEFGA 是否有 6 个子节点?就像
第二次迭代是ACBDEFGA、ADCBEFGA、AECDBFGA、AFCDEBGA、AGCDEFBA?
第三次迭代:假设在第二次迭代中选择了 ADCBEFGA,那么第三次迭代是否会与所有其他城市交换城市“C”等等?
我只想知道我对算法的理解是否正确。
最佳答案
爬山算法非常适合寻找局部最优值,它通过改变当前状态的一小部分来获得更好(在本例中为更短)的路径。
如何实现小的更改以找到更好的解决方案取决于您。假设您想简单地切换两个节点,并且只保留比当前解决方案更好的结果。
只需将第二个城镇与其他城镇交换即可得到以下内容:
# first iteration
start: ABCDEFGA
next: ACBDEFGA, ADCBEFGA, AECDBFGA, AFCDEBGA, AGCDEFBA
# second iteration
start: ADCBEFGA
next: ACDBEFGA, ABCDEFGA, AECBDFGA, AFCBEDGA, AGCBEFDA
您可能想要检查每一种可能性的适用性并保留最好的一种。然后重复,直到接下来的可能性都不比你现在的状态好。您将希望对每次迭代持续使用相同的算法。
您可以在第一次迭代时切换第二个城市,第二次切换第三个城市,第三个切换第四个城市,依此类推。结尾。我会建议坚持使用一个位置并与其他位置交换,但无论您如何解决这个问题,最终您都会得到不同的次优答案。
关于algorithm - 爬山搜索算法应用于旅行商,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/14971181/