在成本约束下寻找图中从头到尾具有必要和可选路点的最优路径

Question

我正在研究一个涉及加权图中寻路的问题，我需要从起始节点移动到结束节点，同时考虑必要和可选路径点节点的组合。问题的关键在于存在必要的路点（从起始节点到结束节点的任何有效路径上必须访问的节点）和可选的路点。这些可选路径点在有效路径中并不是严格必需的，但我更愿意访问尽可能多的路径点。还有最大成本限制。

我的目标是找到一条满足以下条件的有效路径（如果存在）：

1. 强制约束满足：首先，我需要确定是否存在从起始节点到结束节点的任何路径，该路径访问所有必要的路点并保持在最大成本约束内。
2. 最佳可选包含：如果存在这样的路径，那么我想找到一条最大化访问的可选路径点数量同时仍满足成本约束的路径。

示例图：

• 启动节点：

  A

• 结束节点：

  B

• 必要的航点：

  [W1, W2]

• 可选航点：

  [O1, O2, O3]

• 最高成本：

  C

鉴于此设置，我想：

1. 查找在成本

   A -> ... -> B

   内是否存在访问

   W1

   和

   W2

   的路径

   C

   。
2. 如果存在这样的路径，则从

   [O1, O2, O3]

   中找到可以包含的节点数最大且不超过成本

   C

   的路径。

考虑的方法：

• 我考虑过使用 Dijkstra 的最短路径算法，并找到了一种方法，通过使用包含当前访问的路点的“路点内存”对每个状态进行建模，在给定起始节点、结束节点和必要的路点的情况下找到最短路径。但是，我不确定如何将其扩展到不必要的路径点。
• 我曾考虑过尝试使用回溯进行详尽的搜索，但担心组合爆炸导致的性能。

我的问题：

1. 什么算法或技术最适合此类寻路问题？理想情况下，它应该能够处理大量不必要的航点。

任何有关如何实现或优化这些要求的指导将不胜感激！

Answer 1

你说你已经解决了包含强制航路点的问题。 现在您想要添加可选航点。 因此，将可选航路点从可选列表移动到强制列表并解决。 重复此操作，直到找不到可以在不超出成本限制的情况下添加的可选航路点。