我想解决以下问题：
我有一个DAG，其中包含需要完成的城市和工作 . 这些工作适用于可以加载限定的卡车 . 卡车装载得越多，旅行就越好 . 有些工作用于加载某些东西，有些用于加载已定义的东西 . 即使在他们之间没有工作要做，你总是可以从城市a开车到b . 最后一个限制是我总是需要从城市a开始并返回到a，因为有卡车的家:)
我首先想到了Dijkstra的最短路径算法 . 我可以很容易地把它变成最长的路径计算 . 我的问题是，现在所有这些算法都是用于计算从顶点a到b的最短路径或最长路径，但是我需要从返回到 - 在一个圆圈中 .
有一些人为我的想法踢了一脚吗？
感谢您的反馈意见！
马尔科
4 回答
背包和travelling salesman的疯狂组合肯定是NP-hard .
几乎无处不在，当您想要以最佳作业计划加载代理程序时，或者当您想要构建通过图表中所有顶点的路径时，或者当您觉得需要查找“longest path *”时，您很可能会运行进入NP-complete或NP-hard问题 .
这意味着，没有已知的快速且精确的问题解决方案，即在多项式时间内运行的解决方案 .
因此，您必须根据您的特定条件创建近似值并实现非最佳算法 . 什么时候可以接受损失？卡车可以驾驶还有其他模式吗？您对图表有更多了解（例如，区域是否分为远距离密集区域）？回答这些问题，您将找到满足您客户需求的非严格启发式方法 .
*是的，搜索最长的路径并不像你想象的那么容易 . 鉴于您的图形不是非循环的，最长路径问题是NP完全的 .
您是否正在尝试找到最简单的方法来完成所有工作？这让我想起了最大流量/最小切割问题 . 您可以通过以下方式估算出最佳答案：
将所有终端节点连接到最终的
end节点 .运行各种maximum flow算法之一，以查找
a和end之间的最大流量 .返回城市
a. 更新图表以反映您刚才所做的事情 . 重复，直到完成所有作业 .这个想法是你每次旅行都能获得最大的收益 . 第一次之后的每次旅行效率会降低，效率也会降低，但这是可以预料的 .
Note: 这仅适用，因为您有DAG . 旅行推销员不会有一个DAG，因为你可以返回城市
a- 这是真的吗？这不是Transportation problem吗？
根据卡车编号和起点，您可以添加假交通或增加成本以满足您的限制 .
我还会问卡车限制：
他们都在同一个城市吗？
你有固定数量的吗？
如果你使用的少，你会赢得什么？
有周期时间限制吗？
您可以调整旅行销售人员问题动态编程算法来做你想要的 .
经典方法表明，您希望最大限度地发挥所有城市的最佳功能，但您可以考虑，每一步都有回家的可能性 .
就像帕维尔提到的那样，这个问题肯定是NP难的 . 您是否有城市数量的上限或可以装载到卡车中的最大物体数量？
PS：你想要最佳解决方案（最大利润 - 在处理时间方面可能不太现实）或者你接受一些近似值？