1

ゲームボード上のパスは、次のような形式の辞書に保存されています。

{1: [2,3,4], 2: [1,3,5], 3: [1,2,4], ...}

つまり、スペース1を使用している場合は、スペース2、3、または4などに移動できます。すべてのキーは、リスト内の少なくとも2つの値にリンクしています。多くは4つ以上あります。ボードには合計199のスペースがあります。注目すべき点は、スペースをスキップできる場合があることです。

{1:[2,3,4], 2:[3]}

... 1-> 2-> 3に進むことも、1->3に進むこともできます。

2つの正方形の間の最短距離を見つけるためのアルゴリズムを作成しようとしています。明らかな考えは、開始スペースのキーを検索し、次にリストの最初の番号を取得し、その可能性のあるスペースを検索するなど、以前に表示された番号のいずれかにヒットしたときに停止して前のリストに戻ることです。または最後の正方形（結果の正方形に当たった場合のパスと距離を保存し、終了後に比較します）。

ただし、これを実装する方法についてはほとんどわかりません。（ステップが2つしかない場合は、ネストされたループを使用しますが、レベルがいくつになるかわからないため、ここでは機能しません）。

他のデータ構造を含むより良いソリューションまたは最適化を歓迎します。この辞書に似たCSVファイルにデータを保存しているので、うまくいけば他のファイルに簡単に変換できます。

これが私が使っているボードの写真へのリンクです：http： //goo.gl/Rasq6

編集：さて、私はダイクストラのアルゴリズムを実装しようとしています。これが私が持っているものです：

  1 movedict, transdict = boardstruct.prepare_board()
  2 
  3 source = 87
  4 dest = 88
  5 
  6 dist = {}
  7 prev = {}
  8 for v in movedict.keys():
  9     dist[v] = float('inf')
 10     prev[v] = None
 11 
 12 dist[source] = 0
 13 q = movedict.keys()
 14 
 15 while q:
 16     smallest = float('inf')
 17     for i in q:
 18         dist_to = dist[i]
 19         if dist_to < smallest:
 20             smallest = dist_to
 21     print smallest
 22     u = q.pop(smallest)
 23     print u
 24 
 25     if dist[u] == float('inf'):
 26         break
 27 
 28     for v in movedict[u]:
 29         alt = dist[u] + 1 # distance = flat 1
 30         if alt < dist[v]:
 31             dist[v] = alt
 32             prev[v] = u
 33             # reorder queue?

（21と23は、削除するのを忘れたデバッグステートメントです）

必要なデータ形式に一致する既存の実装が見つからないため、ウィキペディア（http://en.wikipedia.org/wiki/Dijkstra's_algorithm#Pseudocode）の擬似コードを処理しています（すべての移動で固定費なので、距離はどこにも保存されません）。

最後にキューを並べ替える必要があることは理解していますが、方法がわかりません。また、25行目と26行目が何のためにあるのかわかりません（コメントには、「残りのすべての頂点はソースからアクセスできません」と書かれています。これにより、最適なパスがすでに見つかっていることが保証されている場合に、それ以上実行されなくなりますか？）。私も何か他のことを台無しにしたので、よろしければご覧いただければ幸いです。

4

2 に答える 2

3

What you're describing is a shortest path problem. There are several ways to solve it. Dijkstra's algorithm is one of the simplest to implement, but it's overkill for your application. (It finds the shortest path from one node to all other nodes.) There's a related algorithm called A* that's a little more complicated, but it does exactly what you're looking for.

于 2012-12-31T04:53:07.427 に答える
2

networkxを使用します。簡単にインストールできます。

ゲームボードの写真から、スコットランドヤードのゲームを認識します。
@Bill the Lizard との会話についてコメントします
。ノードもエッジも変化しません。タクシーで5段、または地下1段で
アクセスできます。4613

おそらく、すべてのエッジ (タクシー、バス、地下鉄) を含む 1 つの「大きな」グラフと、タクシー + バス、タクシー + 地下鉄、およびタクシーのみを組み合わせたいくつかのグラフを使用します (ゲームのルールはよく覚えていません...何が理にかなっているのかを理解する必要があります）。

networkx のアルゴリズムが同順位をどのように処理するのかわかりません!

したがって、先のすべての最短経路を事前計算します。
次に、必要なときにいつでもそれらを調べてください。

import networkx as nx

# simplified example
# data is in the format as you specified
data = data = {1: [2,3,4],
               2: [1,3,5],
               3: [1,2,4],
               4: [1,3,5],
               5: [2,4]}

# initialize empty graph
G = nx.graph()

# now we're adding all edges
# don't bother about duplicates -- they're ignored
for n1, n in data.items():
    for n2 in n:
        G.add_edge(n1, n2)

# get ALL shortest paths
p = nx.shortest_path(G)

# lookup when needed, e.g. from 1 to 5
p[1][5]
# gives [1, 2, 5]
于 2012-12-31T19:38:31.293 に答える