8

開始ノードから終了ノードまでのパスを提供するアルゴリズムが必要ですが、パスには正確な数のノードが必要です。そうでない場合、パスファインディングは失敗します。

拡張するために、タイルのグリッドがあります。移動は、すぐ隣の上下左右のタイルにのみ行うことができます (つまり、斜めの移動はできません)。パスで使用できるタイルと使用できないタイルには多くのルールがありますが、ほとんどの場合、単純なブール値に要約して、タイルを使用できるかどうかを判断できます (これは、アルゴリズムを開始する前に計算することもできます)。 . しかし、私に問題を引き起こしているのは、パスに必要な距離が指定されているという事実です。つまり、1 つのタイルから隣接するタイルへのすべての移動は 1 の距離であり、パス全体には指定された距離、それ以上でもそれ以下でもありませんまた、一度タイルが踏まれると (ただし、アルゴリズムの開始時にすべてのタイルが利用可能です)、再び踏むことはできません。自分で食べないように気をつけなければなりません。

私は Dijkstra/A* を見て、パスファインディングのアルゴリズムをグーグルで検索しましたが、私が知る限り、すべてが最短パスに焦点を合わせているため、あまり役に立ちません。前述のルールに従っている限り、どのパスであってもかまいません。

私は何かを見逃しましたか、そのようなアルゴリズムはすでに存在していますか、またはこの結果を得るために Dijkstra/A* を変更する簡単な方法はありますか? 私は英語を母国語としないので、間違った用語を使用している可能性があります。このタイプのアルゴリズムのキーワードの提案を歓迎します。


これは、正確な距離である必要があり、同じタイルを 2 回使用することはできないと私が言っていることの例です。

距離が 7 でなければならないとしましょう。今度は、パスで使用できるタイルを O、使用できないタイルを X、開始点を S、ゴールを E でマークしましょう。

XXXXXXX
XOOESOO
XOOOOOO

距離制限がなければ、左に行って問題を解決できます。距離制限があっても「同じ牌を踏めない」という制限がなければ、一度下って、左、右、左、右、左、上でゴールできます。 . 両方の制限があるため、右、下、左、左、左、上、右に移動してゴールに到達する必要があります。しかし、このような状況では、有効なパスはありません。

XXXXXXX
XOOESOO
XXOOOXO

関連する場合に備えて、このボードゲームを C# で開発しています。

最大距離については、距離の範囲は次のとおりです。プレイヤーはサイコロを投げて、1 ～ 6 の数字を出します。プレイヤーが 6 を出したら、もう一度サイコロを投げ、別の 6 が出たら、6 が出なくなるまで何度も何度もサイコロを投げます。 8 まで上がりますが、通常は 0 ～ 3、または 4 です。

別の注意として、私は新しい注文を受け取ったばかりで、ゲームのルールが変更され、同じパスで同じ位置を2回踏むことができるようになりました。これにより、プロセスが大幅に簡素化されると思いますが、この質問はそのままにしておきますそのような状況で誰かを助けることができる素晴らしい答えがあると思います.

4

4 に答える 4

3

Haileが指摘したように、NP完全であるため、問題が十分に小さい場合のヒューリスティックを次に示します。

  • S含まれていない半島 (つまり、1 つのノードだけで残りの部分に接続されているグラフの部分) を見つけて、Eそれらを削除します。
  • PからSへの最短経路を見つけますE。nより小さい場合、len(P)解はありません。
  • Sここで、 からまでの深さ優先検索を実行Eし、次のヒューリスティックを使用して最初に掘るノードを選択します。深Aさ優先検索で現在のタイルとします。ユークリッド幾何学では、 の位置をA直線上に射影し、(SE)この点を と呼びますA'。比率len(current path) / nを に近づけるようにしてくださいlen([SA']) / len([SE])。Aまたは、何らかの方法でパスPに「投影」して、比率を に近づけてA''維持します。len(current path) / nlen([SA''] along P) / len(P)

処理する正確なケースについてはあまりわかりませんが、深さ優先検索ツリーの一部を破棄するために追加するヒューリスティックが他にもあることは確かです。

于 2012-09-20T09:56:04.347 に答える
3

各ステップのコストが 1 になるという問題があるため、深さ制限検索と呼ばれる深さ優先検索の単純なバリアントで、必要な種類のパスを見つけることができるはずです。Python の単純なバージョン:

def dls(path, goal, depth):
    last = path[-1]
    if len(path) == depth:
        if last == goal:
            return path
    else:
        for n in neighbors(last):
            if allowed(n) and n not in path:
                path.append(n)
                solution = dls(path, depth)
                if solution:
                    return solution
                path.pop()

# call as:
dls([start], goal, depth)

他の人が指摘したように、問題は NP 完全であるため、より長いパスの長さに対して奇跡を期待しないでください。

Russell & Norvigは、この種のアルゴリズムの決定的な教科書です。

于 2012-09-20T10:01:03.407 に答える
2

このための高速なアルゴリズムがあれば、プラグインすることができ、アルゴリズムはハミルトニアン パスnumber of nodes = nがあるかどうかをすぐに教えてくれます。その問題はNP完全なので、あなたの問題もそうです。

于 2012-09-20T09:41:46.293 に答える
0

質問が距離の通常の値で更新されたので...

したがって、各タイム ステップでは、最大で 4 つの選択肢があり、最大で 5+4 = 9 つのステップがあります。これにより、潜在的なパスは 4 9 = 262 144未満になります。最初に力ずくで試してみて、どこまで行けるか見てみましょう。

また、6 以外の目が出るまでサイコロを繰り返し投げることは、1 から 5 の間の乱数を引くことと同じであることに注意してください。10 面ダイスを使用することも一般的です。

于 2012-09-20T14:51:32.763 に答える