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

はじめに

---

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

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

posted with ヨメレバ

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

Amazon

Kindle

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

環境

---

• ruby

難易度

---

• とても簡単

利用シーン

---

• 迷路

深さ優先探索(depth-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, node7, node8])
node2.setChildren([node3, node6])
node3.setChildren([node4, node5])
node8.setChildren([node9, node12])
node9.setChildren([node10, node11])

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

# encoding: utf-8
class DepthFirstSearch
  
  def search(node) 
    # 訪問したノード名を出力
    puts node.name
    # 訪問済みにチェック
    node.setVisited(true)
    # 子ノードを取得
    childrenNodes = node.childrenNode
    unless childrenNodes.empty?
      childrenNodes.each { |tempNode|
        # 未訪問
        unless tempNode.visited
          search(tempNode)
        end
      }
    end
    
  end

end

プログラムの実行と結果

---

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

depthFirstSearch = DepthFirstSearch.new
depthFirstSearch.search(node1)

結果です。

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

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

まとめ

---

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

以上

まとめ

---

• 深さ優先探索

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

Tweet