0

無向グラフしか作れません。監督されたものを作る方法がわかりません。

何か案が？

4

3 に答える 3

1

かなり長い曲がりくねった投稿をお詫びします。電車の中で暇つぶしがありました。

あなたが求めているのは、開始位置から離れたすべてのパスを表す有向グラフだと思います (任意の開始/終了位置を解決するために使用できる迷路のグラフ表現とは対照的です)。

（悪意はありませんが）これは宿題のように聞こえますが、少なくとも、宿題に非常に適したタスクです。これを念頭に置いて、次のソリューションでは、パフォーマンスやエレガンスよりもシンプルさに重点を置いています。

アプローチ

これを行う簡単な方法の 1 つは、最初にマップをよりナビゲートしやすい形式で保存し、次に開始ノードから始めて次の手順を実行することです。

  1. 隣人を調べる (上、下、左、右)
  2. 各隣人について:
    • 可能なパスでない場合は無視します
    • 以前にこのノードを処理したことがある場合は、無視します
    • それ以外の場合は、このノードをエッジとして追加し、さらに処理するためにキュー (スタックではなく、これについては後で詳しく説明します) にプッシュします。
  3. キュー/スタック内のノードごとに、手順 1 から繰り返します。

(以下の実装例を参照)

この時点で、ツリーの最上部に開始ノードがあり、葉の 1 つとして終了ノードを持つ有向非巡回グラフ (DAG)が完成します。この時点でこれを解決するのは簡単です。グラフとして表す迷路の解法については、この回答を参照してください。

グラフを作成する際に考えられる最適化は、終点が見つかったら停止することです。不完全なグラフになってしまいますが、最終的な解だけに関心があるのであれば、これは問題ではありません。

スタックまたはキュー?

スタック (先入れ先出し) を使用すると深さ優先でグラフを構築することを意味し、キュー (先入れ先出し) を使用すると幅優先アプローチになることに注意してください。

通常、最短パスを探すことが目的の場合は、キュー (幅優先) を使用することをお勧めします。次のマップを検討してください。

       START
########   ###### 
########   ######
### b    a ######  
###   ##   ######
###   ## e ######
### c    d ######
########   ######
########      END
#################

パスが深さ優先でトラバースされ、ブランチaでたまたまa->b前のパスをたどるa->eと、グラフは次のようになります。

 START
   |
   a
  / \
 b   e   <-- end, since d already visited
 |
 c
 |
 d
  \
   END

ただし、幅優先のアプローチを使用すると、a->eパスはノードdに早く到達するため、グラフが短くなり、ソリューションが改善されます。

 START
   |
   a
  / \
 b   e 
 |   |
 c   d
     |
    END

サンプルコード

入力例:

..........
#########.
..........
.#########
......#...
#####...#.
##...####.
##.#......
...#######

e = (0,0)
s = (8,0)

免責事項: 次のコードは、速度ではなく、わかりやすくするために書かれています。完全にテストされていないため、正確性を保証するものではありませんが、何が可能かについてのアイデアが得られるはずです。

入力ファイルが一貫してフォーマットされていることを前提としています。簡潔にするために、ほとんどのエラー チェックは省略されています。

# regex to extract start/end positions
import re
re_sepos = re.compile("""
    ^([se])\s* # capture first char (s or e) followed by arbitrary spaces
    =\s*        # equal sign followed by arbitrary spaces
    \(          # left parenthesis
    (\d+),(\d+) # capture 2 sets of integers separated by comma
    \)          # right parenthesis
""", re.VERBOSE)

def read_maze(filename):
    """
    Reads input from file and returns tuple (maze, start, end)
      maze : dict holding value of each maze cell { (x1,y1):'#', ... }
      start: start node coordinage (x1,y1)
      end  : end node coordinate (x2,y2)
    """
    # read whole file into a list
    f = open(filename, "r")
    data = f.readlines()
    f.close()

    # parse start and end positions from last 2 lines
    pos = {}
    for line in data[-2:]: 
        match = re_sepos.match(line)
        if not match:
            raise ValueError("invalid input file")
        c,x,y = match.groups() # extract values
        pos[c] = (int(x),int(y))
    try:
        start = pos["s"]
        end   = pos["e"]
    except KeyError:
        raise ValueError("invalid input file")

    # read ascii maze, '#' for wall '.' for empty slor 
    # store as maze = { (x1,y1):'#', (x2,y2):'.', ... }
    # NOTE: this is of course not optimal, but leads to a simpler access later 
    maze = {}
    for line_num, line in enumerate(data[:-3]): # ignore last 3 lines
        for col_num, value in enumerate(line[:-1]): # ignore \n at end
            maze[(line_num, col_num)] = value

    return maze, start, end

def maze_to_dag(maze, start, end):
    """
    Traverses the map starting from start coordinate.
    Returns directed acyclic graph in the form {(x,y):[(x1,y1),(x2,y2)], ...}
    """
    dag = {}        # directed acyclic graph
    queue = [start] # queue of nodes to process

    # repeat till queue is empty
    while queue:
        x,y = queue.pop(0)      # get next node in queue
        edges = dag[(x,y)] = [] # init list to store edges

        # for each neighbour (top, bottom, left, right)
        for coord in ((x,y-1), (x,y+1), (x-1,y), (x+1,y)): 
            if coord in dag.keys(): continue   # visited before, ignore

            node_value = maze.get(coord, None) # Return None if outside maze
            if node_value == ".": # valid path found
                edges.append(coord) # add as edge
                queue.append(coord) # push into queue

                # uncomment this to stop once we've found the end point
                #if coord == end: return dag

    return dag

if __name__ == "__main__":
    maze,start,end = read_maze("l4.txt")
    dag = maze_to_dag(maze, start, end)
    print dag
于 2011-01-20T15:03:39.023 に答える
0

このページは、Pythonでグラフを実装するための優れたチュートリアルを提供します。記事から、これは辞書で表されるディレクトリグラフの例です。

graph = {'A': ['B', 'C'],
         'B': ['C', 'D'],
         'C': ['D'],
         'D': ['C'],
         'E': ['F'],
         'F': ['C']}

そうは言っても、 NetworkXやigraphなどの既存のグラフライブラリを調べることもできます。

于 2011-01-19T17:02:13.000 に答える
0

既にリストがあるので、辞書の代わりに隣接行列を作成してみてください。

list_of_houses = []
directed_graph = [][]
for i in xrange(len(list_of_houses)):
    for i in xrange(len(list_of_houses)):
        directed_graph[i][i] = 0

次に、ある家から別の家への新しいエッジ（または接続がある場合）

directed_graph[from_house][to_house] = 1

これで完了です。house_aからまでのエッジがあれhouse_bばdirected_graph[house_a][house_b] == 1.

于 2011-01-19T18:29:33.657 に答える