我得到了几个坐标点：
资源
(0,0)目的地
(m,n)一组坐标点
S = {(x,y)，使得0 < x < m和0 < y < n}
目标是找出 和 之间的最短路径的数量，(0,0)使得(m,n)集合中的任何点S都不会在这些路径中遇到。我如何找到它？
问问题
5530 次
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
我认为这是一个完整的解决方案，但您可能想对其进行测试并将其转换为 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]"""
于 2012-08-09T10:09:21.773 回答
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 回答
0
如果只允许整数坐标，它可以简单地简化为图形问题。
这可能是每场比赛的完成方式。该图看起来像一个矩形，源在一个角，目标在对面，节点由垂直或水平边连接。（部分节点已被删除，设置为 S）。
现在，这里的最短路径是拐角之间的 Dyck 路径的子集，因此加泰罗尼亚数字是一个上限。http://mathworld.wolfram.com/DyckPath.html
于 2012-08-09T08:25:37.393 回答
0
我假设您正在谈论在 (x,y) 中定义的点网格。并且您要计算最短路径集的两点之间是多个障碍之一
因此，让我们将问题分成两个 1- 找到一组从 A 点到 B 点的最短路径 2- 确保在这些路径的每条路径上，没有一个属于 S 的点在路径上
为了解决这个问题，有很多算法，我想到的第一个是强化学习这是这个链接中的一个可视化示例 你可以使用这个库或自己实现它。它相当容易
两种算法都可以在网格中实现，您将一些点标记为障碍物，即您的点集 S，并且在检测路径时，集 S 的点将避开。
希望这可以帮助
于 2012-08-09T08:24:59.103 回答
-1
尝试查看 Dijkstra 的算法： http ://en.wikipedia.org/wiki/Dijkstra%27s%5Falgorithm
于 2012-08-09T08:10:13.480 回答