记一个图算法的求解过程

Updated on with 664 views

几天前做了一题相对复杂的算法题,算是路径题。一般此类题目能想到的解法有 DFS、BFS、动态规划、贪心、迪杰斯特拉算法(不适用)、弗洛伊德算法(不适用)等。

题目大意

接下来看下完整的题目,题目很长,当时读题(全英文)就花了近半小时。为了方便理解,我将其描述为容易理解的语言。

上图是一个 m * n 的矩阵,S 为出发的起点(永远为左下角),A 为所要达到的终点。可以从任一方向前进(上下左右),但是水平前进时,需要有路,即必须有短横才能同行;而纵向的同行可以直接跳跃到下一个短横。

需要求解的是,纵向路径长版的最小值。即上图中的答案为 2。该图的其他路径,例如从 S 先向上到 6 的第一个板,之后再向右到达 A。但是这样使得纵向路径的长板为 5,没有达到最优的 2。

这个图只是一个个例,要注意的是,其路径不一定都是向右和向上,有可能先向上后向下也会是最优解。

算法求解

首先,我想到了 DFS 求解,即可就开始写。定义一个 GraphDFS,将一些属性设置好,arr 为这个图,mark 是记忆恢复使用的数组,ans 为最优解,curMax 用于记录一个路径中的长版。

public class GraphDFS {
	private final int[][] arr;
	private final int[][] mark;
	private final int m;
	private final int n;
	private int ans;
	private int curMax;

	// start -> (m - 1, 0)
	// end -> arr[i][j] = 2

	public GraphDFS(int[][] arr) {
		this.m = arr.length;
		this.n = arr[0].length;
		this.arr = arr;
		this.mark = new int[m][n];
		this.ans = m;
		this.curMax = 1;
	}
}

边界判断,这个很常见,不赘述。

private boolean inArea(int i, int j) {
	return i >= 0 && j >= 0 && i < m && j < n;
}

之后是 DFS 的核心算法,首先判断是否越界,之后到达 S 点的判断(之前没有提到,S 点的数组值为 2,短横的值为 1,其他为 0)。之后是从四个方向分别搜索,这里传了一个布尔值,这是由于纵向遍历时,需要计算当前的长版,所以在自定义的 ops 方法内会有些不同。

private void dfs(int i, int j) {
	if (!inArea(i, j)) {
		return;
	}
	if (arr[i][j] == 2) {
		ans = Math.min(ans, curMax);		
		return;
	}
	ops(up(i, j), i, true);
	ops(down(i, j), i, true);
	ops(left(i, j), i, false);
	ops(right(i, j), i, false);
}

四个方向的搜索以获得,最新的位置,这里复杂的地方是 updown 方法的搜索,需要向上或向下找到一个板,这里需要用到 while,但没有办法,这部分时间复杂度只能贡献。

private int[] up(int i, int j) {
	while (inArea(--i, j)) {
		if (arr[i][j] == 1 || arr[i][j] == 2) {
			return new int[]{i, j};
		}
	}
	return new int[]{-1, -1};
}

private int[] down(int i, int j) {
	while (inArea(++i, j)) {
		if (arr[i][j] == 1 || arr[i][j] == 2) {
			return new int[]{i, j};
		}	
	}
	return new int[]{-1, -1};
}

private int[] left(int i, int j) {
	if (!inArea(i, j - 1) || (arr[i][j - 1] != 1 && arr[i][j - 1] != 2)) {
		return new int[]{-1, -1};
	}
	return new int[]{i, j - 1};
}

private int[] right(int i, int j) {
	if (!inArea(i, j + 1) || (arr[i][j + 1] != 1 && arr[i][j + 1] != 2)) {
		return new int[]{-1, -1};
	}
	return new int[]{i, j + 1};
}

ops 是我自定义方法,抽取了 DFS 操作方向的公用代码,也可以直接写在 DFS 里,会比较长。纵向时需要更新 curMax 长板值。

private void ops(int[] dir, int i, boolean cmp) {
	int x = dir[0];
	int y = dir[1];
	int tmpCurMax = curMax;

	if (x != -1 && mark[x][y] != 1) {
		if (cmp) {
			curMax = Math.max(curMax, Math.abs(i - x));
		}

		mark[x][y] = 1;
		dfs(x, y);
		mark[x][y] = 0;

		if (cmp) {
			curMax = tmpCurMax;
		}
	}
}

代码到这里其实基本结束了,用主方法测一下,能得到正确值。

public static void main(String[] args) {
	int[][] arr = new int[][]{
			{1, 1, 0, 0, 1, 1},
			{0, 0, 1, 1, 0, 0},
			{1, 1, 1, 1, 1, 2},
			{0, 0, 0, 0, 0, 0},
			{0, 0, 0, 0, 0, 1},
			{0, 0, 0, 0, 1, 1},
			{0, 0, 0, 1, 1, 0},
			{1, 1, 1, 1, 1, 1}
	};
	GraphDFS graph = new GraphDFS(arr);
	System.out.println(graph.getAns());
}

但这个问题到这里远没有结束,这里用 DFS 搜索确实可以求解这个矩阵图,其原因是矩阵很小,但是题目给到了一个 50 * 50 的矩阵,用上述代码剪枝后仍然无法求解,复杂度过高,后续有时间会再写一个 BFS 的版本,可以降低一些复杂度,或许可以求解大矩阵。


标题:记一个图算法的求解过程
作者:Jeffrey

Responses
取消