0

だから私は 8puzzle と目標状態である配列の初期状態を持っています

int[] myPuzzle   = {1,3,4,
                    0,2,5,
                    8,6,7}

int[] goalPuzzle = {2,1,0,
                    3,4,5,
                    8,7,6};

斜めに行かずに、初期状態と目標状態の間の距離を把握しようとしています。誰でも私を助けることができますか？(注: この配列を 2 次元配列に変更してもかまいません。これにより物事が単純になり、すべての距離を知りたいだけです)。

私がオンラインで見るところはどこでも、昇順の goalPuzzle 状態を期待しています。これは私の問題には当てはまりません。

4

1 に答える 1

1

これらの配列は、8 パズルの状態を表しています。このようなパズルのソルバーを実装する 1 つの方法は、最短経路検索に要約されます (詳細については、A-Star または Dijkstra のアルゴリズムを使用して 15 パズルをどのように解決しますか?を参照してください)。特にA* アルゴリズムの場合は、許容できるヒューリスティックが必要になります。この場合、現在の配列内のタイルの位置とゴール状態のタイルの位置の間のタクシーまたはマンハッタン距離の合計によって与えられます。 . このヒューリスティックが使用されるのは、必要な実際の移動数の下限を定義するためです。コメントで述べたように: 実際の移動数は少なくとも、タイル間の純粋な幾何学的 (マンハッタン) 距離と同じ大きさにする必要があります。

これを実装することはそれほど難しくありません。正確な実装は、ボードの状態の表現によって異なります。これには 2D 配列を使用することもできます。しかし、1D 配列の使用には優れた利点があります。タイル位置間の対応を見つけるのは簡単です。

一般に、現在の状態vの位置で特定の値を見つけた場合、この値が目標状態で持つ位置を検索して、2 つの間の距離を計算できるようにする必要があります。(sx,sy)(gx,gy)

しかし、配列には 0 から までの数値しか含まれていないarray.length-1ため、目標状態の「逆数」を計算し、これを使用して配列内の値の位置 (インデックス) を直接調べることができます。

コメントのリクエストに従って、追加された例と詳細:

たとえば、6位置 に表示されるパズルの値を考えてみましょう(1,2)。6ここで、目標状態にある位置を見つける必要があります。あなたの例では、これは(2,2)、または indexです。8この位置6は、目標状態配列の値を検索することで見つけることができます。しかし、これを各値に対して行うと、これはO(n*n)非効率になります。このinvertメソッドは、指定された目標状態に対して を返し[2,1,0,3,4,5,8,7,6]ます。この配列の要素は、元の配列での値iの位置です。たとえば、インデックス(探している値) でこの配列にアクセスすると、値が見つかります。そして、これはまさにその値のインデックスです i6886ゴール配列にありました。したがって、ゴール配列内の特定の値のインデックスを見つけることは、単純なルックアップで行うことができます (つまり、配列全体を検索する必要はありません)。

1D 配列のインデックスとボードのサイズから(x,y)座標を計算し、それを使用して距離を計算します。

次に例を示します。

public class TaxicabPuzzle
{
    public static void main(String[] args)
    {
        int[] myPuzzle = {
            1,3,4,
            0,2,5,
            8,6,7
        };

        int[] goalPuzzle = {
            2,1,0,
            3,4,5,
            8,7,6
        };

        int distanceBound = computeDistanceBound(myPuzzle, goalPuzzle, 3);
        System.out.println("Distance bound: "+distanceBound);
    }

    private static int computeDistanceBound(
        int state[], int goal[], int sizeX)
    {
        int inverseGoal[] = invert(goal);
        int distance = 0;
        for (int i=0; i<state.length; i++)
        {
            int goalIndex = inverseGoal[state[i]];
            distance += distance(i, goalIndex, sizeX);
        }
        return distance;
    }

    // For two indices in an array that represents a 2D array in row-major
    // order, compute the manhattan distance between the positions that are
    // defined by these indices
    private static int distance(int index0, int index1, int sizeX)
    {
        int x0 = index0 % sizeX;
        int y0 = index0 / sizeX;
        int x1 = index1 % sizeX;
        int y1 = index1 / sizeX;
        return Math.abs(x1 - x0) + Math.abs(y1 - y0);
    }

    // Given an array containing the values 0...array.length-1, this
    // method returns an array that contains at index 'i' the index
    // that 'i' had in the given array
    private static int[] invert(int array[])
    {
        int result[] = array.clone();
        for (int i=0; i<array.length; i++)
        {
            result[array[i]] = i;
        }
        return result;
    }
}
于 2016-10-02T04:10:25.687 に答える