4

アルゴリズムで過去4日間立ち往生しています。私は Mahjong Safari タイプのゲーム ( http://www.pogo.com/games/mahjongsafari ) に取り組んでおり、タイルの数が最も少ない 2 つのタイル間のパスを開発したいと考えています。

Manhattan Hueristic で A* アルゴリズムを既に適用しましたが、それはターン数の多い最短パスを生成します。最短経路は必要ありません。最小ターン (できれば 2) の経路が必要なだけです。以下は、2 つのタイルの間にパスを生成する Mahjong Safari ゲームの画像です。A から B へのパスと B から A へのパスが異なることがわかります。

ここに画像の説明を入力

コード、アルゴリズム名、または機能すると思われるロジックで、私を助けてください。

編集:私がこれに適用したソリューション:

最初に本物の A* アルゴリズムを使用して最短経路を見つけ、マンハッタン距離をヒューリスティックな目標推定値として使用しました。パスをよりまっすぐにし、ターン数が最も少ないパスを選択するために、各反復で次の戦術を使用しました。

Tile first = currentNode.parent;
Tile curr  = currentNode;
Tile last  = successorOfCurrentNode;
if (first != null)
{
    if ((first.X == curr.X && first.Y != curr.Y) && (curr.Y == last.Y && curr.X != last.X))
    {
        // We got turn
    currentNode.Cost += 10;
    currentNode.calcuateTotalCost();

        successorOfCurrentNode.Cost += 5;
    successorOfCurrentNode.calcuateTotalCost();
    }
    else if ((first.X != curr.X && first.Y == curr.Y) && (curr.X == last.X && curr.Y != last.Y))
    {
        // We got turn
    currentNode.Cost += 10;
    currentNode.calcuateTotalCost();

        successorOfCurrentNode.Cost += 5;
    successorOfCurrentNode.calcuateTotalCost();
    }

}

4

3 に答える 3

0

ダイクストラの最短経路アルゴリズムを使用することもできますが、すべてのノードで最短経路だけでなく、その経路の方向も保存する必要があるため、カウントを増やす必要があるかどうかがわかります。

もう少し考えてみると、最適なパスを選択するには、すべてのノードの方向とともにすべての最短パスを保存する必要があると思います。

于 2013-03-12T12:33:13.277 に答える
0

私がこれに適用したソリューション：

最初に本物の A* アルゴリズムを使用して最短経路を見つけ、マンハッタン距離をヒューリスティックな目標推定値として使用しました。パスをよりまっすぐにし、ターン数が最も少ないパスを選択するために、各反復で次の戦術を使用しました。

enter code here

Tile first = currentNode.parent;
Tile curr  = currentNode;
Tile last  = successorOfCurrentNode;
if (first != null)
{
    if ((first.X == curr.X && first.Y != curr.Y) && (curr.Y == last.Y && curr.X != last.X))
    {
        // We got turn
        currentNode.Cost += 10;
        currentNode.calcuateTotalCost();

        successorOfCurrentNode.Cost += 5;
        successorOfCurrentNode.calcuateTotalCost();
    }
    else if ((first.X != curr.X && first.Y == curr.Y) && (curr.X == last.X && curr.Y != last.Y))
    {
        // We got turn
        currentNode.Cost += 10;
        currentNode.calcuateTotalCost();

        successorOfCurrentNode.Cost += 5;
        successorOfCurrentNode.calcuateTotalCost();
    }

}
于 2013-03-14T10:04:12.330 に答える
0

期待は必要ないため、問題はヒューリスティックを使用するよりも単純ですが、検索が「完全」ではない場合に最適なものを見つける速度を向上させることができます..むしろ、最小限のターンでパスが必要なだけです。したがって、貪欲な検索を使用できます。

h(A) > h(B) ~ turns(A) < turns(B)

h* = MIN(turns(x))

h(x): heuristic of path X

turns(x): number of turns in path X

h*: highest possible heuristic, path with minimum number of turns

Java の簡単なコードを次に示します。

class TileGame
{
    // example of a game board
    int [][] matrix = new int [10][10];

    // return possible next-state
    public ArrayList<Path> next (Path p)
    {
        // based on your rules, you decide valid transitions
        ArrayList<Path> n = new ArrayList<Path>();
        ArrayList<Point> t = new ArrayList<Point>();

        // add up, down, right, and left
        t.add(new Point(p.current.x+1, p.current.y));
        t.add(new Point(p.current.x-1, p.current.y));
        t.add(new Point(p.current.x, p.current.y+1));
        t.add(new Point(p.current.x, p.current.y-1));

        // don't allow going back to previous tile, cause infinite loops
        t.remove(p.previous);

        for (Point i : t)
        {
            if (i.x == p.current.x == p.previous.x || i.y == p.current.y == p.previous.y)
                n.add(new Path(i, p.current, p.turns));
            else
                n.add(new Path(i, p.current, p.turns+1));
        }

        return n;
    }

    // ..

}

private class Path
{
    public Point current, previous;
    public int turns;

    public Path(Point curr, Point prev, int tur)
    {
        current = curr;
        previous = prev;
        turns = tur;
    }
}
于 2013-03-13T08:20:17.903 に答える