2

以前の投稿の後に、詳細を記載して再投稿します。

問題 : 問題は、地図上に広がるさまざまな都市に移動しなければならない略奪者で構成されています。開始位置はわかっています。各都市には固定の戦利品が関連付けられています。マローダーの目的は、地形のさまざまな性質を横断することです。地形の性質上、各都市間の移動コストはさまざまです。彼は獲得した戦利品を最大化する必要があります。


実行したこと: 隣接行列 (各ノードのブート パス コスト) を生成し、ヒューリスティック分析を採用しました。妥当な出力が得られました。

さて、現在の問題は、各都市には、（支払いによって）購入して旅行に使用できる車両がほとんどないか、または多いことです。車両が実際に行うことは、経路コストを削減することです。車両を購入すると、次の車両を購入するまで残ります。車両を購入するかどうか、およびどのように購入するかを決定するのはあなた次第です。

この時点で助けが必要です。車両のアイデアを私たちがすでに持っているものにどのように統合するか? さらに、利益を最大化するのに役立つその他のアイデア。必要に応じて、コードを投稿できます。ありがとう！

4

2 に答える 2

4

これを行う 1 つの方法は、削減されたコストを持つ複製グラフに向かって、車両のコストを負担する有向エッジを持つことです。必要に応じて、削減が単なるパーセンテージよりも細かくなるようにすることもできます。

欠点は、これによりおそらくグラフのサイズが大幅に増加することです (さまざまな車両とそれらの間のリンクがあるのと同じ数のコピー)。新しいエッジを積極的に。

于 2013-01-14T13:44:20.603 に答える
1

ビーム探索がこの問題に適しているように思えます。ビーム検索はヒューリスティック関数Hとパラメーターkを使用し、次のように機能します。

  1. セットSを初期ゲーム位置に初期化します。

  2. Tを空集合に設定します。

  3. Sの各ゲーム位置について、略奪者が 1 回移動した後、 Sに続く可能性のあるすべての位置を生成します。(移動とは、略奪、車両の購入、隣接する都市への移動、または略奪者ができるその他のことです。) そのようなそれぞれの後継者の位置をセットTに追加します。

  4. Tの各位置pについて、ヒューリスティック関数HについてH ( p ) を評価します。(ヒューリスティック関数は、戦利品の量、車両の所有、略奪されていない残りの都市の数、および関連性があり計算が容易であると思われるその他すべてを考慮に入れることができます。)

  5. 検索時間を使い果たした場合は、Tで最高得点の位置を返します。

  6. それ以外の場合は、SをT内の最高得点のk位置に設定し、手順 2 に戻ります。

Tをk 個の要素を持つヒープの形式で格納すると、このアルゴリズムはうまく機能します。

于 2013-01-14T15:41:38.150 に答える