网格 最短路径算法求助

Question

网格算法

Answer 1

其实好像就是排列组合。。因为两点之间的最短路径很简单，所以只需要知道怎么遍历这些节点就可以了
写了一个例子，比较乱，凑合着看。。
输入文件的格式为
第一行两个整数，用空格隔开，分别表示起点的X和Y坐标
第二行相似，表示终点的坐标
第三行一个整数，表示中间需要走到的节点个数N
接下来N行，每行表示一个节点的坐标，并且按顺序每个节点的编号为0,1,2,...
以LZ的图为例的输入文件
4 0
4 4
3
0 1
1 3
3 2

Answer 2

贴上代码，输入文件路径请自行修改
import java.io.*;
import java.util.*;public class FindPath {
private static int min = Integer.MAX_VALUE;
private static List<Node> minPath;

public static void main(String[] args) throws IOException {
Scanner in = new Scanner(new FileInputStream("D:\\input.txt"));

Point start = readPoint(in);
in.nextLine();
Point end = readPoint(in);
in.nextLine();

int num = in.nextInt();

Point[] points = new Point[num];
for (int i = 0; i < num; i++) {
in.nextLine();
points[i] = readPoint(in);
}

in.close();

List<Node> left = new ArrayList<>();
Node[] nodes = new Node[num];
for (int i = 0; i < num; i++) {
nodes[i] = new Node(String.valueOf(i));
nodes[i].distanceToEnd = end.distanceTo(points[i]);
nodes[i].distanceFromStart = start.distanceTo(points[i]);

for (int j = i - 1; j >= 0; j--) {
int distance = points[i].distanceTo(points[j]);
nodes[i].neighbor.put(nodes[j], distance);
nodes[j].neighbor.put(nodes[i], distance);
}

left.add(nodes[i]);
}

search(new Path(), left);

System.out.println("Min: " + min);

System.out.print("Start->");
for (Node node : minPath) {
System.out.print(node.name + "->");
}
System.out.println("End");
}

private static Point readPoint(Scanner in) {
int x = in.nextInt(), y = in.nextInt();
return new Point(x, y);
}

private static void search(Path path, List<Node> left) {
if (left.size() == 0) {
int distance = path.getTotalDistance();
if (distance < min) {
min = distance;
minPath = path.getPath();
}
} else {
for (int i = left.size(); i > 0; i--) {
Node node = left.remove(0);
path.add(node);
search(path, left);
left.add(node);
path.removeLast();
}
}
}

private static class Path {
List<Node> path;
int distance;

public Path() {
this.path = new ArrayList<>();
this.distance = 0;
}
public void add(Node node) {
if (path.size() > 0) {
Node last = this.path.get(this.path.size() - 1);
this.distance += last.neighbor.get(node);
}
this.path.add(node);
}
public void removeLast() {
Node node = this.path.remove(this.path.size() - 1);
if (path.size() > 0) {
Node last = this.path.get(this.path.size() - 1);
this.distance -= last.neighbor.get(node);
}
}
public int getTotalDistance() {
Node last = this.path.get(this.path.size() - 1);
Node first = this.path.get(0);
return distance + last.distanceToEnd + first.distanceFromStart;
}
public List<Node> getPath() {
List<Node> copy = new ArrayList<Node>(this.path.size());
for (Node node : this.path) {
copy.add(node);
}
return copy;
}
}

private static class Point {
int x, y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
public int distanceTo(Point point) {
return Math.abs(this.x - point.x) + Math.abs(this.y - point.y);
}
}

private static class Node {
String name;
Map<Node, Integer> neighbor;
int distanceToEnd, distanceFromStart;

public Node(String name) {
this.name = name;
this.neighbor = new HashMap<>();
}
}
}

Answer 3

看数据结构里最小生成树的算法，很简单的
1. Prim算法视频http://v.qq.com/boke/page/n/0/f/n0127zg3qzf.html
2. Kruskal算法http://v.qq.com/boke/page/s/0/5/s0127bo19g5.html

Answer 4

谢谢英雄悉心指导
经粗略测试，暂且可以
试问英语算法思路
因为我接下来想要稍稍改进一下，输出显示 start->0->1->2->end 的具体走法
万分感谢您的帮助 
解决了困扰多日的问题

Answer 5

思路其实就是图的深度优先搜索，稍微剪了一下枝
因为每个节点都要访问且最多访问一次（重复访问一个节点不可能是最优解），所以可以用一个List来记录还没访问到的节点，避免重复访问同一个节点深搜的思路大概是，在某个节点上，首先判断现在是不是所有节点都访问到了（59行，left.size() == 0），如果是，那么计算总路程，并且和当前最短路径对比，如果还有节点没访问过（left这个List里还有节点），那么依次访问没访问到的节点。如果你要输出坐标具体路径，起点和终点分别是start和end（都是我自己写的Point类，见112行），中间的节点坐标通过points[n]获取，n为节点编号（就是0,1,2,..这些）