このwikiページで問題を見つけたと思います：
`だと思います
高々ε倍のコストを持つ
加重 A* アルゴリズム部分では、
コストが ε 倍未満である
代わりは。
ここでは ε > 1 を想定しているためです。しかし、私にはよくわかりません。これについて誰かの意見を聞きたいだけです..
事前にご協力いただきありがとうございます:)
2958 次
1 に答える
2
「Weighted A*.If ha(n) is」で始まる段落は正しいと思います。見つかったパスのコストが最大で eta 倍の最適なパスのコストであるという保証は、あなたが望む保証のようなものです。最小コストのパスを探して、CPU 時間を削減しようとしている 最適ではない (コストが高い) ソリューションに落ち着いていますが、コストがそれほど悪くないという保証を得ています。
この段落と上の段落の eta の使用には矛盾があると思います - それが間違いなのか、それとも加重 A* とそれ以上の慣習の不幸な違いから派生したものなのかはわかりません。近似解の一般的な定義。
このパラグラフは、 http://inst.eecs.berkeley.edu/~cs188/sp11/slides/SP11%20cs188%20lecture%204%20--%20CSPs%206PP.pdfの注記と一致しています。 pdfと大まかな証明付き。重み付けされた A* が、コスト g(x) の解があると判断した場合、まだプレイ中のすべてのノードは、少なくともこれ以上の予測コスト g(y) + eh(y) を持つ必要があります。考えられる最大の誤差を得るには、g(y) がゼロであり、正しい解 y に対して eh(y) = g(x) と仮定すると、A* が見つけたと考えている解は y の e 倍の費用がかかることがわかります。元の h() は許容可能であり、したがってコストの上限であると仮定します。
于 2013-10-12T04:35:54.997 に答える