送快递的最短路径 - 好文

题目描述：某物流派送员p，需要给a、b、c、d4个快递点派送包裹，请问派送员需要选择什么的路线，才能完成最短路程的派送。假设如图派送员的起点坐标(0,0)，派送路线只能沿着图中的方格边行驶，每个小格都是正方形，且边长为1，如p到d的距离就是4。随机输入n个派送点坐标，求输出最短派送路线值（从起点开始完成n个点派送并回到起始点的距离）。

* 题目分析

首先应该想到的是最笨最常见的做法，那就是枚举法，列出所有的路径，求出所有距离的最小值。而不应该去企图从Dijkstra或者是其他的图算法那里找突破口，说明你对图算法还了解的不深。这里很明显应该回溯穷举暴力破解，这里回溯时注意现场的恢复；
* 代码实现 static class Point { int x, y; public Point(int i, int i1) { x = i; y
= i1; } }public static void main(String[] args) { start = new Point(0, 0);
points =new Point[]{new Point(1, 1), new Point(5, 2), new Point(4, 6), new
Point(2, 7)}; System.out.println(minPath()); } private static int min =
Integer.MAX_VALUE;//全局最小路径，初始为无穷大 private static Point start; //起点 private
static Point[] points; //所有的顶点数组 /** * 计算最短路径的算法，深搜，回溯等 * @return 返回全局最小路径数值 */
private static int minPath() { boolean[] b = new boolean[points.length]; int
path =0; for (int i=0; i<points.length; i++) { path += getDis(start,
points[i]); dfs(i, path, b,1, points.length); } return min; } /** * 深搜主算法 *
@param index 当前顶点的序号 * @param path 所有距离累加值 * @param b 标记数组，true则在当前路径上 * @param
level 深搜深度 * @param length 总深度 */ private static void dfs(int index, int path,
boolean[] b, int level, int length) { if (level == length) { path +=
getDis(start, points[index]);if (path < min) min = path; return; } b[index] =
true; for (int i=0; i<points.length; i++) { if (!b[i]) { path +=
getDis(points[index], points[i]); dfs (i, path, b, level+1, length); } }
b[index] =false; } /** * 由两个点获取期间的距离算法 * @param start * @param point * @return
*/ private static int getDis(Point start, Point point) { return
Math.abs(start.x-point.x) + Math.abs(start.y-point.y); }
* 做题应该先从最容易想到的算法想起，有时间再考虑优化，除非你对高级算法已经非常熟悉了。

热门工具换一换