5

インタビューに出演しました。1つの質問に行き詰まりました。私は同じことを求めています。

質問: 環状道路が指定されています。その道路にはガソリン ポンプの数が含まれています。各ガソリンポンプにはガソリンの量が与えられています。連続する 2 つのガソリン ポンプ間の距離も表示されます。今、無限の容量の空の燃料タンクを持つ車両が与えられています。アルゴリズムを構築して、車両が後戻りすることなく完全に一周できるようにします。そのような経路が確実に可能であることが示されています。

入力: (int 燃料[]、int 距離[])

出力:車両が環状道路を完全に一周できる場所からのガソリン ポンプ インデックス。

私のアプローチ：

  1. 各ガソリン ポンプからチェックし、途中で燃料タンクが空になっている場合は、次のガソリン ポンプに移動します。再度同じプロセスを開始します。このアルゴリズムは O(N^2) を使用します。ここで、N = ガソリン ポンプの数です。

  2. 次に、バイナリ検索の概念に移り、複雑さを O(n*logn) に減らします。しかし、私は解決策を結論付けることができませんでした。私はこの解決策を台無しにしました。

  3. 次に、その 2 つのガソリン ポンプの中で、左側のガソリンが最大であるガソリン ポンプを選択することで、ある程度の知性を適用しようとします。

4

5 に答える 5

8

（これは、Evgeny Kluevが投稿したアルゴリズムと同等である可能性がありますが、私にはわかりません。その場合、その回答が優先されます。）

F_i_jを、iで充填する前にタンク内の燃料がゼロで、iで開始した、jに到着したときのタンク内の正味の符号付き燃料量とします。

各ノードで燃料を追加し、各エッジの燃料コストを差し引く円を回避して、すべてのノードiのF_0_iを計算します。

0から始まる回路の終わりの正味燃料であるF_0_0が負の場合、システムに十分な燃料がありません（これは問題の説明によると発生しないはずです）。

F_0_iが負でない場合は、結果として0を報告します。

それ以外の場合は、F_0_sの値が最も負のノードsを見つけます。開始ノードとしてsを選択します。

どのノードiでも、F_s_iはF_0_i + abs（F_0_s）に等しくなります。F_0_sは最も負のF_0_iであるため、F_s_iは非負になります。

Worked example, as suggested in a comment by Handcraftsman:
Label nodes 0 through 4

node: 0,1,2,3,4
fuel: 1,3,4,4,1
dist: 1,4,2,2,2


First calculate F_0_i for i = 1, 2, 3, 4, 0
Start at node 0 with 0 fuel.

f_0_1 = 0 + 1 - 1 = 0, min score 0, node 1;
f_0_2 = 0 + 3 - 4 = -1, min score -1, node 2;
f_0_3 = -1 + 4 - 2 = 1;
f_0_4 = 1 + 4 - 2 = 3;
f_0_0 = 3 + 1 - 2 = 2;

f_0_0 is non-negative, so there is enough fuel.

The minimum score was -1, at node 2, so the result is node 2.
于 2012-11-07T05:24:54.307 に答える
3

ブルートフォース ソリューションは明らかです。すべての i から開始し、利用可能なガスですべてのポイントに到達できるかどうかを確認します。ガスが負の数に達することなく旅行を完了することができる最初の i を返します。ただし、このアプローチは 2 次になります。どうすれば改善できるか見てみましょう。

ここで貪欲なアプローチを取ることができます。

1 ガスの合計がコストの合計よりも大きい場合、解がないことを意味します。出発点を捨てることができる

2 i から開始し、j で sum(gas) - sum(cost) の最初の負数をヒットするとします。TotalSum(gas) - TotalSum(cost) > 0 であることがわかっています。したがって、i を j に破棄し、j + 1 から開始できます。

上記アルゴリズムの Java コード 

        public int canCompleteCircuit(final List<Integer> gas, final List<Integer> cost) {
            int start = 0;
            int totalGas = 0;
            int totalCost = 0;
            int currentCost = 0;
            for (int i = 0; i < gas.size(); i++) {
                totalCost += cost.get(i);
                totalGas += gas.get(i);
                currentCost += gas.get(i) - cost.get(i);
                if (currentCost <0){
                    start = i + 1;
                    currentCost = 0;
                }
            }

            if (totalCost > totalGas){
                return -1;
            }

            return start;

        }
于 2015-12-19T16:13:17.400 に答える
2

正しいコースを見つけることができるとき、私は最初の理解なしでは問題を解決できませんでした.

D- すべての距離の P合計 - すべての燃料ポンプの合計

  1. P < D問題が解決できない場合
  2. P = D常に解決策がある場合、以下の証明
  3. P > Dいくつかのポンプを減らして、ソリューションをあたかもP = D.

P = Dつまり、コースを完了するのに必要な量の燃料が正確にあると仮定します。タンク内の燃料の量を時間の関数としてグラフを描いてみましょう。タンク時間が 0 の場合、それは実際の関数ではありませんが、重要ではありません。どこからでも始めて、タンクに燃料を入れます。

ポンプ 1、4、3 および距離 2、5、1 の例:

   |\       
   | \      
|\ |  \  |\ 
  \|   \ |  
        \|

注意事項:

  1. 私たちは無限に旅をすることができ、チャートは同じように繰り返されます。出発時と同じ量の燃料でスタート地点に戻ります。
  2. 燃料量が最も少ないポイントが常に 1 つあり、常に同じステーションになります (最小ステーションが複数ある場合は、何も変わりません)。
  3. 別の場所から開始すると、極小点は常に同じ駅になります。

上記に基づいて、最小限のポンプで開始し、それに 0 レベルを割り当てます。それは私たちの燃料が決してゼロ以下にならないという証拠です。

これで、との計算は不要ですが、エフゲニーの解が正しいことがわかりました。ポンプ値を加算して距離を減算するだけで済みます。Evgeny のアルゴリズムでは. したがって、最適な出発駅は、最小限の燃料で到着する駅です。SS/NV

エフゲニーが恣意的な方向に進む理由を理解するのに時間がかかりました。なぜ彼は、解決策が彼が取った方向に存在し、反対の方向には存在しないと確信しているのですか? しかし、それP = Dがコースを修了するための十分条件であることがわかっている場合、方向性は重要ではないこともわかります。反対方向の出発点として別の駅を選ぶ必要がありますが、両方の方向でそれを行うことができます.

ニティス、あなたに与えられた時間は？会社名を教えてください。:) 少なくとも同様の循環問題に慣れていない人にとっては、かなり難しい作業だったと思います。

于 2012-11-07T06:52:34.333 に答える
0

これは再帰の条件です。最初に、最後のストレッチで燃料が残っているかどうかを確認します。必要な燃料がxで、ポンプnの燃料がyの場合、x> yの場合、（xy）+ポンプn、n-1間のストレッチに必要な燃料が必要です。それ以外の場合は、最後に必要な燃料のみが必要です。ただし、ポンプn-1から1回のストレッチが必要です。これは、ポンプ1に到達するまで続きます。

于 2012-11-07T05:11:58.723 に答える