-1

我有一个 NxN 表，比如说 5 乘以 5，其中给定一个随机位置的点 A 和未知数量的点 B：

+---+---+---+---+---+
| B |   |   |   |   |
+---+---+---+---+---+
|   | A |   |   | B |
+---+---+---+---+---+
|   |   | B |   |   |
+---+---+---+---+---+
|   |   |   | B |   |
+---+---+---+---+---+
| B |   |   | B |   |
+---+---+---+---+---+

从 A 点出发，有没有办法找到通过所有 B 点的最短路径？

在这里提出了同样的问题，我已经对旅行商问题进行了几项研究。但是，在图形和类似表格上的解决方案的方法是不同的，因为我无法确定 2 个插槽之间的长度，并且在这个类似表格的图形上，A 只能向上/向下/向左/向右移动。此外，wiki 并没有详细说明算法的工作原理或如何将其转化为编程而不是数学运算。我被困住了，不知道现在该往哪里走。任何建议都非常感谢。请给我一些解决方案。

编辑：Adrian Wragg 建议我画线作为距离，所以 1 个问题解决了。我不知道如何以确切的步骤解决问题，因为我找到的所有资源（即使是我的语言）都是关于数学符号的理论。太远了我的知识。

蒂姆。

4

3 回答 3

3

您可以通过找到所有对之间的最短距离来解决旅行推销员问题。由于您只能上下左右，因此任意 K 和 L 节点之间的距离将是Math.abs(L.y-K.y) + Math.abs(L.x-K.x)其中 x 和 y 是它们的坐标。

于 2013-08-21T08:38:51.343 回答
2

有没有什么办法

是的，当然。例如，蛮力解决方案保证在适当的时候为您提供最佳解决方案。

如果您正在寻找一种有效的算法（在多项式时间内运行），您可能会感到失望，因为这个问题可以简化为旅行推销员并且属于 NP 类。如果您确实设法在多项式时间内解决了这个问题，我相信会有 1.000.000 美元或类似的现金奖励。

见： http://en.wikipedia.org/wiki/Reduction_(complexity)

http://en.wikipedia.org/wiki/NP_（复杂性）

于 2013-08-21T08:47:15.280 回答
1

您可以尝试具有不同距离函数的 travelsalesman 算法，例如曼哈顿距离。

于 2013-08-21T09:31:49.187 回答