具有约束的图中两个坐标点之间的最短路径数
我得到了几个坐标点：
-
来源
(0,0) -
目的地
(m,n) -
一组坐标点
S = {(x,y)，使得0 < x < m且0 < y < n}
目标是找出(0,0)和(m,n)之间的最短路径的数量，使得在这些路径中从不遇到集合S中的任何点。 我怎么找到它？
这里有一个C＃解决方案，但可以轻松转换为Java。 希望你会发现它很有用。
using System; using System.Collections.Generic; using System.Drawing; namespace Game { class Program { /// /// Find a matrix with all possible optimum paths from point A to point B /// /// Rows of the matrix /// Cols of the matrix /// Obstacles location /// Allowed moves /// Resulting matrix /// Starting point /// Ending point private static void FindMatrix(int rows, int cols, List points, List moves, out List> matrix, out Point A, out Point B) { matrix = new List>(); 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 ()); 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)) { AX = 0; AY = 0; BX = cols; BY = rows; } if ((AX >= 0) && (AY >= 0) && (BX >= 0) && (BY >= 0)) //To check if points A and B exist in the board { var pairs = new List[2] { new List (), new List () }; 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[AY][AX] = 0; } } /// /// Finds all possible optimum paths from point A to point B in a matix with obstacles /// /// Matrix with obstacles /// Allowed moves /// Starting point /// Ending point /// Resulting optimum paths /// Temporary single optimum path private static void WalkMatrix(List> matrix, List moves, Point A, Point B, ref List> result, ref List list) { if ((list.Count > 0) && (list[list.Count - 1] == B)) //Stop condition { result.Add(new List (list)); } else { foreach (var move in moves) if ((AY + move.Y >= 0) && (AY + move.Y < matrix.Count) && (AX + move.X >= 0) && (AX + move.X < matrix[AY + move.Y].Count) && (matrix[AY + move.Y][AX + move.X] == matrix[AY][AX] + 1)) //Inside the boundaries? Next step? { list.Add(new Point(AX + move.X, AY + 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> FindPaths(int rows, int cols, List points) { var result = new List>(); var moves = new List { new Point(1, 0), new Point(0, 1), new Point(-1, 0), new Point(0, -1) }; //Right, Down, Left, Up (clockwise) List> 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 ((AX >= 0) && (AY >= 0) && (BX >= 0) && (BY >= 0)) //To check if points A and B exist { List list = new List (); list.Add(A); WalkMatrix(matrix, moves, A, B, ref result, ref list); } return result; } static void Main(string[] args) { var points = new List { 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> paths = FindPaths(5, 10, points); //path.Count store the quantity of optimum paths } } }
这可以使用动态编程来解决。
首先，使用广度优先搜索找到每个节点的原点距离。
然后，通过距离到原点d的点(x,y)的最短路径F的数量正好是所有(x1, y1)相邻(x,y)与距离的F(x1,y1) (x,y)和d-1 。
换句话说， F(x,y) = Sum F(all neighboring points with distance-to-origin of d-1)
我认为这是一个完整的解决方案，但你可能想测试它并将其转换为java。
基本思想是首先搜索网格。 在网格中的每个点，到达该点的方式的数量等于在距离较少的那一点上接近该点的方式的数量。
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]"""
我假设你在谈论（x，y）中定义的点网格。 在你想要计算最短路径集合的两点之间的那个是一个或多个障碍
所以让我们把问题分解为两个1-找到一组从A点到B的最短路径2-确保在这些路径的每条路径上，没有一个属于S的路径在路径上
为了解决这个问题，有很多算法，第一个我想到的是强化学习这是一个可视化的例子，你可以使用这个库或自己实现它。 它相当容易
两种算法都可以针对网格实现，其中您将某些点标记为障碍物，即您的点S集合，并且在检测路径时将避免集合S的点。
希望这可以帮助
如果仅允许整数坐标，则可以简单地将其简化为图形问题。
这就是它在每场比赛中的表现。 该图形看起来像一个矩形，一个角落的源，另一个角落的目的地，以及通过垂直或水平边缘连接的节点。 （一些节点已被删除，集合S）。
现在，这里的最短路径是角落之间的Dyck路径的子集，因此加泰罗尼亚数字是上限。 http://mathworld.wolfram.com/DyckPath.html
试着看看Dijkstra的算法： http ： //en.wikipedia.org/wiki/Dijkstra%27s%5Falgorithm