C# 中的 Held–Karp 算法实现

代码仓库

引言

在本文中，我们将直接进入算法的实现，我假设读者熟悉旅行商问题和动态规划。

背景

我找不到一个可靠的算法实现，所以我决定自己来做，希望它能帮助到一些人；）

工作原理

动态规划的核心有两个部分

1) 一个我们已经知道答案的基本情况（停止条件）
2) 缩小问题域并再次调用我们的算法。（递归）

非常简单地说，并且不涉及太多数学术语，该算法接受两个输入：我们开始的顶点vertex，以及要访问的顶点列表vertices。

现在我们面临两种情况，要么

1. vertices为空，那么太好了！没有工作要做，返回起点到 vertex的距离。
2. vertices 不为空，哼！让我们缩小我们的问题空间：

a) 考虑 vertices 中的每个顶点 newV 作为起点。

b) 因为我们考虑 newV 作为起点，我们必须调整要访问的顶点列表，方法是移除 newV 从 vertices。（我为什么要规划去我已经所在的城市的路线）令其为 newVertices.

c) 计算访问 newV 的成本 + 从 newV 开始访问其余顶点的成本。

（这基本上是再次调用算法，但输入为 newV 和 newVertices ）

d) 返回步骤 c 中的最小结果。

分步演练

假设我们有一个具有以下距离矩阵的双向图

 

	1	2	3	4
1	0	10	15	20
2	5	0	9	10
3	6	13	0	12
4	8	8	9	0

起始顶点是 (1)，我们要访问顶点 {2,3,4}
假设我们的函数名为 g，那么我们想要的是
g(1,{2,3, 4})

这些被分解为计算以下项的最小值：
c12 + g(2,{3, 4})
c13 + g(3,{2,4})
c14 + g(4,{2,3})}
c12 是从 (1) 到 (2) 的成本，c13 是从 (1) 到 (3) 的成本，依此类推……
它们（按顺序）是

g(2, {3,4})= min {

c23 + g(3,{4}),

c24 + g(4,{3})

} = 25

g(3, {4}) = c34 + g(4,{}) = 12 + 8 = 20

g(4, {3}) = c43 + g(3,{}) = 9 + 6 =15

g(3, {2,4})= min {

c32 + g(2,{4}),

c34 + g(4,{2})

} = 25

g(2, {4}) = c24 + g(4, {}) = 10 + 8 = 18

g(4, {2}) = c42 + g(2,{}) = 8 + 5 = 13

g(4, {2,3})= min {

c42 + g(2,{3}),

c43 + g(3,{2})

} = 23

g(3, {2}) = c32 + g(2,{}) = 13 + 5 = 18

g(2, {3}) = c23 + g(3, {}) = 9 + 6 = 15

代入我们的前三个公式得到
min{

10 + 25,

15 + 25,

20 + 23

}=min {35, 40, 43}=35
为了得到实际的路线，我们创建一个树

        private class Node
        {
            public int Value { get; set; }
            public Node[] ChildNodes { get; set; }
            public bool Selected { get; set; }
        } 

树数据结构将模仿我们算法的分支，每次标记成本最低的节点（顶点）为已选。



算法终止后，我们遍历树，只检查被标记为已选的顶点。

代码

private double GetMinimumCostRoute(int startVertex, HashSet set, Node root)
        {
            if (!set.Any())
            {
                //source node is assumed to be the first
                root.ChildNodes = new Node[1] { new Node { Value = _vertices.First(), Selected = true } };
                return _adjacencyMatrix[startVertex, 0];
            }

            double totalCost = double.MaxValue;
            int i = 0;
            int selectedIdx = i;
            root.ChildNodes = new Node[set.Count()];

            foreach (var destination in set)
            {
                root.ChildNodes[i] = new Node { Value = destination };

                double costOfVistingCurrentNode = _adjacencyMatrix[startVertex, destination];

                var newSet = new HashSet(set);
                newSet.Remove(destination);
                double costOfVisitingOtherNodes = GetMinimumCostRoute(destination, newSet, root.ChildNodes[i]);
                double currentCost = costOfVistingCurrentNode + costOfVisitingOtherNodes;

                if (totalCost > currentCost)
                {
                    totalCost = currentCost;
                    selectedIdx = i;
                }

                i++;
            }

            root.ChildNodes[selectedIdx].Selected = true;

            return totalCost;

        }

结论

请注意，运行时间是指数级的，最多有 O(n*2ⁿ) 个子问题，每个子问题需要线性时间来解决。因此，总运行时间为 O(n²*2ⁿ)。

一如既往，我希望我提供了一个清晰的解释和充分的实现；）
如果您有任何反馈/问题，请告知我。