1

「セクター」内の START から GOAL までの最短経路を見つけるというプログラミングの課題があります。1 つのノードが START で、別のノードが GOAL であるノードの 2D 配列としてセクターを視覚化できます。他のすべてのノードは FLAT または HILL です。丘を越えて移動することはできません。例えば：

  0123456789
 |----------| {S = START, G = GOAL, " " = FLAT, # = HILL}
0|S         |
1|#####     |
2|          |
3|          | 
4|          | 
5|          | 
6|          | 
7|          |
8|   #######|
9|         G|
 |----------|

わかりましたので、ダイクストラのアルゴリズムを実装して、S から G への最短経路を見つけました。より短い経路を見つけさせれば、HILL を吹き飛ばすための 5 つの爆弾が与えられます。したがって、私が投稿したセクターの例では、2 つの爆弾を使用して次のようなパスを取得したいと考えています。

  0123456789
 |----------| {S = START, G = GOAL, " " = FLAT, # = HILL, + = PATH}
0|S         |
1|#+###     | Blasted away HILL @ [1][1]
2|  +       |     4 bombs remaining
3|   +      | 
4|    +     | 
5|     +    | 
6|      +   | 
7|       +  |
8|   #####+#| Blasted away HILL @ [8][8]
9|         G|     3 bombs remaining
 |----------|

プログラムをテストするために指定されたセクターは 100x100 で、厚い「山脈」があるため、爆弾が 5 つしかないので、ゴールなどに直線で爆破することができます。

爆弾を賢く使用するタイミングを計算する方法についてのアイデアはありますか? 現在、「現在見ているノードが丘で、爆弾が残っている場合は、丘を爆破する」という一時的な実装があります。明らかにそれはうまくいきませんが、適切に行う方法が思いつきません。

助けてくれてありがとう。

4

1 に答える 1

0

最初のソリューションでは、グラフ接続があり、フラットスペースのみを接続するグラフがあったと思います。各ヒルに高コスト エッジを作成することを提案します。Hill への各着信エッジのコストは、たとえば 100000 ユニットです。他のすべてのエッジのコストは 1 ユニットです (例にすぎません)。

(0,0) -> (0,1)最初の例では、コストが 100000 の場合にエッジを持つことができます。

そのため、累積コストが より大きいか等しい場合は、検索を停止する必要があります (ダイクストラでは、コストが隣接ノードの検索の場合) (bombs + 1)*100000。

基本的な考え方は、アルゴリズムがコストを最小限に抑えようとすることであり、爆弾の使用は非常に高価です。当然のことながら、最短経路は爆弾が最も少ない経路を見つけます。最小パスに 5 個の爆弾がある場合、コストは 500000 に加えて平坦な地形を通過するコストになります。

于 2014-01-18T01:08:56.287 に答える