php - A* 検索 - 最小ホップ数?

Question

A* パスファインディング アルゴリズムを作成しようとしていますが、それをうまく使いこなすのに少し苦労しています。少し背景:

私は経路探索アルゴリズムに精通しているわけではありませんが、数年前にこのテーマに触れました (それ以来、学んだことはすべて忘れてしまいました)。インターネット宇宙船に関するオンライン ゲームである EVE Online をプレイしています。開発者は、静的情報 (ゲーム内のアイテム、太陽系の位置など) のデータ ダンプをリリースします。太陽系Aから太陽系Bへの最短ルートを見つけようとしています。

このマップを見てください: http://evemaps.dotlan.net/map/UUA-F4これはゲーム内の 1 つの領域であり、各ノードがシステムです。これらのシステムの任意の 2 つの間の最短距離を計算したいと思います。

私の問題: A* についてオンラインで読んだものはすべて、2 つのノード間の距離 (たとえば、2 つの都市間の距離) を組み込んで最短経路を計算することについて話している。ホップ間の距離ではなく、ホップ数 (ノード 1 > ノード 2 > ノード 3) に関心があるため、これは私の場合には役に立ちません。これを組み込むために A* アルゴリズムを変更する方法がわかりません。

データベースにある情報: すべてのシステムとその近隣システムのリスト (したがって、systemX は systemA および systemB とリンクしています) 3D グリッド内のすべてのシステムの x、y、および z 座標

誰かが私を正しい方向に向けることができれば、それは素晴らしいことです. これを PHP で使用することを検討していますが、Python でも少し作業を開始したので、それも機能します。

必要に応じて、サンプル データをリクエストに応じて提供できます。

編集

一部の人が指摘しているように、各ジャンプに関連付けられた「コスト」は単純に 1 になります。ただし、A* では、現在のノードからターゲット ノードまでの距離を推定するヒューリスティックも必要です。残りのホップがわからないため、この値を決定する方法が正確にはわかりません。述べたように、私はすべてのノードの 3D 座標 (x、y、z) を持っていますが、各ノード間の物理的な距離は問題ではないため、これが洞察を与えるかどうかはわかりません。パスが 99 ホップを超えることはありません。

編集2

サンプル リージョンの MySQL データ。

to -> fromデータ: http://pastebin.com/gTuudr7h

システム情報 (必要に応じて x、y、z 座標): http://pastebin.com/Vz3FD3Kz

Answer 1

「ホップ」の数が重要な場合は、それを距離と考えてください。つまり、2 つの場所が 1 つのホップで接続されている場合、距離は 1 です。

A* の場合、次の 2 つが必要です。

1. ある場所から各近隣へのコストは、あなたの場合、一定 (ホップ) のようです。

2. 現在の「ノード」または場所からゴールまでのコストを見積もるヒューリスティック。これをどのように推定できるかは、問題によって大きく異なります。あなたのヒューリスティックが真のコストを*過大に*見積もらないことが重要です。さもないと、A* は最良の結果を保証できなくなります。

Answer 2

リンクされたグラフの上部を取ります:

線は 2 方向 (つまり、リンクされたノードに出入りできる) を表し、黒い線は 1 の「コスト」、赤い線は 2 の「コスト」であると仮定します。

その構造は、次の Python データ構造で表すことができます。

graph = {'Q-KCK3': {'3C-261':1, 'L-SDU7':1},
         'L-SDU7': {'Q-KCK3':1, '3C-261':1,'4-IPWK':1},
         '3C-261': {'4-IPWK':1,'9K-VDI':1,'L-SDU7':1,'U8MM-3':1},
         'U8MM-3': {'9K-VDI':1,'3C-261':1, '9K-VDI':1, 'Q8T-MC':2},
         'Q8T-MC': {'U8MM-3':2, 'H55-2R':1, 'VM-QFU':2},
         'H55-2R': {'Q8T-MC':1, '9XI-OX':1, 'A3-PAT':1, 'P6-DBM':1},
         'P6-DBM': {'A3-PAT':1, 'H55-2R':1},
         'A3-PAT': {'P6-DBM':1, 'H55-2R':1, '9XI-OX':1,'YRZ-E4':1},
         'YRZ-E4': {'A3-PAT':1}, 
         'VM-QFU': {'IEZW-V':1, 'PU-128':2},
         'IEZW-V': {'VM-QFU':1, 'PU-128':1, 'B-DX09':1},
         'PU-128': {'VM-QFU':1, 'B-DX09':1, 'IEZW-V':1},
         'B-DX09': {'IEZW-V':1, 'PU-128':1, '1TS-WIN':1},
         '1TS-WIN': {'B-DX09':1, '16-31U':1},
         '16-31U': {'1TS-WIN':1}
        }

これで、そのデータをナビゲートする再帰関数を定義できます。

def find_all_paths(graph, start, end, path=[]):
        path = path + [start]
        if start == end:
            return [path]
        if start not in graph:
            return []
        paths = []
        for node in graph[start]:
            if node not in path:
                newpaths = find_all_paths(graph, node, end, path)
                for newpath in newpaths:
                    paths.append(newpath)
        return paths       

def min_path(graph, start, end):
    paths=find_all_paths(graph,start,end)
    mt=10**99
    mpath=[]
    print '\tAll paths:',paths
    for path in paths:
        t=sum(graph[i][j] for i,j in zip(path,path[1::]))
        print '\t\tevaluating:',path, t
        if t<mt: 
            mt=t
            mpath=path

    e1='\n'.join('{}->{}:{}'.format(i,j,graph[i][j]) for i,j in zip(mpath,mpath[1::]))
    e2=str(sum(graph[i][j] for i,j in zip(mpath,mpath[1::])))
    print 'Best path: '+e1+'   Total: '+e2+'\n'  

今すぐデモ：

min_path(graph,'Q-KCK3','A3-PAT')
min_path(graph,'Q-KCK3','16-31U')

版画:

    All paths: [['Q-KCK3', '3C-261', 'U8MM-3', 'Q8T-MC', 'H55-2R', 'P6-DBM', 'A3-PAT'], ['Q-KCK3', '3C-261', 'U8MM-3', 'Q8T-MC', 'H55-2R', 'A3-PAT'], ['Q-KCK3', 'L-SDU7', '3C-261', 'U8MM-3', 'Q8T-MC', 'H55-2R', 'P6-DBM', 'A3-PAT'], ['Q-KCK3', 'L-SDU7', '3C-261', 'U8MM-3', 'Q8T-MC', 'H55-2R', 'A3-PAT']]
        evaluating: ['Q-KCK3', '3C-261', 'U8MM-3', 'Q8T-MC', 'H55-2R', 'P6-DBM', 'A3-PAT'] 7
        evaluating: ['Q-KCK3', '3C-261', 'U8MM-3', 'Q8T-MC', 'H55-2R', 'A3-PAT'] 6
        evaluating: ['Q-KCK3', 'L-SDU7', '3C-261', 'U8MM-3', 'Q8T-MC', 'H55-2R', 'P6-DBM', 'A3-PAT'] 8
        evaluating: ['Q-KCK3', 'L-SDU7', '3C-261', 'U8MM-3', 'Q8T-MC', 'H55-2R', 'A3-PAT'] 7
Best path: Q-KCK3->3C-261:1
3C-261->U8MM-3:1
U8MM-3->Q8T-MC:2
Q8T-MC->H55-2R:1
H55-2R->A3-PAT:1   Total: 6

    All paths: [['Q-KCK3', '3C-261', 'U8MM-3', 'Q8T-MC', 'VM-QFU', 'IEZW-V', 'B-DX09', '1TS-WIN', '16-31U'], ['Q-KCK3', '3C-261', 'U8MM-3', 'Q8T-MC', 'VM-QFU', 'IEZW-V', 'PU-128', 'B-DX09', '1TS-WIN', '16-31U'], ['Q-KCK3', '3C-261', 'U8MM-3', 'Q8T-MC', 'VM-QFU', 'PU-128', 'B-DX09', '1TS-WIN', '16-31U'], ['Q-KCK3', '3C-261', 'U8MM-3', 'Q8T-MC', 'VM-QFU', 'PU-128', 'IEZW-V', 'B-DX09', '1TS-WIN', '16-31U'], ['Q-KCK3', 'L-SDU7', '3C-261', 'U8MM-3', 'Q8T-MC', 'VM-QFU', 'IEZW-V', 'B-DX09', '1TS-WIN', '16-31U'], ['Q-KCK3', 'L-SDU7', '3C-261', 'U8MM-3', 'Q8T-MC', 'VM-QFU', 'IEZW-V', 'PU-128', 'B-DX09', '1TS-WIN', '16-31U'], ['Q-KCK3', 'L-SDU7', '3C-261', 'U8MM-3', 'Q8T-MC', 'VM-QFU', 'PU-128', 'B-DX09', '1TS-WIN', '16-31U'], ['Q-KCK3', 'L-SDU7', '3C-261', 'U8MM-3', 'Q8T-MC', 'VM-QFU', 'PU-128', 'IEZW-V', 'B-DX09', '1TS-WIN', '16-31U']]
        evaluating: ['Q-KCK3', '3C-261', 'U8MM-3', 'Q8T-MC', 'VM-QFU', 'IEZW-V', 'B-DX09', '1TS-WIN', '16-31U'] 10
        evaluating: ['Q-KCK3', '3C-261', 'U8MM-3', 'Q8T-MC', 'VM-QFU', 'IEZW-V', 'PU-128', 'B-DX09', '1TS-WIN', '16-31U'] 11
        evaluating: ['Q-KCK3', '3C-261', 'U8MM-3', 'Q8T-MC', 'VM-QFU', 'PU-128', 'B-DX09', '1TS-WIN', '16-31U'] 11
        evaluating: ['Q-KCK3', '3C-261', 'U8MM-3', 'Q8T-MC', 'VM-QFU', 'PU-128', 'IEZW-V', 'B-DX09', '1TS-WIN', '16-31U'] 12
        evaluating: ['Q-KCK3', 'L-SDU7', '3C-261', 'U8MM-3', 'Q8T-MC', 'VM-QFU', 'IEZW-V', 'B-DX09', '1TS-WIN', '16-31U'] 11
        evaluating: ['Q-KCK3', 'L-SDU7', '3C-261', 'U8MM-3', 'Q8T-MC', 'VM-QFU', 'IEZW-V', 'PU-128', 'B-DX09', '1TS-WIN', '16-31U'] 12
        evaluating: ['Q-KCK3', 'L-SDU7', '3C-261', 'U8MM-3', 'Q8T-MC', 'VM-QFU', 'PU-128', 'B-DX09', '1TS-WIN', '16-31U'] 12
        evaluating: ['Q-KCK3', 'L-SDU7', '3C-261', 'U8MM-3', 'Q8T-MC', 'VM-QFU', 'PU-128', 'IEZW-V', 'B-DX09', '1TS-WIN', '16-31U'] 13
Best path: Q-KCK3->3C-261:1
3C-261->U8MM-3:1
U8MM-3->Q8T-MC:2
Q8T-MC->VM-QFU:2
VM-QFU->IEZW-V:1
IEZW-V->B-DX09:1
B-DX09->1TS-WIN:1
1TS-WIN->16-31U:1   Total: 10

min_pathホップの最小数が必要な場合は、ホップの最小合計コストではなく、最短のリスト長を返すように変更するだけです。または、各ホップのコストを作成します1。

電車に関する私の以前の回答を見てください。