开发者社区

文档建议反馈控制台

文章/答案/技术大牛

发布

社区首页 >问答首页 >TSP:距离约束下的利润最大化

问TSP:距离约束下的利润最大化
EN

Stack Overflow用户

提问于 2021-10-23 14:15:41

回答 1查看 42关注 0票数 0

为了尽可能简单，有没有一种TSP的变体，我试图最大化收益，但限制了我可以带着回家的需求旅行的路程？(我对这些类型的算法相当生疏，可能需要DP?)

假设我可以计算每个节点之间的距离，并且从列表中删除每个被访问的节点。

我认为应该以成本/收益比作为权重来指导它(因为成本可能在方向上有所不同)。

任何建议都很感谢。

graph-algorithm

traveling-salesman

EN

回答 1

Stack Overflow用户

发布于 2021-10-23 15:06:29

运行标准TSP
如果总距离小于最大已完成
运行Dijsktra以查找从主页到每个折点的距离
从TSP移除距离最远的折点

票数 0

EN

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/69688971

复制

相似问题