再帰は終わらないんじゃなくて、まだ終わってないだけ。アルゴリズムは超大事

ちょっと気になっていた問題が公開されたのでやってみた。問題は以下のページ

さて試験問題です。

で、実際に書いたコードは

#!/usr/bin/env python 
# coding:utf-8

maze='''**************************
*S* *                    *
* * *  *  *************  *
* *   *    ************  *
*    *                   *
************** ***********
*                        *
** ***********************
*      *              G  *
*  *      *********** *  *
*    *        ******* *  *
*       *                *
**************************'''

def makeMazeArr(mazeArr):
 global dircDict
 return tuple(tuple(mazeArr.split('\n')))

def curMove(direction, curPos):
  global dircDict
  for i in range(len(curPos)):
    curPos[i] += dircDict[direction][i]
  return curPos

def getChar(arr):
  global maze
  curChar =  maze[arr[0]][arr[1]]
  if curChar == '*':
    return ['stop', arr]
  elif curChar == ' ':
    return ['next', arr]
  else:
    return ['finish', arr]

global_res = []
def saikikun(PosList):
  import time
  time.sleep(0.01)
  global global_res
  nextPosList = []
  #print 'Start PosList: %s'%(PosList)
   
  # 現在のポジションの周り4つを探す
  for i in dircDict.keys():
    nextPosList.append(curMove(i, PosList[-1][:])[:])

  # 移動可能か検証する
  
  hoge = []
  for i in nextPosList:
    if i in PosList:
      #print u'すでに通りました'
      continue
    curFlg = getChar(i)
    if 'finish' == curFlg[0]:
      hoge =  PosList + [curFlg[1]]
      #print u'ゴールしました'
      if  hoge in global_res != True:
        global_res.append(hoge)
      break
    elif 'stop' == curFlg[0]:
      #print u'行き止まり'
      continue
    elif 'next' == curFlg[0]:
      hoge =  PosList + [curFlg[1]]
      #print u'次へ進む'
      printMaze(hoge)
      saikikun(hoge)
  return hoge
  
def printMaze(arr):
  global maze
  tmp_maze = [list(x) for x in maze]
  for i in arr:
    tmp_maze[i[0]][i[1]] = "$"
  hoge, hoge2 = [], []
  for i in tmp_maze:
    hoge.append("".join(i))

  print   "\n".join(hoge)

    
if __name__ == '__main__':
  maze = makeMazeArr(maze)
  dircDict = {'n':[-1,0], 'e':[0, 1], 's':[1, 0], 'w':[0, -1]}
  saikikun([[1,1]])    
  print global_res

よくわかんないけど、4方向のマス目とって移動可能な方向へすべて移動してみて、ゴールまでたどりつけるPathをArrにどんどん追加して最後に一番短いのだけ出せばいいじゃんと思ってかいたコード。

実行してみれば分かりますが全然終わりません。ほんとに終わらない。色々試してみて再帰が止まらないので、ステップ毎にどういう経路をたどっているのか表示してみたら、確かにこりゃ終わらなさそうな勢いで探しまくってた。（上記コードは1ステップ10msで表示していくやつ）1時間以上放置して1400万通りはやったけど全然終わらなさそう。っていうか、そんなにパターンあるのか？

アルゴリズム使うとどんだけ速くなるのかしらないけど、多分何倍も速いんだろうなぁと思う。時間があったら試そう。