两个推销员 - 一个总是访问最近的邻居,另一个是最远的

Question

考虑相对于图论的这个问题:设G完全(每个顶点连接到所有其他顶点)大小为N x N的非有向图.两个"推销员"以这种方式旅行:第一个始终访问最近的非访问顶点,第二个访问最远,直到他们都访问了所有顶点.我们必须生成一个距离矩阵和两个推销员的起点(它们可以是不同的),这样:

• 所有距离都是唯一的编辑:正整数
• 从顶点到自身的距离始终为0.
• 由两个推销员覆盖的总距离之间的差必须是一个具体的数字,d.
• 从A到B的距离等于从B到A的距离

哪些有效的算法对我有用？我只能想到回溯,但我认为没有办法减少程序要完成的工作.

Answer 1

几何学很有帮助。

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

或者，实际上也可以使用距离都不同的任何二维形状。在这种情况下，您应该放大或缩小形状以获得正确的D。

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

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