我想解决以下问题：
我有一个 DAG，其中包含需要完成的城市和工作。这些工作适用于可以装载定义限制的卡车。卡车装载的越多，旅行就越好。有些工作是为了加载一些东西，有些是为了加载定义的东西。即使他们之间没有工作要做，您也可以随时从城市 a 开车到 b。最后一个限制是我总是需要从 a 城市开始并返回 a，因为那里有卡车的家 :)
我首先想到的是 Dijkstra 的最短路径算法。我可以轻松地将其转换为最长路径计算。我现在想到的问题是，所有这些算法都用于计算从顶点 a 到 b 的最短或最长路径，但我需要它从 a 返回到 a - 在一个圆圈中。
有没有一些让我心动的？
感谢您的反馈意见！
马可
这种背包和旅行推销员的疯狂组合肯定是NP-hard。
几乎在任何地方，当您想要加载具有最佳作业计划的代理时，或者当您想要构建通过图中所有顶点的路线时，或者当您觉得需要寻找“最长路径*”时，您很可能遇到NP 完全问题或NP难题。
这意味着，对于该问题没有已知的快速和精确的解决方案，即在多项式时间内运行的解决方案。
因此，您必须根据您的特定条件创建近似值并实施非最优算法。什么时间损失是可以接受的？卡车可以驾驶其他模式吗？您对图表了解更多吗（例如，该区域是否被划分为遥远的密集区域）？回答这些问题，您会发现满足您客户的非严格启发式方法。
*是的，寻找最长的路径并不像你想象的那么容易。鉴于您的图不是无环的，最长路径问题是 NP 完全的。
您正在尝试找到完成所有事情的最小方法吗？这让我想起了最大流量/最小切割问题。您可以通过以下方式近似得出最佳答案：
end节点。a流量end。a。更新图表以反映您刚刚所做的事情。重复直到完成所有工作。我们的想法是让您每次旅行都能获得最大的收获。第 1 次之后的每次旅行都会效率低下，效率也会降低，但这是意料之中的。
注意：这仅适用于您有 DAG。旅行推销员在有向无环图上也不会是 NP-Complete 的，甚至可能不可能命中图上的所有节点。重新阅读您的问题，您似乎没有 DAG，因为您可以返回城市a- 是真的吗？
你可以调整旅行商问题动态规划算法来做你想做的事。
经典方法是说您希望最大限度地发挥所有城市的最佳功能，但您可以考虑每一步还有返回家园的可能性。
就像 Pavel 提到的那样，这个问题绝对是 NP-hard。您对卡车可以装载的城市数量或最大物品数量是否有上限？
PS：您想要最好的解决方案（最大利润 - 在处理时间方面可能不现实）还是您接受一些近似值？