Russell と Norvig で与えられたアルゴリズムと計算の理解が正しいかどうかを確認したかっただけです。
宣教師と人食い人種を問題として使用して、時間と空間の複雑さをテストしています。深さの計算はそれほど大したことではありません。私はいつも深さ 11 で解を見つけます。頭を包み込めないのは、分岐要因です。
Russell と Norvig の 82 ページには、次のように書かれています。
「
O(b^(d-1))
探索セットにはO(b^d)
ノードがあり、フロンティアにはノードがあります...」
私のプログラムは8502
、探索されたセット内の14006
ノードとフロンティア内のノードを表示します。
私の思考プロセスは次のとおりですd
。Russell と Norvig に従ってノードの数とルートを取得すると、分岐係数が何であるかを取得する必要があります。今、自分の考えが正しいかどうかわかりません。私はちょうどそれを思いつきました。
したがって、 の 10 乗根 (d-1)を取って (およそ) を8502
取得2.47
し、 の 11 乗根 (d) を取って(およそ)14006
を取得し2.39
ます。したがって、私の結論は、分岐係数 b はおおよそ2.43
.
私はまったく的を射ていますか、それとも完全に間違っていますか? これは、私が今羽ばたいているものの1つです。しかし、私が間違っているか正しいかを知りたいです。