0

私はいくつかの座標点を与えられました:

  1. ソース(0,0)

  2. 行き先(m,n)

  3. となるS = {(x,y)ような座標点の集合0 < x < m0 < y < n}

(0,0)目的は、との間の最短経路の数を見つけて、これらの経路で(m,n)セット内のどの点にSも遭遇しないようにすることです。どうすれば見つけられますか?

4

6 に答える 6

3

ここでは C# でソリューションを作成していますが、Java に簡単に変換できます。うまくいけば、それは役に立つでしょう。

using System;
using System.Collections.Generic;
using System.Drawing;

namespace Game
{
    class Program
    {
        /// <summary>
        /// Find a matrix with all possible optimum paths from point A to point B
        /// </summary>
        /// <param name="rows">Rows of the matrix</param>
        /// <param name="cols">Cols of the matrix</param>
        /// <param name="points">Obstacles location</param>
        /// <param name="moves">Allowed moves</param>
        /// <param name="matrix">Resulting matrix</param>
        /// <param name="A">Starting point</param>
        /// <param name="B">Ending point</param>
        private static void FindMatrix(int rows, int cols, List<Point> points, List<Point> moves, out List<List<int>> matrix, out Point A, out Point B)
        {
            matrix = new List<List<int>>();
            A = new Point(-1, -1);
            B = new Point(-1, -1);
            //Init values of the matrix
            for (int row = 0; row <= rows; row++)
            {
                matrix.Add(new List<int>());
                for (int col = 0; col <= cols; col++)
                    matrix[matrix.Count - 1].Add(0);
            }
            var index = 0;
            while ((index < points.Count) && (points[index].Y >= 0) && (points[index].Y <= rows) && (points[index].X >= 0) && (points[index].X <= cols))
            {
                matrix[points[index].Y][points[index].X] = -1;
                index++;
            }
            if ((index == points.Count) && (matrix[0][0] == 0) && (matrix[rows][cols] == 0))
            {
                A.X = 0;
                A.Y = 0;
                B.X = cols;
                B.Y = rows;
            }
            if ((A.X >= 0) && (A.Y >= 0) && (B.X >= 0) && (B.Y >= 0)) //To check if points A and B exist in the board
            {
                var pairs = new List<Point>[2] { new List<Point>(), new List<Point>() };
                int level = 0;
                index = 0;
                pairs[index].Add(A);
                while ((pairs[index].Count > 0) && (pairs[index][pairs[index].Count - 1] != B))
                {
                    pairs[Math.Abs(1 - index)].Clear();
                    level++;
                    foreach (var pair in pairs[index])
                        foreach (var move in moves) //Test all possible moves
                            if ((pair.Y + move.Y >= 0) && (pair.Y + move.Y < matrix.Count) && (pair.X + move.X >= 0) && (pair.X + move.X < matrix[pair.Y + move.Y].Count) && (matrix[pair.Y + move.Y][pair.X + move.X] == 0)) //Inside the boundaries? Not visited before?
                            {
                                pairs[Math.Abs(1 - index)].Add(new Point(pair.X + move.X, pair.Y + move.Y));
                                matrix[pair.Y + move.Y][pair.X + move.X] = level;
                            }
                    index = Math.Abs(1 - index);
                }
                matrix[A.Y][A.X] = 0;
            }
        }

        /// <summary>
        /// Finds all possible optimum paths from point A to point B in a matix with obstacles
        /// </summary>
        /// <param name="matrix">Matrix with obstacles</param>
        /// <param name="moves">Allowed moves</param>
        /// <param name="A">Starting point</param>
        /// <param name="B">Ending point</param>
        /// <param name="result">Resulting optimum paths</param>
        /// <param name="list">Temporary single optimum path</param>
        private static void WalkMatrix(List<List<int>> matrix, List<Point> moves, Point A, Point B, ref List<List<Point>> result, ref List<Point> list)
        {
            if ((list.Count > 0) && (list[list.Count - 1] == B)) //Stop condition
            {
                result.Add(new List<Point>(list));
            }
            else
            {
                foreach (var move in moves)
                    if ((A.Y + move.Y >= 0) && (A.Y + move.Y < matrix.Count) && (A.X + move.X >= 0) && (A.X + move.X < matrix[A.Y + move.Y].Count) && (matrix[A.Y + move.Y][A.X + move.X] == matrix[A.Y][A.X] + 1)) //Inside the boundaries? Next step?
                    {
                        list.Add(new Point(A.X + move.X, A.Y + move.Y)); //Store temporary cell
                        WalkMatrix(matrix, moves, list[list.Count - 1], B, ref result, ref list);
                        list.RemoveAt(list.Count - 1); //Clean temporary cell
                    }
            }
        }

        public static List<List<Point>> FindPaths(int rows, int cols, List<Point> points)
        {
            var result = new List<List<Point>>();
            var moves = new List<Point> { new Point(1, 0), new Point(0, 1), new Point(-1, 0), new Point(0, -1) }; //Right, Down, Left, Up (clockwise)
            List<List<int>> matrix; //Matrix temporary representation to store all possible optimum paths
            Point A; //Starting point
            Point B; //Ending point
            FindMatrix(rows, cols, points, moves, out matrix, out A, out B);
            if ((A.X >= 0) && (A.Y >= 0) && (B.X >= 0) && (B.Y >= 0)) //To check if points A and B exist
            {
                List<Point> list = new List<Point>();
                list.Add(A);
                WalkMatrix(matrix, moves, A, B, ref result, ref list);
            }
            return result;
        }

        static void Main(string[] args)
        {
            var points = new List<Point>
            {
                new Point(3, 2),
                new Point(4, 2),
                new Point(5, 2),
                new Point(3, 3),
                new Point(4, 3),
                new Point(5, 3),
                new Point(3, 4),
                new Point(4, 4),
                new Point(5, 4)
            };
            List<List<Point>> paths = FindPaths(5, 10, points); //path.Count store the quantity of optimum paths
        }
    }
}
于 2012-08-09T09:16:47.517 に答える
1

これは、動的計画法を使用して解決できます。

まず、幅優先探索を使用して、すべてのノードの原点までの距離を見つけます。

その場合、原点までの距離Fを持つ点を通過する最短経路の数は、距離を持つすべての隣接する点の合計になります。(x,y)dF(x1,y1)(x1, y1)(x,y)d-1

言い換えると、F(x,y) = Sum F(all neighboring points with distance-to-origin of d-1)

于 2012-08-09T08:55:41.040 に答える
1

これは完全な解決策だと思いますが、テストして Java に変換することをお勧めします。

基本的な考え方は、最初にグリッドを検索することです。グリッド内の各ポイントで、そのポイントに到達する方法の数は、そのポイントの次の距離に到達する方法の数から 1 を引いた数に等しくなります。

n, m = 10, 15 #10 by 15 grid say

s = set([(1, 1), (2, 2), (9, 14)])

grid = []
ways = []
for i in range(n + 1):
    grid.append([None]*(m + 1))
    ways.append([0]*(m + 1))

start = (0, 0)
end = (n, m)

grid[0][0] = 0
ways[0][0] = 1

fringe = [start]
distance = 0
new_fringe = []
while True:
    for node in new_fringe:
        i, j = node
        deltas = [(-1, 0), (1, 0), (0, 1), (0, -1)] #directions to travel
        for di, dj in deltas:
            i2, j2 = i + di, j + dj
            if 0 <= i2 <= n and 0 <= j2 <= m and grid[i2][j2] == distance - 1:
                ways[i][j] += ways[i2][j2]

    new_fringe = []
    for node in fringe:
        i, j = node
        deltas = [(-1, 0), (1, 0), (0, 1), (0, -1)] #directions to travel
        for di, dj in deltas:
            i2, j2 = i + di, j + dj
            if 0 <= i2 <= n and 0 <= j2 <= m and (i2, j2) not in s and grid[i2][j2] is None:
                grid[i2][j2] = distance + 1
                new_fringe.append((i2, j2))
    if not new_fringe: #no new nodes
        break
    fringe = new_fringe
    distance += 1

for row in grid:
    print row
"""[[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15],
    [1, None, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16],
    [2, 3, None, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17],
    [3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18],
    [4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19],
    [5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20],
    [6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21],
    [7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22],
    [8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23],
    [9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, None, 24],
    [10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25]]"""

for row in ways:
    print row

"""[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]
[1, 1, 0, 2, 5, 9, 14, 20, 27, 35, 44, 54, 65, 77, 90, 104]
[1, 2, 2, 4, 9, 18, 32, 52, 79, 114, 158, 212, 277, 354, 444, 548]
[1, 3, 5, 9, 18, 36, 68, 120, 199, 313, 471, 683, 960, 1314, 1758, 2306]
[1, 4, 9, 18, 36, 72, 140, 260, 459, 772, 1243, 1926, 2886, 4200, 5958, 8264]
[1, 5, 14, 32, 68, 140, 280, 540, 999, 1771, 3014, 4940, 7826, 12026, 17984, 26248]
[1, 6, 20, 52, 120, 260, 540, 1080, 2079, 3850, 6864, 11804, 19630, 31656, 49640, 75888]
[1, 7, 27, 79, 199, 459, 999, 2079, 4158, 8008, 14872, 26676, 46306, 77962, 127602, 203490]
[1, 8, 35, 114, 313, 772, 1771, 3850, 8008, 16016, 30888, 57564, 103870, 181832, 0, 203490]
[1, 9, 44, 158, 471, 1243, 3014, 6864, 14872, 30888, 61776, 119340, 223210, 405042, 405042, 608532]"""
于 2012-08-09T10:09:21.773 に答える
0

整数座標のみが許可されている場合、グラフの問題に単純化できます。

これは、おそらくすべてのゲームで行われる方法です。グラフは四角形のように見え、一方の隅にソース、反対側に目的地があり、ノードは垂直または水平のエッジで接続されています。(いくつかのノードが削除されました。セット S)。

ここでの最短経路はコーナー間の Dyck 経路のサブセットであるため、カタロニア語数は上限です。http://mathworld.wolfram.com/DyckPath.html

于 2012-08-09T08:25:37.393 に答える
0

（x、y）で定義された点のグリッドについて話していると思います。そして、一連の最短経路を計算したい 2 点の間には、1 つ以上の障害物があります。

問題を 2 つに分けましょう 1- ポイント A から B への最短パスのグループを見つけます 2- これらの各パスで、S に属するポイントがパス上にないことを確認します

この問題を解決するために、多くのアルゴリズムが存在します。最初に考えられるのは強化学習です。これは、このリンクの視覚的な例 です。このライブラリを使用するか、自分で実装することができます。かなり簡単

両方のアルゴリズムをグリッドに実装できます。グリッドでは、いくつかのポイントを障害物としてマークします。つまり、ポイントのセット S で、パスを検出している間、セット S のポイントを回避します。

お役に立てれば

于 2012-08-09T08:24:59.103 に答える
-1

ダイクストラのアルゴリズムを調べてみてください: http://en.wikipedia.org/wiki/Dijkstra%27s%5Falgorithm

于 2012-08-09T08:10:13.480 に答える