比旅行商算法更聪明

Question

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

给出起点，该算法迭代地选择图形上最接近的未使用点，并对其进行访问，直到其循环回到起点为止。该算法具有蛮力，将每个点作为起点运行，并从所有输出周期中选择最短的汉密尔顿周期。]

我一生无法解决这个问题，我绘制了无数图，经过了求解并解决了这些问题，但仍然无法提出算法无法为其找到最佳解决方案的图。

这完全是理论上的，没有代码。非常感谢任何有关我应如何处理/思考此问题的指导或指示。

我在构造一个小的无向图G时遇到困难，该图的加权边值超过给定算法，这意味着无论... ...>

Answer 1

请考虑以下4-顶点图：

Answer 2

如果将所有3更改为4，将所有2更改为1，最优解是否会更改？可不可能是：A-> B-> C-> D-> C-> B-> A = 6要么A-> B-> D-> C-> A = 10