機械学習の基礎知識まとめ アルゴリズム 探索木 幅優先探索(breadth first search)

はじめに

---

2015年も後半になって、ようやく重い腰をあげて機械学習の本を読み始めました。

人工知能は人間を超えるか ディープラーニングの先にあるもの (角川EPUB選書)

posted with ヨメレバ

松尾 豊 KADOKAWA/中経出版 2015-03-11

Amazon

Kindle

しかし、色々と基礎知識が欠落していて内容を理解するのに苦労しています。
というわけで、ブログに学習したことを記載していきたいと思います。
プログラマー目線で記載しているので、プログラマーでこれから機械学習を勉強しようと思っている人の役に立てばいいなと思って記事を書きました。
数年後には、エンジニアにある程度求められる能力になる可能性が高いので、何もわからない人はちょっとずつ準備しといたほうがよいと思います。
今回はアルゴリズム「幅優先探索(breadth first search)」の記事です。

環境

---

• ruby

難易度

---

• 簡単

利用シーン

---

• 迷路

幅優先探索(breadth first search)とは

---

木やグラフを探索するためのアルゴリズムです。
根ノードから探索し、隣接した全てのノードを探索していきます。

キューを利用したアルゴリズムです。

サンプル

---

木の探索の実装

wikipediaに掲載されているツリー状の探索を、rubyでプログラム化してみましょう。

image from wikipedia

木のnode(図の○の部分)の番号は探索順になります。

プログラムの作成

---

上記の式をプログラムに落とし込みます。

最初にnode(図の○の部分)をクラス化します。

# encoding: utf-8
class Node

  def initialize(name)
    @name = name
    @visited = false
    @childrenNode = []
  end
  
  # 子ノードの設定
  def setChildren(children)
    @childrenNode = children
  end

  def setVisited(status)
    @visited = status
  end
  
  def visited
    return @visited
  end
  
  def name
    return @name
  end
  
  def childrenNode
    return @childrenNode
  end

end

次に図の木の構成をプログラム化します。

# ノードの作成
node1 = Node.new('1')
node2 = Node.new('2')
node3 = Node.new('3')
node4 = Node.new('4')
node5 = Node.new('5')
node6 = Node.new('6')
node7 = Node.new('7')
node8 = Node.new('8')
node9 = Node.new('9')
node10 = Node.new('10')
node11 = Node.new('11')
node12 = Node.new('12')


# ノードの子ノードの設定
node1.setChildren([node2, node3, node4])
node2.setChildren([node5, node6])
node4.setChildren([node7, node8])
node5.setChildren([node9, node10])
node7.setChildren([node11, node12])

最後に幅優先探索を実装します。

# encoding: utf-8
class BreadthFirstSearch

  def initialize
    @queue = []
  end
  
  def search(node)
    # 訪問済みにチェック
    node.setVisited(true)
    # キューに追加
    @queue.push(node)
    # キューが空白でない
    while !@queue.empty? do
      # キューから取り出す
      queue_node = @queue.shift
      # キューの名称
      puts queue_node.name
      # 子供を取り出す
      childrenNode = queue_node.childrenNode
      unless childrenNode.empty?
        childrenNode.each { |tempNode|
          # 未訪問
          unless tempNode.visited
            # 訪問済みにチェック
            tempNode.setVisited(true)
            # キューに追加
            @queue.push(tempNode)
          end
        }
      end
    end
    
  end

end

プログラムの実行と結果

---

上記のプログラムを実行します。

breadthFirstSearch = BreadthFirstSearch.new
breadthFirstSearch.search(node1)

結果です。

1
2
3
4
5
6
7
8
9
10
11
12

図の探索順通りに出力されていますね。

まとめ

---

幅優先探索は有名なアルゴリズムなので、機械学習の学習をしていなくても、プログラマーであれば押さえておくべきです。実装もシンプルで簡単です。
また、プログラムコンテスト等でもよく出題されるので、過去問などをあさって、どんなケースで利用されているのかを知っておくと良いでしょう。

以上

参考サイト

• 幅優先探索

この記事がお役にたちましたらシェアをお願いします

Tweet