ヒューリスティック関数とも探索手法とも直行した探索改善手法
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/01/16 01:19 UTC 版)
「自動計画」の記事における「ヒューリスティック関数とも探索手法とも直行した探索改善手法」の解説
2008年の "How Good is Almost Perfect?." (AAAI08 Best Paper) という論文によって、ヒューリスティック関数をどれだけ改善しても、完璧なヒューリスティック(緩和を行わない=計算するのにもとの問題を解くのと同じだけの計算量がかかるので非実用的)を得ない限り究極的には指数爆発が避けられないケースがあることが示された。以来、上記２つとは独立した探索手法の改善、ないし枝刈り手法が求められている。 このうち代表的な手法に、対称性検知(symmetry breaking)、行き止まり検知(dead-end detection)、Dominance Pruning、Partial Order Pruningなどがある。対称性検知は、探索グラフのうちisomorphicな部分グラフを検知して、その一つを残してすべて枝刈りする。行き止まり検知は、現在のノードからはゴールにたどり着けないことを、実際にゴールを探索し尽くすことなく検知する。Dominance Pruningは、「あるノードが別のノードよりも悪い」ことを、ヒューリスティクス関数/下界関数による分枝限定法とは別の仕組みで検知する。Partial Order Pruningは、順序を入れ替えただけのアクションの列のうち、一つを残して枝刈りする。
※この「ヒューリスティック関数とも探索手法とも直行した探索改善手法」の解説は、「自動計画」の解説の一部です。
「ヒューリスティック関数とも探索手法とも直行した探索改善手法」を含む「自動計画」の記事については、「自動計画」の概要を参照ください。
- ヒューリスティック関数とも探索手法とも直行した探索改善手法のページへのリンク
