0

我有一组节点。从一个节点到连接节点的旅行成本始终为 1，但并非所有节点都直接连接。也就是说，从节点 A 到 C 的旅行可能需要经过节点 B，它的总旅行成本为 2。

然后我有一组有序的对航路点。每个航路点对包含一个起点节点和终点节点，必须按顺序访问。

有序对本身不必以任何特定顺序被访问，也不必紧跟在源节点之后访问目标节点。

一个节点可能会被访问​​两次，如果那是为了优化整个路线。它永远不需要访问三次。

如何订购我的节点以实现最低旅行成本并确保访问包含在一个航点中的所有节点，并遵守上面的有序对规则？

我用这个把头撞在墙上。

4

2 回答 2

0

不是一个完整的答案，只是大声思考，一种贪婪的方法：

  1. 计算图的最短距离矩阵，
  2. 找到最短路线最长的一对航路点。
  3. 将该路线附加到最终结果。
  4. 从尚未处理的航路点集合中删除该路线中出现的任何航路点对。
  5. 对剩余的航路点从 2 开始重复，直到没有航路点为止。

如果您遇到一对以相反顺序出现在路线中的航点，则需要想出一种“有效”的方式来反向遍历路线。

另一个想法：

找到图的最小生成树并从左到右和从右到左遍历它。

于 2013-02-25T18:20:12.503 回答
0

不幸的是，这是一个 NP-Hard 问题，因为它减少了（公制）旅行商问题。

这意味着在一般情况下，它不能在多项式时间内完成。您可以采取几种方法

  • 接受超多项式运行时间
  • 放宽要求，不再是NP Complete
  • 使用近似算法
  • 将您的图限制为可以有效求解的集合（例如有界分支宽度图）

或者您可以使用多种方法的组合。例如，使用可以快速解决常见情况的精确算法，并在病理情况下回退到近似算法。

于 2013-02-25T17:03:56.847 回答