質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
86.12%
アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

再帰

情報工学における再帰とは、プログラムのあるメソッドの処理上で自身のメソッドが再び呼び出されている処理の事をいいます。

Python

Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。

解決済

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

YasuhiroHorii
YasuhiroHorii

総合スコア11

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

再帰

情報工学における再帰とは、プログラムのあるメソッドの処理上で自身のメソッドが再び呼び出されている処理の事をいいます。

Python

Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。

2回答

0リアクション

0クリップ

837閲覧

投稿2021/12/10 07:55

編集2021/12/10 12:28

前提・実現したいこと

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

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

エラーメッセージ

該当のソースコード

ソースコード
#迷路 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/ツールのバージョンなど)

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

以下のような質問にはリアクションをつけましょう

  • 質問内容が明確
  • 自分も答えを知りたい
  • 質問者以外のユーザにも役立つ

リアクションが多い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

気になる質問をクリップする

クリップした質問は、後からいつでもマイページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

下記のような質問は推奨されていません。

  • 間違っている
  • 質問になっていない投稿
  • スパムや攻撃的な表現を用いた投稿

適切な質問に修正を依頼しましょう。

tiitoi

2021/12/10 11:05

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

2021/12/10 12:30

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

まだ回答がついていません

会員登録して回答してみよう

アカウントをお持ちの方は

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
86.12%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問

同じタグがついた質問を見る

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

再帰

情報工学における再帰とは、プログラムのあるメソッドの処理上で自身のメソッドが再び呼び出されている処理の事をいいます。

Python

Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。