给定一个排序数组A e.g. {4,9,10,11,19}。搬家费用i->j is abs(A[j]-A[i])。从给定元素开始，例如10。找出成本最低的路径，而无需两次访问同一元素。所以在这个例子中解决方案是10->9->4->11->19 i.e. 1 + 5 + 7 + 8 = 21.
我尝试使用最近邻方法来解决这个问题。
i = start;
While (array is not empty)
ldiff = A[i] - A[i-1]
rdiff = A[i+1] - A[i]
(ldiff < rdiff) ? sum += ldiff : sum += rdiff
remove A[i]
该解决方案并不适用于所有情况。我已经意识到这是 TSP 问题。解决这个问题的最佳方法是什么？我应该使用 Christofides 等 TSP 启发式算法或其他算法吗？
对于您的情况，最低成本是 21，请参阅
10->9->4->11->19 ==> 1 + 5 + 7 + 8 = 21.
我认为，对于常见情况，如果你从第 i 个位置开始，最小成本是路径，最小
A[i]->A[i-1]-> ...->A[1] -> A[i+1] -> A[i+2] -> ...->A[n] and
A[i]->A[i+1]-> ... ->A[n] ->A[i-1] ->A[i-2] -> ...->A[1]
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
