問題タブ [hill-climbing]

次の問題は、人工知能コースで見つけた試験問題です。

「ヒルクライミング アルゴリズムを使用して、この問題を解決できるヒューリスティック メカニズムを提案してください。(S=開始点、F=最終点/ゴール)。斜めの移動は許可されません。」

マンハッタン距離またはユークリッド距離がロボットを (3,4) に送り、バックトラックが許可されないことは明らかなので、この問題に対する可能な解決策 (ヒューリスティック メカニズム) は何ですか?

編集: 問題をより明確にするために、ボード上のマンハッタン距離のいくつかをマークしました。

マンハッタン距離を使用すると、ヒューリスティック値が 2 であるため、ロボットの次の移動は (3,4) になることは明らかです。HC はそれを選択し、永遠に立ち往生します。目的は、適切なヒューリスティック アルゴリズムを見つけることによって、決してその道に進まないようにすることです。

私の機能では、次のものがあります。

私は自分のクラスインスタンスを繰り返し処理していませんが、それでも次のようになります:

山登りでランダムな 8 パズルを解くアルゴリズムを書こうとしています。最初の選択、最良の選択、およびランダムな再起動を使用して作成しましたが、常に無限ループに陥ります。それを防ぐ方法はありますか? また、ランダムなパズルを生成するときに、アルゴリズムを使用して、生成されたすべてのパズルが解けるようにしました。したがって、可解性の問題はありません。これは、ほぼ 100% のパズルで 8 つのパズルを解決するランダム リスタート タイプの関数です。

OptaPlanner を使用して、いくつかの計画の問題を解決しています。ドキュメントを読みましたが、Hill Climbing と Tabu Search のアルゴリズムがどのように機能するのかよくわかりません。私が確信していないのは：

• ヒル クライミング ピックは、現在のスコアよりも優れたベスト スコアのムーブのみを選択できますか?
• タブー検索では、現在のスコアよりも良いか等しいスコアのソリューションにつながる動きがない場合、現在のスコアよりも悪いスコアを持つ動きを選択できますか?

R で bnlearn パッケージを使用して、特定の結果を予測しています。ただし、データ セットのすべての行について、同じ予測が得られます。

トレーニング

予測

HC と MMHC の出力 (入力ごとに異なる予測)

GS の出力 (すべての行で同じ予測)

数独をランダム リスタート ヒル クライミングで解決するプログラムを (C# で) 作成し、オペレーターとして 2 つのフィールドの値を切り替える必要があります。数独の開始ソリューションでは、常に各フィールドに (1 から n n まで) の値が割り当てられます。ここで、n n の各長方形のサブグリッドには、それぞれの数字が 1 回だけ出現します。

今、私は2つの質問があります:

1. 山登りアルゴリズムで動作する数独の次の 2 つのフィールドを決定するにはどうすればよいですか?

2. ヒル クライミング アルゴリズムはいつ再起動しますか? ( / (ローカル) 最大値に達したことを確認する方法、現在のソリューションよりも優れたサクセサーはありませんか?)

誰かがこれについて私を助けることができれば、それは大歓迎です。

よろしくお願いします。

確率的な山登りアルゴリズムと第一選択の山登りアルゴリズムの違いは何ですか?

選択と突然変異のみを使用する (交叉なし) 遺伝的アルゴリズムを考えてみましょう。これは山登りアルゴリズムにどのように似ていますか?

記事でこのステートメントを見つけましたが、その理由がわかりませんか?

私は、これら 2 つのアルゴリズムの違いと、問題を解決する際の違いを理解しようとしています。私はアルゴリズムとそれらの内部を見てきました。すでにそれらを経験した他の人の話を聞くのは良いことです. 特に、同じ問題でどのように異なる動作をするかを知りたいです。

ありがとうございました。