我想解决以下问题：
我有一个包含城市和他们之间需要做的工作的DAG。这些工作是为卡车可以装载一个明确的限制。卡车装得越多，旅行就越好。有些作业用于加载内容，有些则用于加载已定义的内容即使他们之间没有工作要做，你也可以开车从A市到B市。
最后一个限制是，我总是需要从a市出发，回到a市，因为那里是卡车的家：）
我首先想到了dijkstra的最短路径算法。我可以很容易地把它变成最长路径计算我现在的问题是，所有这些算法都是用来计算从顶点a到b的最短或最长路径的，但我需要从a返回到圆中的a。
有人能让我开心吗？
谢谢你的反馈！
马可
最佳答案
这个背包和travelling salesman的疯狂组合肯定是NP-hard。
实际上，在任何地方，当你想给你的代理加载最优的作业计划，或者当你想建立一条穿过图中所有顶点的路由，或者当你觉得你需要寻找一个“longest path*”时，你很可能会遇到一个NP-complete或NP-hard问题。
也就是说，这个问题没有已知的快速和精确的解决方案，也就是在多项式时间内运行的那个。
因此，你必须创建近似，并根据你的特定条件来实现非最佳算法。什么时间损失是可以接受的？卡车还能开其他的模式吗？你对这个图了解得更多吗（例如，这个区域是否被划分成遥远的密集区域）？回答这些问题，你会发现一个非严格的启发法，满足你的客户。
*是的，寻找最长的路径并不像你想象的那么容易最长路径问题是np完全的，假设你的图不是非循环的。
关于algorithm - 图形中最长的圆圈，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/1736094/