两个销售员——一个总是访问最近的邻居，另一个则访问最远的邻居。

Question

考虑与图论相关的问题： 假设 G 是一个大小为N x N的完全（每个顶点都连接到所有其他顶点）非定向图。两个“推销员”按照以下方式旅行：第一位总是访问最近的未访问顶点，第二位则访问最远的顶点，直到他们都访问了所有顶点。我们必须生成一个距离矩阵和两个推销员（他们可以不同）的起始点，使得：

• 所有距离都是唯一的 编辑：正整数
• 从一个顶点到自身的距离始终为0。
• 两个推销员所走过的总距离之差必须是一个特定的数字，D。
• 从A到B的距离等于从B到A的距离

哪些高效算法可以帮助我？我只能想到回溯，但我看不到任何减少程序工作量的方法。

- Mystostar

---

起点呢？我会假设旅程的距离取决于起点。 - gnasher729

@gnasher729 我必须找到起始点以及距离矩阵。 - Mystostar

Answer 1

几何学很有用。

使用圆上点之间的距离似乎可行。看起来可以通过增加或减小圆的半径来确定调整D。

或者任何距离都不同的2D形状也可能适用。在这种情况下，应缩放形状以获得正确的D。

• 编辑：现在我想想，最简单的解决方案可能只是选择N个随机2D点，例如32位整数坐标，以降低任何距离过于接近的可能性。如果两个距离太接近，请为其中一个选择另一个点，直到它有效为止。

理想情况下，您只需要找出确定D和缩放因子之间关系的公式，但我不确定。如果没有其他办法，您也可以使用二分搜索或插值搜索之类的方法搜索缩放因子以获得所需的D，但这是一种较慢的方法。

- Nuclearman

---

我看到你的方法存在一个问题，就是我必须使用整数距离。因此，对我来说，使用几何似乎比其他方法更困难，不是吗？ - Mystostar

并不是真的需要添加一些额外的步骤。这里的真正目标是尽可能接近D。运行两个算法并跟踪所遵循的边缘。找到一个使用但另一个没有使用的边缘，并调整它们的长度以更接近D，但不要调整得太多，以至于算法会选择另一条路径。这在大多数情况下应该有效，其他情况可能需要特定的几何形状才能工作。棘手的情况是当你无法再调整它们时，以及当距离变得相等时，这个标准使得寻找高效解决方案变得相当困难。 - Nuclearman