Search Nodes Selection 評価

0 200 400 600 800 1,000 1,200

Time

（秒）

（秒）

（秒）

（秒）

バイナリバイナリ バイナリバイナリDAG

PE = 2（機能OFF）

PE = 2（機能ON）

0.0<complexity<=0.25

0.25<complexity<=0.5

0.5<complexity<=0.75

0.75<complexity<=1.0

図5.13 Search Nodes Selectionにおける探索解発見率（PE=2）

図5.13では，手法を有効にした場合も無効にした場合もどちらも短時間で解を得られてい ることから，ほとんど差は見られない．

このことから，P E = 2においては，機能ONと機能OFFのどちらにおいても提案手法が 問題なく機能していることが分かった．

なお，機能OFFと機能ONの結果が重なっているため，図の表示がされていないことに注 意されたい．

0 200 400 600 800 1,000 1,200

Time

（秒）

（秒）

（秒）

（秒）

バイナリ バイナリ バイナリ バイナリDAG PE = 4（機能OFF）

PE = 4（機能ON）

0.0<complexity<=0.25

0.25<complexity<=0.5

0.5<complexity<=0.75

0.75<complexity<=1.0

図5.14 Search Nodes Selectionにおける探索解発見率（PE=4）

図5.14のP E = 4での評価では，DAGの28%で探索時間が改善し，11%で探索時間が悪 化するという結果が得られた．探索時間が悪化したケースについては，Search Node Selection によって探索対象ノードが選定されることで，探索パターンの実行順序が変更し，結果的に時 間が増大したと考えられる．

complexityが0.75以下では，探索時間が大きく改善した例が多く確認できるが，complexity が0.75から1.00ではそれほど多くの改善は見られない．これは，complexity が大きくなる ほどDAGが複雑になり，探索不要ノードが減るためだと考えられる．

0 200 400 600 800 1,000 1,200

Time

（秒）

（秒）

（秒）

（秒）

バイナリ バイナリ バイナリ バイナリDAG

PE = 6（機能OFF） PE = 6（機能ON）

0.0<complexity<=0.25

0.25<complexity<=0.5

0.5<complexity<=0.75

0.75<complexity<=1.0

図5.15 Search Nodes Selectionにおける探索解発見率（PE=6）

P E = 6の評価では，DAGの35%で探索時間が改善し，2%で探索時間が悪化するという 結果が得られた．P E = 4での評価と同様に，complexityが0.5以下のDAGにおいて，探索 時間が大きく改善した例が多く確認できる．これは，complexityが低いほどDAGがシンプ ルになり，より多くの探索不要ノードが発見されるためであると考えられる．

0 200 400 600 800 1,000 1,200

Time

（秒）

（秒）

（秒）

（秒）

バイナリ バイナリ バイナリ バイナリDAG

PE = 8（機能OFF） PE = 8（機能ON） 0.0<complexity<=0.25

0.25<complexity<=0.5

0.5<complexity<=0.75

0.75<complexity<=1.0

図5.16 Search Nodes Selectionにおける探索解発見率（PE=8）

P E = 8の評価では，DAGの37%で探索時間が改善し，7%で探索時間が悪化するという 結果が得られた．また，PE値が増大するにつれて探索空間が増大することから，complexity が0.25以下の場合にも探索に時間のかかるものが増え，Search Node Selectionの効果が出 てきている．逆に，complexityが0.75以上の場合では，そもそも探索時間が長いことから，

Search Node Selectionで探索対象ノードを削減した場合でも1200秒以内に解を発見できな いケースが増えた．

0 200 400 600 800 1,000 1,200

Time

（秒）

（秒）

（秒）

（秒）

バイナリ バイナリ バイナリ バイナリDAG

PE = 10（機能OFF）

PE = 10（機能ON）

0.0<complexity<=0.25

0.25<complexity<=0.5

0.5<complexity<=0.75

0.75<complexity<=1.0

図5.17 Search Nodes Selectionにおける探索解発見率（PE=10）

P E = 10の評価では，DAGの35%で探索時間が改善し，7%で探索時間が悪化するとい う結果が得られた．これは，P E = 8での評価とほぼ同じである．探索時間の改善率について も，P E = 6以降では35%程度で推移している．

以上の全ての結果より，計算時間が悪化したケースについては，枝刈りにより探索パター ンの生成順序が変更され，計算時間が長くなったものと考えられる．機能の特徴としては，

complexityの低いものは機能の有無にかかわらず，計算時間が短く，complexityの高いもの

は，機能が有効なサンプル数は少なくなるが，有効なサンプルについては時間短縮が見られる．

中間のcomplexityのものは，多くのケースで機能が有効に働き，大幅な時間短縮に繋がった．

以上の結果から，Search Nodes Selectionの手法を導入することで，マッピング探索解をよ り早く発見できることが判明した．