PHP バックトラッキングアルゴリズムが n-queens 問題を解決する_PHP チュートリアル-PHPチュートリアル-php.cn

PHP バックトラッキングアルゴリズムが n-queens 問題を解決する_PHP チュートリアル

WBOY

リリース： 2016-07-13 10:42:23

オリジナル

1193 人が閲覧しました

バックトラッキングの基本的な方法は、検索、またはよく整理され、不必要な検索を回避できる徹底的な検索方法です。この方法は、非常に多くの組み合わせがある問題を解決するのに適しています。

バックトラッキング手法は、問題の解空間ツリーの深さ優先戦略に従い、ルートノードから開始して解空間ツリーを検索します。アルゴリズムが解空間ツリー内の任意の点を検索するとき、最初にノードに問題の解が含まれているかどうかを判断します。明らかに含まれていない場合は、そのノードをルートとしてサブツリーの検索をスキップし、その祖先ノードを層ごとに戻します。そうでない場合は、サブツリーに入り、深さ優先戦略に従って検索を続けます。

バックトラッキング手法の指導的イデオロギー - うまくいかない場合は引き返す。設計プロセス: 問題の解決空間を決定し、ノード検索の拡張ルールを決定します。

ここでは主にphpを使用してこの問題を解決する方法を示します

$tres は実現可能な試みを表します

$res は合計結果を記録します

詳細なデータ構造分析については、リンクを参照してください。

リーリーリーリー
// 他に説明すべきことがあります。PHP では最終的な時間の計算があまり厳密ではないため、直接減算することができず、重大なエラーが発生します。これは一時的なデモンストレーションにすぎません。正確な計算が必要な場合は、関連する関数を呼び出す必要があります。