algorithm - 图中最长的圆

Question

我想解决以下问题:

我有一个 DAG，其中包含城市和它们之间需要完成的工作。这些工作适用于可以装载规定限制的卡车。卡车装载的越多，旅行就越好。有些工作是为了加载一些东西，有些是为了加载定义好的东西。你总是可以从城市 a 开车到 b，即使他们之间没有工作可做。最后一个限制是我总是需要从a城市出发然后回到a因为那里是卡车之家:)

我首先想到了Dijkstra的最短路径算法。我可以轻松地将其转化为最长路径计算。我现在想到的问题是，所有这些算法都是为了计算从顶点 a 到 b 的最短或最长路径，但我需要它从 a 返回到 a - 在一个圆圈中。

有人对我有一些刺激吗？

感谢您的反馈!

马可

Answer 1

背包和travelling salesman的疯狂组合肯定是NP-hard .

几乎无处不在，当你想用最佳工作计划加载你的代理时，或者当你想建立一条通过图中所有顶点的路线时，或者当你觉得你需要寻找“longest path*”时，您很可能会遇到 NP-complete或 NP-hard问题。

这意味着，对于该问题，没有已知的快速且精确的解决方案，即在多项式时间内运行的解决方案。

因此，您必须根据您的特定 条件创建近似值并实现非最优算法。什么时间损失是可以接受的？卡车是否可以行驶其他模式？您是否对图表了解更多(例如，该区域是否划分为遥远的密集区域)？回答这些问题，您会发现一种非严格的启发式方法，让您的客户满意。

---

*是的，寻找最长的路径并不像您想象的那么容易。鉴于您的图形不是非循环的，最长路径问题是 NP 完全问题。