私はランダムな順序で35の数字（1〜35）を持つ6*6のパズルを持っています。空白のものを「レジスター」として使用し、番号を1つずつ移動して順番に並べます。私は3*3のパズルを扱うことができますが、6 * 6のパズルをどのように扱うのですか？ヒントを教えてください。
質問する
2222 次
5 に答える
7
考え方は同じで、問題を状態グラフとして表し、最短経路アルゴリズムを実行します。
アルゴリズムの効率が重要な場合は、情報に基づいたアルゴリズム（ A *アルゴリズムなど）が必要になる場合があります。これは、許容可能なヒューリスティック関数を備えた非常に高速であることが期待されます。
低速ですが単純なソリューションでBFS
を実行できます。
両方のアルゴリズム（A *、BFS）は、完全（存在する場合は常に解決策を見つける）と最適（最短経路を見つける）の両方です。
また、マクロを使用して「適切な」一連の動きを学習し、アルゴリズムを高速化できることにも注意してください。実用的な（ただし遅い）ソリューションを実装するまで、この改善を無視してください。
編集：コーディングガイドライン：
問題をグラフとして見てください：グラフはG=(V,E)どこにV = { all possible states}あり、E = { (u,v) | can move from state u to state v within a single step }
さて、このグラフでは、開始位置（入力として与えられるソース）とターゲット（ソートされたパズル）があります。BFSまたはA*を開始し（添付のウィキペディアのリンクでこれらの擬似コードを確認してください）、送信元から宛先へのパスを見つけます。BFSから始める必要があります-それはより簡単です。
最短経路アルゴリズムによって返される経路は、開始ボードからターゲットに到達するために実行する必要のある一連の移動と同じです。
注：実際のグラフを作成する必要はありません。必要なのは、開始ノード（ソース）を保持し、その頂点を作成し、successors:V->2^V各頂点のサクセサを提供する関数（正式には:)を使用することだけですsuccessors(v) = { (v,u) | (v,u) is in E }。このようにして、グラフの関連部分をその場で作成できます。
于 2012-06-20T15:34:03.953 に答える
1
私は大学時代にこれと同じ問題/パズルを研究しましたが、AIとヒューリスティック手法、グラフ理論を含む非常に興味深い問題です。amitが述べているように、A *、BFS、およびヒューリスティックを確認することを強くお勧めします。
これが私の貢献です：これを解決しようとするとき、あなたは戦略を征服するために分割を試みることができます。この6x6グリッドは、互いに接近して結合された4つの3x3グリッドであると考えることができ、特定の順序で別々のケースとしてそれぞれを解決しようとします。
たとえば、次のアルゴリズムを試すことができます。
- 左上のグリッドに、1つ（作業スペースとして使用される）を除くすべてのピースが含まれるようにピースを配置します。
- 左上のグリッドを解きます。
- 右上のグリッドを、右下のグリッド（作業スペースとして使用される）を除いて、すべてのピースが含まれるように配置します。
- 右上のグリッドを解きます。
- ...など、グリッドの数に関係なく！
最後の問題は、右上のグリッドの右上隅を作業スペースの「欠けている部分」にすることはできないため、作業スペースとして残すコーナーに注意を払う必要があるということです。将来そこに作品を置くことが可能です。
Ps1：作業スペースは、ピースを操作するための空きスペースを確保するために、ピースを一時的に見逃した位置です。
Ps2：このコンテキストでは、グリッドはNxNピースの組み合わせであり、必ずしも順番に並んでいるとは限らない、すべての正しいピースが含まれています。
私が何らかの形で助けてくれたことを願っています。:-)
于 2012-06-20T16:06:06.323 に答える
0
このゲームの簡単な戦略は、正しい数字を一番上の行に配置することです（他の数字は気にしないので簡単ですが、最後の2つの数字は、配置する必要があるため、正しい場所に配置するのが少し難しくなります両方とも同じ動きで）、次に上の行をフリーズし、左の列、次に上の行、次に左の列に進みます…</ p>
これは最適な戦略ではありませんが、機能し、コーディングが簡単な戦略です。
于 2012-06-20T15:54:43.750 に答える
0
6 * 6マトリックス全体をトラバースすると、一度に1つの小さな数しか見つけられず、関連するソリューションではない次のマトリックスに移動できると思います。この問題を解決するためのより良い方法は、与えられた行列で二分探索を使用することです。二分探索を適用すると、時間計算量が高くなります。したがって、この問題を解決するためのより良い方法は何ですか。
于 2015-04-01T09:13:10.497 に答える
0
Inserting Sortアルゴリズムを使用して、上記のパズルを解きました。上記のパズルを解くのに2日近くかかりました。何か質問が必要な場合は、.Netコードの下で実行してから、メッセージを送ってください。上記の問題を解決するためにC＃の組み込みクラスを使用したことはありません。これは、コードを使用した純粋なcロジックコードソリューションです。
private static void MazePuzzle()
{
/****
* A typical C Problem for Maze puzzle has been solved by prince.It took almost 3 days.
* Problem is about Sorting a 2D Matrix with any number of row and column
* This problem is also known as Rat Maze puzzle
* It is also be a typical Backtracking Problem
* ***/
const int _row = 6;
const int _coloumn = 6;
//int _column1 = _coloumn;
int[,] _doubleArray = new int[_row, _coloumn] { { 19, 2, 4, 34, 23, 41 }, { 11, 63, 3, 93, 65, 98 }, { 12, 80, 15, 76, 71, 90 }, { 119, 32, 94, 84, 23, 41 }, { 129, 232, 124, 341, 253, 411 }, { 197, 289, 47, 343, 293, 401 } };
int [] _StoringArray1D=new int[_row*_coloumn];
int i = 0;
int j = 0;
int _comparingArrayElement = 0;
int _swipeTemp = 0;
for (; i < _row; i++)
{
int _trackrow = 0;
for (;j <_coloumn; j++)
{
_trackrow = 0;
if(i==0 && j==0)
{
_comparingArrayElement= _doubleArray[i, j + 1];
if(_comparingArrayElement<_doubleArray[i,j])
{
_swipeTemp = _doubleArray[i,j+1];
_doubleArray[i, j + 1] = _doubleArray[i, j];
_doubleArray[i, j] = _swipeTemp;
}//innerMost if
}//For First time
else
{
int k = 0;
do
{
if (_trackrow == i || _trackrow < i)
{
for (; k < _coloumn; k++)
{
if(k==j && i==_trackrow)
{
break;
}
else
{
if(_doubleArray[_trackrow,k]>_doubleArray[i,j])
{
int _swipetempPrevious=_doubleArray[_trackrow,k];
_doubleArray[_trackrow,k]=_doubleArray[i,j];
_doubleArray[i, j] = _swipetempPrevious;
}
else
{
//do nothing just traverse
}//swipe else
}//k==j else
}//inner for do while
_trackrow++;
k = 0;
}//trackrow if
else
{
break;
}//trackrow else
} while (true);
}//else
}//innner for
j = 0;
}//outer for
Console.WriteLine("End of Program");
}//Maze Puzzle Method
于 2015-04-03T07:03:52.300 に答える