algorithm - 给定一对点的数组，对它们进行排序，使终点与下一个点的起点匹配

Question

给定一对点的数组，例如

[19, 11], [11,44] ,[ 98,101], [44,98], [12,32],[44,12],[44,98],[98,101], [33,39]

排列数组，使终点等于下一点的起点。如果不相等，则成本 = 1。我们必须将成本降至最低。例如我们可以将上面的安排为

[19,11],[11,44],[44,12],[12,32],[44,98],[98,101],[44,98],[98,101], [33,39]

所以这里的成本是 [12,32],[44,98] = 1 + [98,101],[44,98] = 1 + [98,101],[33,39] = 1 所以总数 = 3。

我已经尝试了一些解决方案，首先匹配精确对，然后尝试匹配非精确对，但我觉得我的贪婪方法不是最优的，可以使用动态规划来找到一些最优解。

另外一种感觉就是统计所有可能的序列但是复杂度非常高n!。

谁能帮我想出一个动态规划的解决方案

Answer 1

我相信这实际上是著名的 Travelling Salesman 的一个实例问题。这意味着您的解决方案不是最优的，并且在多项式时间内也没有可能的最优解。虽然动态规划does seem to稍微降低时间复杂度，它仍然是 NP-Hard。

要了解原因，我们需要使用图论重新表述这个问题。在这里，每个点都是一个节点。每个节点(即点)都通过成本为 1 的有向加权边与其他节点相连。除非源节点的结束值与邻居节点的开始匹配，否则边的权重为 0。现在创建一个虚拟起始节点，其具有直接边连接从它到每个节点，也从每个节点到它。

现在，如果您从起始节点运行 TSP，您将以最低的成本获得所需的序列。