Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
1
Help us understand the problem. What is going on with this article?
@arthur_maki

深さ優先探索と幅優先探索のアルゴリズムと使用用途と実装ポイント

More than 1 year has passed since last update.

概要

アルゴリズム界隈でよく見る深さ探索と幅優先探索のアルゴリズム、使用用途、実装ポイントの違いのメモです。実装に関してはコードを書こうかと思いましたが、解く問題に依存するためポイントのみ記載しました。

深さ優先探索(Depth First Search)

アルゴリズム

ある状態から始めて遷移できなくなったら一つ前の状態に戻って探索するアルゴリズム

使用用途

  • 全ての状態に対して操作をする場合や探索する場合
    計算量がDFSは$O(2^状態の遷移数)$であるが、BFSは$O(状態数×遷移の仕方)$となり状態数に依存する。これはBFSの方がメモリ使用量が多くなるためDFSを使用する。

実装ポイント

  • 状態の格納にスタックを使用する。
  • 一つ次の状態または前の状態に遷移し続けるため再帰関数で実装する。

幅優先探索(Breadth First Search)

アルゴリズム

ある状態から近い順に遷移させるアルゴリズム。具体的には「ある状態(sとする)から1回で遷移できる全ての状態(s+1となりうる全ての状態)に遷移する」を繰り返す。

使用用途

  • 全ての状態に対して操作をする場合や探索する場合
  • 最短経路で探索したい場合(例えば迷路問題)や最短手数を求めたい場合

実装ポイント

  • 状態の格納にキューを使用する。
    具体的には「現在の状態をキューに入れる→1回で遷移できる全ての状態をキューに入れる→どれか一つの状態を選択して遷移する」を実行し、キューから状態がなくなるまで繰り返すように実装する。
    この時、既に遷移した状態には遷移しないようにする。
  • ある状態から近い順に遷移してから次の状態に遷移するように実装する。
1
Help us understand the problem. What is going on with this article?
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away

Comments

No comments
Sign up for free and join this conversation.
Sign Up
If you already have a Qiita account Login
1
Help us understand the problem. What is going on with this article?