胜过旅行推销员算法

Question

我很难构造一个小的无向图G，它的加权边超过了给定的算法，这意味着无论起始点是什么，算法都不会选择最优解。每个节点都连接到每个其他节点。

给定一个起点，该算法迭代地选择图上最近的未使用点并访问它，直到它循环回起始点为止。该算法以每个点为起点，从所有输出循环中选择最短的哈密顿循环。

在我的一生中，我一直无法解决这个问题，我绘制了无数的图表，并对它们进行了研究和求解，但至今仍未能找到算法无法找到最优解的图表。

这完全是理论性的，没有代码。任何关于我应该如何对待/思考这一点的指导或建议都是非常感谢的。

Answer 1

考虑以下4-顶点图：

​

​

我们有长2的边AB和CD，长度1的BC，长度3的AC和BD，长度无穷的AD (或任意大的)。

如果你从A开始，遵循贪婪的方法，你会到达B(长度2)，然后C(长度1)，D(长度2)，然后被卡在DA (长度无穷大)上。根据图的对称性，从D开始得到相同的结果(D -> C -> B -> A -> D，长度无穷大)。

如果你从B开始，遵循贪婪的方法，然后是C(长度1)，然后是D(长度2)，然后是A(长度无穷大--这是我们已经访问了B和C)，最后是B(长度2)。根据图的对称性，从C开始得到相同的结果(如C -> B -> A -> D -> C，长度无穷大)。

总之，无论贪婪的方法从哪里开始，最终都会得到无限长。同时，路径A -> C -> D -> B -> A的长度为10。

无论起始点如何，蛮力算法不仅不是最优的，而且性能也很差。