图中最长的圆
我想解决以下问题：
我有一个 DAG，其中包含城市以及它们之间需要完成的工作。这些工作针对的是可以装载规定限制的卡车。卡车装载的越多，旅行就越好。有些作业用于加载某些内容，有些作业用于加载定义的内容。你总是可以开车从a城市到b城市，即使它们之间没有工作要做。 最后一个限制是我总是需要从a城市出发并返回a，因为那里是卡车的家:)
我首先想到了Dijkstra的最短路径算法。我可以轻松地将其转化为最长路径计算。我现在想到的问题是，所有这些算法都是为了计算从顶点 a 到 b 的最短或最长路径，但我需要它从 a 返回到 a - 在一个圆圈中。
有人能给我一些启发吗？
感谢您的反馈！
马可
I want to solve the following problem:
I have a DAG which contains cities and jobs between them that needs to be done. The jobs are for trucks which can load a definied limit. The more the truck is loaded the better is the tour. Some jobs are for loading something in and some are for loading defined things out. You can always drive from city a to b even if there is no job to be done between them.
The last restriction is that I always need to start in city a and return to a because there is the home of the trucks :)
I first thought of Dijkstra's shortest path algorithm. I could easly turn that into longest path calculation. My problem in mind is now that all these algorithms are for calculating a shortest or longest path from vertex a to b, but I need it from a returning to a - in a circle.
Has some one some kicks for my mind?
Thanks for your feedback!
Marco
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
背包和旅行推销员的疯狂组合肯定是NP-hard。
几乎在任何地方，当您想要为代理加载最佳作业计划时，或者当您想要构建穿过图中所有顶点的路线时，或者当您觉得需要寻找“最长路径*"，您很可能会遇到 NP-complete 或 NP-难题。
这意味着，没有已知的快速且精确的问题解决方案，即在多项式时间内运行的解决方案。
因此，您必须根据您的特定条件创建近似值并实现非最佳算法。什么时间损失是可以接受的？卡车还可以行驶其他模式吗？您对图表了解更多吗（例如，该区域是否分为遥远的密集区域）？回答这些问题，您将找到令您的客户满意的非严格启发式方法。
*是的，搜索最长路径并不像您想象的那么容易。最长路径问题是 NP 完全问题，因为您的图不是是无环的。
This crazy combination of knapsack and travelling salesman is surely NP-hard.
Virtually everywhere, when you want to load your agent with optimal job schedule, or when you want to build a route through all vertexes in the graph, or when you feel that you need to look for a "longest path*", you most likely run into an NP-complete or an NP-hard problem.
That means, that there is no known fast and exact solution to the problem, i.e. the one that runs in a polynomial time.
So you have to create approximations and implement non-optimal algorithms based on your particular conditions. What time loss is acceptable? Are there additional patterns the trucks can drive? Do you know more about the graph (e.g. is the area divided into distant dense regions)? Answer these questions and you'll find a non-strict heuristics that satisfies your customers.
*yes, searching for longest paths is not as easy as you think. Longest path problem is NP-complete, given that your graph is not acyclic.
您正在尝试找到尽可能最小的方法来完成所有事情吗？这让我想起了最大流/最小割问题。您可以通过以下方式近似获得最佳答案：
end节点。a和<代码>结束。a。更新图表以反映您刚刚所做的事情。重复此操作直至完成所有作业。我们的想法是让您在每次旅行中都能获得最大的收获。第一次之后的每次旅行效率都会越来越低，但这是可以预料的。
注意：这仅在您有 DAG 时才有效。旅行推销员在 DAG 上也不是 NP 完全的，而且甚至可能不可能到达图表上的所有节点。重新阅读你的问题，似乎你没有 DAG，因为你可以返回城市
a- 这是真的吗？You're trying to find the smallest possible way to get everything done? This reminds me of a max-flow/min-cut problem. You might be able to approximate the best answer by:
endnode.aandend.a. Update the graph to reflect what you just did. Repeat until all jobs are done.The idea is that you get the most bang for every trip. Each trip after the 1st will be less efficient and less efficient, but that's to be expected.
Note: This only works because you have a DAG. Travelling salesman wouldn't be NP-Complete on a DAG, either, and it will likely be impossible to even hit all nodes on the graph. Re-reading your problem, it seems like you don't have a DAG, since you can return to city
a- is that true?您可以调整旅行商问题动态规划算法来完成您想要的操作。
经典的方法是，您希望最大限度地发挥所有城市的最佳功能，但您可以在每一步中都考虑到回家的可能性。
正如 Pavel 提到的，这个问题绝对是 NP 困难的。对于城市数量或卡车上可以装载的最大物体数量，您是否有一些上限？
PS：您想要最好的解决方案（最大利润 - 就处理时间而言可能不现实）还是接受一些近似值？
You can adjust the traveling sales man problem dynamic programming algorithm to do what you want.
The classic approach says that you want to maximize the optimum function from all cities but you can take in consideration, at each step also the possibility of returning home.
And like Pavel mentioned, this problem is definitively NP-hard. Do you have some upper bounds for the number of cities or maximum number of objects that can be loaded in a truck?
PS: Do you want the BEST solution (maximum profit - might not be realistic in terms of processing time) or you accept some approximation?
这不是交通问题吗？
根据卡车数量和起点，您可以添加虚假运输或增加成本以满足您的限制。
我还想问一下卡车限制：
你有吗？
Isn't this a Transportation problem?
Depending on the trucks number and starting points, you could add a fake transporations or add costs in order to satisfy your restrictions.
I'd also ask about truck restrictions:
you have?