幅優先、深さ優先、ほかもろもろ。


※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

ダイクストラ

1度調べたノードはもう調べない⇒

「次調べるべきノードは確定的に明らか」にする。

def print_field(field):
  for line in field:
    for tile in line:
      print tile,
    print ''

#ダイクストラは変則横優先探索
#1.nextボックスの中から最短のものを選び
#2.幅優先探索と同じ処理を行う
#
#Pythonは高級な言語ですんで、
#多言語では要アレンジ。
#
#要はコストと次の探索ノードがわかるメモリ領域がほしい。
#
def dijkstra(start,goal,field):
  #ここを書き込みましょう
  pass


field=[[0,0,0,0,0,0,0,0],
       [0,1,1,1,1,1,1,0],
       [0,1,1,1,1,1,1,0],
       [0,1,1,1,0,0,1,0],
       [0,0,1,1,0,1,0,0],
       [0,1,1,0,0,1,0,0],
       [0,1,1,1,1,1,0,0],
       [0,0,0,0,0,0,0,0]]
start = (1,1)
goal = (5,4)

print_field(field)
result=dijkstra(field)
for pos in result:
  (x,y)=pos
  if field[y][x]==0:
    print 'failed ...(%d,%d)'%(x,y)
    break

if 6==len(result):
  print 'OK!'
else:
  print 'failed ...'