0

次のような状況で最適なソリューションを見つけようとしている Android アプリケーションを設計しています。

出発地と目的地の間にいくつかの異なるルートがあり、各ルートの価格と距離が異なるとします。最適な距離と価格を兼ね備えた最適なルートを見つけるにはどうすればよいでしょうか。

つまり、S と D の間に R1、R2、R3、R4、R5 の 5 つのルートがある場合、

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 の間の最適なルートは?

ダイクストラのようなアルゴリズムや、巡回セールスマン問題のようなアルゴリズムを見てきましたが、どれもこれに関連付けることができませんでした。

この種の問題のためのアルゴリズム、公式、またはモデルはありますか?

4

3 に答える 3

2

これは、ノード、エッジ、およびそれらのコストのリストが与えられたときに、グラフ上で A から B への最適な (総コストが最も低い) ルートを見つけるように設計された A*/ダイクストラのアルゴリズムによって解決できます。

A* は貪欲なアプローチを使用して最適なパスのみを見つけますが、ダイクストラのアルゴリズムはグラフ上のある点から他の場所への最適なパスを見つけます。これらは基本的に同じアルゴリズムで、適用方法が少し異なります。

最低価格と最低距離の両方に関心があるため、「コスト」はその両方の側面に関する数式である必要があります (たとえば、燃料価格を使用して距離を価格に変換し、それを価格と結合します)。パラメータごとにアルゴリズムを 2 回実行します。

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

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

于 2013-04-23T05:39:51.837 に答える
1

簡単な答え: 単一の最適なソリューションは存在しない可能性があります。

長い答え: 価格と距離などの 2 つの相反する目標があり、短いルートがより高価なルートである場合、実際にはすべてのルートが最適です。それらはパレート最適と呼ばれます。このような相反する目的の間でアプリオリに実行可能な重み付けを決定できない場合は、ソリューションを選択する選択を延期する必要があります。ただし、パレート優勢の原則を使用して、パレート最適解の最小セットを常に取得できます。

パレート優勢は、目的空間内の 2 点間の可能な状態を、優勢または非優勢のいずれかに分離します。ある解決策が別の解決策を支配する場合、少なくとも 1 つの目的ではより優れており、他の目的では同等です。2 つのソリューションが非支配的である場合、少なくとも 1 つの目的では最初のソリューションが優れていますが、別の目的では 2 つ目のソリューションが優れています。したがって、すべての目的を同等に扱う場合、アプリオリに最適な候補はなく、両方が最適です。

たとえば、Google マップが道順を尋ねるときに別のルートを提示しているのをよく見かけます。これらは、距離は短くなりますが、運転に時間がかかるルートです。通常、最初に最速のルートを選択するため、先験的な選択は時間のみです。

于 2013-04-23T14:04:51.267 に答える