时间戳

首页 > 解决方案 > 包含限制的 TSP 的 Bellman-Held-Karp 算法

algorithm - 包含限制的 TSP 的 Bellman-Held-Karp 算法

问题描述

我正在使用动态编程修改 TSP 的 Bellman-Held-Karp 算法。在这种情况下，经典的 Bellman-Held-Karp 算法的不同之处在于必须先访问某些城市，但我需要保留最小化路径成本。在用编程语言实现它之前，我正在修改伪代码，最终解决并证明解决方案。我正在尝试一个示例，例如[1,2,3,4,5..n]，在完整图表中，从第一个城市（第一个索引）开始排序的城市，例如，第 5 个城市不能出现在第二个城市之前。我使用这个伪代码作为基础：

function algorithm TSP (G, n) is
    for k := 2 to n do
        C({k}, k) := d1,k
    end for

    for s := 2 to n−1 do
        for all S ⊆ {2, . . . , n}, |S| = s do
            for all k ∈ S do
                C(S, k) := minm≠k,m∈S [C(S\{k}, m) + dm,k]
            end for
        end for
    end for

    opt := mink≠1 [C({2, 3, . . . , n}, k) + dk, 1]
    return (opt)
end function

我正在考虑将最大城市索引保存在列表中（在重复中），以确保它永远不会更高，但我不确定这种方法是否正确。

minm≠k,m∈S [C(S\{k}, m) + dm,k] + max(S\{k + i < 4})

是正确的这种方法吗？有人能帮我吗？

标签： algorithmdynamic-programmingtraveling-salesman

解决方案

我不明白你的第二个代码片段，或者你记录“最大城市索引”的意思（对于给定的集合，这不是总是一样的S吗？），但无论如何：根据我的经验，试图记录DP 解决方案旁边的“附加信息”几乎总是会导致细微的错误，通常是因为它假设某种解决方案的唯一性实际上并不存在。例如，可能有两条不同的最佳长度路径访问一组S顶点并结束于m——那么边信息实际上是在谈论哪一条？

一种不同的方法允许任意优先约束。让succ(v)是必须出现在 city之后的一组城市v。改变

C(S, k) := minm≠k,m∈S [C(S\{k}, m) + dm,k]

至

if succ(k) ∩ S\{k} = ∅:
    C(S, k) := minm≠k,m∈S [C(S\{k}, m) + dm,k]
else
    C(S, k) = INF

这个想法只是对任何v出现的后继者的路径进行严厉惩罚v，确保它永远不会被选为最佳解决方案的一部分。

推荐阅读