問題解決の数理
放送大学教養学部　主任講師：大西 仁

第10章・第10回　問題の状態空間モデルと探索

概要

問題の解決の状態空間モデルと状態空間を含むグラフの探索法について解説する。問題解決は、状態空間を探索して初期状態からゴールへ至る系列を発見することと定式化することもできる。パズルやゲームなどを状態空間の探索により解くことは、人工知能の最初期からの研究課題であったが、1990年代にはチェスの世界チャンピオンに勝利するほど探索の技法は高度化した。探索技法はパズルやゲームに限らず、様々な問題解決のツールとして利用できる。
【キーワード】
状態空間モデル，系統的探索，ヒューリスティック探索

放送授業パタン，台本（字幕代りにどうぞ）

パタン
パタン	A4版背景なし
台本

このページのトップへ

Rによる深さ優先探索

プログラム

> source('DFS_1.R')
> G <- matrix(c(0,1,1,0,0,0,0,0,0,  0,0,0,1,1,0,0,0,0,  0,0,0,0,0,0,0,0,0,                      0,0,0,0,0,1,1,0,0,  0,0,0,0,0,0,0,0,0,  0,0,0,0,0,0,0,1,1,                      0,0,0,0,0,0,0,0,0,  0,0,0,0,0,0,0,0,0,  0,0,0,0,0,0,0,0,0), ncol=9, byrow=T)
> G
      [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9]
 [1,]    0    1    1    0    0    0    0    0    0
 [2,]    0    0    0    1    1    0    0    0    0
 [3,]    0    0    0    0    0    0    0    0    0
 [4,]    0    0    0    0    0    1    1    0    0
 [5,]    0    0    0    0    0    0    0    0    0
 [6,]    0    0    0    0    0    0    0    1    1
 [7,]    0    0    0    0    0    0    0    0    0
 [8,]    0    0    0    0    0    0    0    0    0
 [9,]    0    0    0    0    0    0    0    0    0
> g <- 5
> DFS(G, g, 1)
[1] "visit 1"
[1] "visit 2"
[1] "visit 4"
[1] "visit 6"
[1] "visit 8"
[1] "visit 9"
[1] "visit 7"
[1] "visit 5"
[1] "found 5"
>

このページのトップへ

Rによる幅優先探索

プログラム

> source('BFS_1.R')
> BFS(G, g, 1)
[1] "visit 1"
[1] "visit 2"
[1] "visit 3"
[1] "visit 4"
[1] "visit 5"
[1] "found 5"
> 

このページのトップへ

Rによる反復深化深さ優先探索

プログラム

> source('IDDFS.R')
> IDDFS(G, g, 1)
[1] "========limit=1========"
[1] "depth[1]=1"
[1] "visit 1"
[1] "========limit=2========"
[1] "depth[1]=1"
[1] "visit 1"
[1] "depth[2]=2"
[1] "visit 2"
[1] "depth[3]=2"
[1] "visit 3"
[1] "========limit=3========"
[1] "depth[1]=1"
[1] "visit 1"
[1] "depth[2]=2"
[1] "visit 2"
[1] "depth[4]=3"
[1] "visit 4"
[1] "depth[5]=3"
[1] "visit 5"
[1] "found 5"
>