バックトラック法、及び再帰関数の仕組みを理解したい。(迷路問題を解く)

前提・実現したいこと

プログラミングの学習課題で再帰関数とバックトラック法を学ぶために簡単な迷路問題のコードを読んでいます。
ソースコードはすでに出来上がったものでちゃんとゴールまでのルートを表示してくれます。
しかし、「バックトラックしたあとに一度訪問したノードにまた進んでしまわないのか？」という疑問が生まれ、なかなかスッキリと解消できる説明が思い浮かびません。学習はじめたばかりの初歩の初歩的な質問で恐縮ですが、どなたか解説いただけると幸いです。
もし言葉足らずだったり、不足している情報があったらご指摘ください。

発生している問題・エラーメッセージ

エラーメッセージ

該当のソースコード

ソースコード

#迷路
maze=
　　　　　　　　　　[[".",".",".","."]
     ,[".","x","x","x"]
     ,[".",".",".","x"]
     ,["x","x",".","."]]
#迷路を表示
def print_maze(maze):
  for raw in maze:
    raw_print=""
    for value in raw:
      raw_print+= value + ""
    print (raw_print)
#本題の迷路を解く関数（再帰関数とバックトラック）
def solve_maze_helper(maze,sol,pos_row,pos_col):
  num_row=len(maze)
  num_col=len(maze[0])

  #Base Case
  if pos_row==num_row-1 and pos_col==num_col-1:
    return sol
  if pos_row>=num_row or pos_col>=num_col:
    return None 
  if maze[pos_row][pos_col]=='x':
    return None
  #Recursive Case
  #右に進む
  sol.append("r")
  sol_going_right=solve_maze_helper(maze,sol,pos_row,pos_col+1)
  if sol_going_right is not None:
    return sol_going_right
  #右にいけない＞バックトラック＞下に進む
  sol.pop()
  sol.append("d")
  sol_going_down=solve_maze_helper(maze,sol,pos_row+1,pos_col)
  if sol_going_down is not None:
    return sol_going_down
  #解なし＞バックトラック
  sol.pop()
  return None

試したこと

ここに問題に対して試したことを記載してください。

補足情報（FW/ツールのバージョンなど）

ここにより詳細な情報を記載してください。

tiitoi

2021/12/10 11:05

質問を編集して、コードは markdown 記法で ```コード``` というように囲ってください。

YasuhiroHorii

2021/12/10 12:30

失礼しました。チュートリアルを良く見ずに投稿してしまっていました。ご指摘感謝です。

行動規範の内容に同意します

回答2件

ベストアンサー

どこまで理解されているのかよくわからないので、さわりだけ。

この迷路は、とある場所に居るときに、次の行動が右と下にしか行かないルールです。これは、以下の2つしか迷路を進む手順が定義されていないことからわかります。

text
1  sol.append("r")
2  sol.append("d")

ということは、

「バックトラックしたあとに一度訪問したノードにまた進んでしまわないのか？」

については、「戻らないのだからそんなことは起きない」ということです。

また、「バックトラックは戻るのでは」という認識かもしれませんが、そうではありません。
「右に行ってみて、その先に解がなければ、右に行かない」がバックトラックです。その部分を解説するとこうです

python
1  sol.append("r")    #右に行くことにする。
2  sol_going_right=solve_maze_helper(maze,sol,pos_row,pos_col+1) 右に行ってみる
3  if sol_going_right is not None:  # 右に行って答えがあれば、
4    return sol_going_right     # それが答え
5  #右にいけない＞バックトラック＞下に進む  
6  sol.pop()   # 右に行って答が無ければ右にいくのをやめる

バックトラックの説明で「引き換えす」というような説明をするし、ある意味そうなのですが、単に引き返すわけではなく、その「枝」を捨てるようにするのがポイントです。

少しは役に経つでしょうか。

投稿2021/12/10 15:14

TakaiY

総合スコア12761

YasuhiroHorii

2021/12/12 15:56 編集

回答ありがとうございます。バックトラック＝「戻る」というイメージが確かに根強くありました。ポイントは戻ることよりも、無駄な選択肢をどんどん減らしていくことにある、、一言で言えば消去法みたいなものでしょうか。答えがない＞バックトラック　のときに、sol.pop() return None でその試行は除けられていくという理解であってますでしょうか。