0

我正在设计一个 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's 和其他一些像旅行商问题这样的算法，但我无法将它们中的任何一个与此联系起来。

这类问题有一些算法、公式或模型吗？

4

3 回答 3

2

这可以通过 A*/Dijkstra 算法解决，该算法旨在在给定节点、边及其成本的列表的情况下，在图上找到从 A 到 B 的最佳（最低总成本）路线。

A* 使用贪心方法只找到最佳路径，而 Dijkstra 算法则找到从图上的一个点到其他任何地方的最佳路径。它们基本上是相同的算法，只是应用有点不同。

由于您对最低价格和最低距离都感兴趣，因此您的“成本”应该是一个涵盖这两个方面的数学公式（例如，使用燃油价格将距离转换为价格，然后将其与价格相结合），或者您应该运行每个参数算法两次。

http://en.wikipedia.org/wiki/A*_search_algorithm

http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

于 2013-04-23T05:39:51.837 回答
1

简短的回答：可能没有单一的最佳解决方案。

长答案：如果有两个相互冲突的目标，例如价格和距离，并且较短的路线是更昂贵的路线，那么实际上所有路线都是最优的。它们被称为帕累托最优。如果您无法确定此类冲突目标之间的先验可行权重，则必须推迟选择解决方案。但是您可以使用帕累托优势原则来始终获得最小的帕累托最优解集。

帕累托支配将客观空间中两点之间的可能状态分为支配或非支配。当一种解决方案支配另一种解决方案时，它至少在一个目标上更好，而在其他目标上则相同。当两个解决方案是非支配的时，第一个在至少一个目标上更好，但第二个在另一个目标上更好。因此，如果您平等地对待所有目标，则没有先验最优候选者，两者都是最优的。

例如，您经常会看到谷歌地图在询问路线时会显示替代路线。这些路线距离较短，但行驶时间较长。通常它首先选择最快的路线，所以他们的先验选择只是时间。

于 2013-04-23T14:04:51.267 回答
0

您想找到“最佳距离和最佳价格组合”，但是最佳距离和最佳价格可以有两种不同的方式，例如（A，B，C，D），我们想找到从A到D的最佳方式

  1. A --> B，距离 10，价格 10
  2. B --> D，距离 10，价格 10
  3. A --> C，距离 20，价格 5
  4. C --> D，距离 20，价格 5

因此，您可以通过使用两个差异度量来获得两种不同的方式。

但是通过使用一些数学，可以简化这个问题：

cost = distance * p1 + price * p2;
// p1 and p2 are some rate that can be learned,guessed .EG, p1 = 0.3, p2 = 0.7

所以使用dij或其他一些图算法来解决这个问题是合适的。

于 2013-04-23T06:44:17.593 回答