C でルービック キューブを解くためのプログラムを開発しようとしています。これにはバック トラッキング手法を使用しました。これは非常に長いプロセスであり、多くの反復が必要なため、解決できません。
他の手法やバックトラッキング自体の採用など、これをより効率的に解決する方法について提案してください。Google では、これを解決するためのショートカットがたくさん見つかりましたが、ショートカットを使用してこれを解決したくありません。
36689 次
5 に答える
7
人間指向のソリューションを使用して、これをプログラムしてみませんか。
パターン マッチングが必要ですが、それほど難しくはありません。(1000x1000x1000 を解決するプログラムもあります)。
基本的な考え方は、段階的に作業することです。
- 最初の層
- 二層目
- 第三層
レイヤーごとに、パターン X をパターン X' に変換するいくつかのアルゴリズムを実装します。フェーズの各ステップは、キューブを解決に近づける必要があります。これを行うには、各パターンに値を追加します (より高い値が未解決のキューブに与えられます)。また、難易度 (ターン数など) を追加して、難易度ごとの最高のバリュー ゲインに基づいてアルゴリズムを選択することもできます (または、最小のターンで最高の結果に到達することもできます)。
このアプローチの面白さは、必要に応じて新しいアルゴリズムを追加し、それらがどのくらいの頻度で使用されるかをテストできることです。したがって、各アルゴリズムの有用性をテストできます。
これらのギークポイントを本当に獲得したい場合は、別の言語を作成して、アルゴリズムとアルゴリズムが解決するパターンを記述してください。
于 2011-04-06T08:55:25.983 に答える
4
ルービック問題を解くアルゴリズムはたくさんありますが、この最適なものを参照できます http://en.wikipedia.org/wiki/Optimal_solutions_for_Rubik's_Cube
于 2011-04-06T09:03:22.780 に答える
1
ルービック キューブの状態空間サイズは 2 65のオーダーです。状態空間をやみくもに検索するバックトラッキング アルゴリズムは、解を見つける前に状態空間の大部分を調べる必要がある場合があるため、単純なバックトラッキング アルゴリズムがうまく機能しないことは明らかです。しかし、この問題はすでに何度も解決されています。たとえば、http ://www.cs.princeton.edu/courses/archive/fall06/cos402/papers/korfrubik.pdf を参照してください。
于 2011-04-07T04:53:38.330 に答える
1
あなたの問題と、ショートカットの意味を理解しているかどうかはわかりません。ルービック キューブを解くために何らかの動的計画法を使用している場合は、解に到達するために十分なステップを先に見ていることを確認する必要があります。2 種類の移動 (右回転、上回転) のみをサポートする場合は、解決策を確実にするために、各移動を決定する前に 12 のステップ (確信はありません) を見る必要があると思います。
このようなことを行っていて、メモリのスペースが不足していることに気付いた場合は、適切なソリューションを決定するためにトラバースしているパスのみを保持する必要があることに注意してください (ツリー全体ではありません)。
Javaでルービックキューブを解決するためにこのアプローチをうまく使用したので、Cには問題がありません（メモリフットプリントに関する限り）。
于 2011-04-06T08:56:55.627 に答える
0
関係する移動の数を気にしない場合は、ブルートフォースメソッドが機能するように状態空間を分割する方法があります。
ダミーのためのルービックキューブソリューションを見つける
- 最初にすべてのルビックスファセットをブルートフォースしますが、コーナーを所定の場所に配置します
- 次に、不変なものをファセット化する動きを見つけます（例：（fgf-1.g-1）^ 3）。実際には2回の動きで十分です。それらを見つけるには、コーナーと非コーナーサブキューブに関連する順列を検討し、コーナーサイクルの長さのppcmを反復して、コーナーで不変になります）
- バックトラッキングアルゴリズムを使用して、コーナーを所定の位置に配置します（ただし、色を揃えるために回転が必要です）
- 一緒に回転する同じセグメント上で立方体になる魔法の動きを見つけます。その動きはありません
于 2011-04-17T13:54:41.563 に答える