智胜旅行推销员算法
Outsmarting a Traveling Salesman Algorithm
我在构建一个小的无向图 G 时遇到了困难，该图具有比给定算法更聪明的加权边，这意味着无论起点是什么，该算法都不会选择最佳解决方案。每个节点都连接到每个其他节点。
给定一个起点，算法会迭代地选择图形上最近的未使用点并访问它，直到它循环回到起点。该算法进行蛮力，运行每个点作为起点，并从所有输出的循环中选择最短的哈密顿循环。
我这辈子都想不通，我画了无数图，遍历并解决了它们，但仍然无法得出一个算法无法找到最优的图
的解决方案
这完全是理论上的，没有代码。非常感谢任何关于我应该如何 approach/think 的指导或指示。
考虑以下 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.
无论起点如何，蛮力算法不仅不是最优的，而且性能非常差。
我在构建一个小的无向图 G 时遇到了困难，该图具有比给定算法更聪明的加权边，这意味着无论起点是什么，该算法都不会选择最佳解决方案。每个节点都连接到每个其他节点。
给定一个起点，算法会迭代地选择图形上最近的未使用点并访问它，直到它循环回到起点。该算法进行蛮力，运行每个点作为起点，并从所有输出的循环中选择最短的哈密顿循环。
我这辈子都想不通，我画了无数图，遍历并解决了它们，但仍然无法得出一个算法无法找到最优的图
的解决方案这完全是理论上的，没有代码。非常感谢任何关于我应该如何 approach/think 的指导或指示。
考虑以下 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.
无论起点如何，蛮力算法不仅不是最优的，而且性能非常差。