algorithm - 有路线限制的图搜索问题

Question

我想计算最赚钱的路线，我认为这是一种旅行商问题。
我有一组我可以访问的节点和一个函数来计算节点之间的旅行成本和到达节点的点。目标是在最小化成本的同时达到固定的已知分数。

这个成本和奖励不是固定的，取决于之前访问过的节点。
起始节点是固定的。

节点的访问方式有一些限制。一些简化的示例包括:

• 节点B只能在A之后访问
• 访问节点C后，可以访问D或E。必须至少访问一个，允许同时访问两个。
• 只有至少访问了 5 个其他节点后才能访问 Z
• 访问50个节点后，节点A-M不再奖励积分
• 某些节点可以(而且可能必须)被多次访问

目前我能想到的解决办法只有两种:
a) 遗传算法，用适应度函数计算生成路线的成本/ yield
b) Dijkstra 搜索图，因为起始节点是固定的，尽管大量的节点可能会使内存不可行。

是否有任何其他方法可以通过图表确定最佳路线？它不需要是完美的，近似的路径是完美的，只要它的误差是可以接受的。
TSP 求解器会是这里的一个选项吗？

Answer 1

有了这么多奇怪的变化和路径依赖，您实际搜索的不是图形本身，而是从根(树)开始的路径空间。如果问题像您所说的那样普遍，那么您将无法比直接搜索“路径树”、保存最佳值和相应路径做得更好。如果您可以将其转换为任何方式，从而不存在这种路径依赖性，那么您应该这样做。

如果不能，有两个基本选项:广度优先，它会按长度顺序返回路径，但是以高内存使用为代价，因为必须存储许多临时路径。深度优先搜索只需要存储一条路径(完全可以作为一系列递归调用来完成)，但没有自然停止点，如果路径大小没有上限，则不能保证实际终止。

如果您足够幸运，成本随着每增加一步单调增加，您可以改为按成本排序。第一个足够好的就是你想要的那个。广度优先搜索有时是通过将要探索的路径放在队列中来实现的。将其更改为基于成本的优先级队列，您现在有一个“成本优先搜索”，正式名称为 Uniform-cost search .

如果通过在路径上添加成本函数可以减少，可以修改 A* 搜索来进行搜索，但您不再保证可以提前停止。