11

さまざまな整数の長さの道路で接続された町のネットワークがあります。

旅行者は、ある町から別の町へ車で移動したいと考えています。ただし、彼は移動距離を最小限に抑えたくありません。代わりに、彼は旅のガソリン代を最小限に抑えたいと考えています。ガソリンはどの都市でも購入できますが、各都市はさまざまな (整数の) 価格でガソリンを供給します (したがって、最短ルートが必ずしも最安値であるとは限りません)。ガソリン 1 単位で、彼は 1 単位の距離を運転できます。彼の車は、タンクに入れることができるガソリンの量に制限があり、移動する各都市で購入するガソリンの単位を選択できます。最低ガソリン代を求めよ。

この問題を解決するために使用できる効率的なアルゴリズムを知っている人はいますか? このタイプの問題の名前でさえ、私が自分で調査できるように役立つでしょう! 明らかに、最短経路問題とはまったく同じではありません。その他のヒントをいただければ幸いです。

編集-私が抱えている実際の問題は、1000未満の都市があると述べています。<10000 道路; ガソリンタンクの容量は 1 から 100 の間になります。

4

6 に答える 6

5

グラフのサイズを大きくしてもよければ、Djikstra のアルゴリズムを使用してこれを直接解決できます。

ガソリン タンクに 0 ～ 9 単位のガソリンを入れることができるとします。

各町を 10 個のノードに分割し、町 t のノード x は町 t にあり、タンクに x 単位のガソリンがあることを表します。

次に、この展開されたグラフにゼロ コストのエッジを構築して、異なる町間の移動を表すことができます (ガソリンを消費するため、距離が 3 の場合、レベル 8 のノードからレベル 5 のノードに移動します)。各町のタンクに 1 単位のガソリンを入れることを表します (料金は町によって異なります)。

次に、Djikstra を適用すると、最初から最後まで最小コストのパスが得られます。

于 2012-08-17T18:01:21.150 に答える
1

質問は次のとおりです。ガソリンが根本的な巡回セールスマン問題を計算上実行可能にする可能性はありますか？そうでない場合、効率的な非近似アルゴリズムはありません。

もちろん、エッジケースの効率的な解決策を見つけることができます。ガソリンが非常に安いため、常にこの都市を最初に取るように、ガソリンの状態でエッジケースが増える可能性があります。

于 2012-08-17T16:33:25.987 に答える
1

動的計画法で解決できると思います。ノードごとに、最適解を含む、ガソリン コストとそのガソリンを使用する経路の長さのタプルの配列を保存します。すべてのノードをループするすべてのステップで、すでに解決策があるノードがある場合は、ソリューションで移動できるすべてのノードをループします。最小コストを選択しますが、注意: 現在のノードのガソリン コストを考慮する必要があります。現在のノードのコストよりも高いアレイ内のすべてのコストは、代わりに現在のノードで購入できます。そこから移動できるノードが変更される可能性があるため、既にソリューションを持っているノードは再計算する必要があることに注意してください。エンド ノードから始めて、解を空の配列 (またはコストと長さが 0 の 1 つのエントリ) に設定します。

于 2012-08-17T16:36:53.983 に答える
0

これを整数線形計画（ILP）問題として定式化することもできます。利点は、このタスク用の既製のソルバーが多数あり、タンクのサイズを持つPetersソリューションの場合ほど複雑さが増すことはないということです。

この特定の問題の変数は、任意の1つの町で購入されたガソリンの量、途中の任意の町の車のタンクの量、および実際に通った道路です。制約は、車がすべての道路で必要な燃料を消費し、どの町でも0未満またはMAXを超える燃料がないこと、および道路がAからBへのパスを構成することを保証する必要があります。購入した燃料の総費用。

全体が巨大に見えるかもしれませんが（ILP製剤はしばしばそうします）、それはそれが合理的な時間で解決できないという意味ではありません。

于 2012-08-20T16:06:10.383 に答える
0

私はこれを試してみます：

  1. 出発地から目的地までの最短ルートを検索します。これにはダイクストラのアルゴリズムが適しています。
  2. このルートを移動するためのガソリンの最小コストを見つけます。このための既製のアルゴリズムは知りませんが、ルートに沿って多くの都市がない限り、徹底的な検索でさえ計算上実行不可能になることはありません。
  3. 次の最短ルートを見つけて...

正確な停止基準を定義することは、少し難しい作業です。新しくテストされたルートの最小コストが、既にテストされたルートの最小コストよりも大きくなったら、停止するのが最善かもしれません。

したがって、問題の各部分に 1 つずつ、2 つのアルゴリズムを使用します。

于 2012-08-17T16:59:13.307 に答える
0

これは、遺伝的アルゴリズムを使用して適切に最適化できます。遺伝的アルゴリズムは、いくつかの複雑な問題で人間を打ち負かします: http://en.wikipedia.org/wiki/Genetic_algorithm

遺伝的アルゴリズムの要点は次のとおりです。

  1. 解候補のランキング関数を考える
  2. 独自の候補ソリューションのプールを考え出します。ランダムに生成されたいくつかの可能性で初期化します。たぶん10か100か1000...
  3. プールから候補解をコピーし、何らかの方法でそれを混乱させます - 町を追加する、町を削除する、2 つの町を追加するなど。あなたはどちらを選びますか？通常は最善のものを選択しますが、場合によっては、局所最適に行き詰まらないように意図的に選択することもあります。
  4. 新しいソリューションはすでにランク付けされていますか? はいの場合は、ジャンクして次の場所に移動します
    1. いいえの場合は、続行...
  5. 新しく計算されたランクの下で、摂動候補をプールに戻します
  6. 十分長くやったと感じるまで、これを続けます (#3 から繰り返します)。
  7. 最後に、最高ランクの回答を選択します。最適ではないかもしれませんが、かなり良いはずです。
于 2012-08-17T23:17:09.447 に答える