我有兴趣解决（小）网格图的 TSP。任何类型的图书馆都可以为我做，但这似乎比预期的要难。我尝试了几个在那里发现的求解器（包括协和式），但是当三角不等式不成立时，它们似乎都有问题。
例如，我希望求解器为下面的图（具有单位边权重）输出游览 (0, 1, 2, 1, 4, 3)：
0-1-2
| |
3-4
在这种特殊情况下，我告诉协和边 (2, 4) 的权重为 1000，协和迅速生成成本为 1004 的游览 (0, 1, 2, 4, 3)。这显然不是我想要的。
理想情况下，Java 中会有一些简单的（可能是蛮力的）实现，但任何可行的方法实际上都可以。谁能给我指出一些代码，或者我真的必须自己去实现它吗？
编辑：另外，重要的是我得到一个精确的解决方案，而不是一些近似值。
Edit2：确实，这似乎不是 TSP。我试图找到的是访问所有顶点的最短封闭步行。