PHP バックトラッキング アルゴリズムが n-queens 問題を解決する_PHP チュートリアル
- WBOYオリジナル
- 2016-07-13 10:42:231193ブラウズ
バックトラッキングの基本的な方法は、検索、またはよく整理され、不必要な検索を回避できる徹底的な検索方法です。この方法は、非常に多くの組み合わせがある問題を解決するのに適しています。
バックトラッキング手法は、問題の解空間ツリーの深さ優先戦略に従い、ルート ノードから開始して解空間ツリーを検索します。アルゴリズムが解空間ツリー内の任意の点を検索するとき、最初にノードに問題の解が含まれているかどうかを判断します。明らかに含まれていない場合は、そのノードをルートとしてサブツリーの検索をスキップし、その祖先ノードを層ごとに戻します。そうでない場合は、サブツリーに入り、深さ優先戦略に従って検索を続けます。
バックトラッキング手法の指導的イデオロギー - うまくいかない場合は引き返す。設計プロセス: 問題の解決空間を決定し、ノード検索の拡張ルールを決定します。
ここでは主にphpを使用してこの問題を解決する方法を示します
$tres は実現可能な試みを表します
$res は合計結果を記録します
詳細なデータ構造分析については、リンクを参照してください。
リーリー リーリー
// 他に説明すべきことがあります。PHP では最終的な時間の計算があまり厳密ではないため、直接減算することができず、重大なエラーが発生します。これは一時的なデモンストレーションにすぎません。正確な計算が必要な場合は、関連する関数を呼び出す必要があります。
声明：
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。