我正在设计一个 Android 应用程序，我试图在这种情况下找到最佳解决方案:
假设我们在起点和目的地之间有几条不同的路线，每条路线都有不同的价格和距离。如何找到距离和价格都最优的最优路径？
也就是说，如果我们在 S 和 D 之间有 5 条路由 R1、R2、R3、R4、R5
distances R2 30 miles ,
R3 40 miles ,
R1 50 miles ,
R5 60 miles ,
R4 70 miles ,
R6 80 miles
Price for R1 $5 ,
R6 $8 ,
R3 $9 ,
R5 $11 ,
R2 $13 ,
R4 $15
S 和 D 之间的最佳路线是什么？
我见过 Dijkstra 等算法和其他一些算法，例如旅行商问题，但我无法将它们与此联系起来。
是否有一些算法、公式或模型可以解决这类问题？
最佳答案
这可以通过 A*/Dijkstra 算法解决，该算法旨在在给定节点、边及其成本列表的情况下，在图上找到从 A 到 B 的最佳(总成本最低)路线。
A* 使用贪婪的方法只寻找最佳路径，而 Dijkstra 算法寻找从一个点到图上其他任何地方的最佳路径。它们基本上是相同的算法，只是应用方式略有不同。
由于您对最低价格和最短距离都感兴趣，因此您的“成本”应该是它两个方面的数学公式(例如，使用燃料价格将距离转换为价格，然后将其与价格相结合)，或者您应该为每个参数运行算法两次。
关于algorithm - 以价格和距离为约束的具有多条路线的节点之间的优化，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/16161651/