亲宝软件园·资讯

展开

Java 深度搜索DFS算法

java舞动乾坤 人气:0

DFS概述

深度优先搜索是一种在开发爬虫早期使用较多的方法。它的目的是要达到被搜索结构的叶结点(即那些不包含任何超链的HTML文件) 。在一个HTML文件中,当一个超链被选择后,被链接的HTML文件将执行深度优先搜索,即在搜索其余的超链结果之前必须先完整地搜索单独的一条链。深度优先搜索沿着HTML文件上的超链走到不能再深入为止,然后返回到某一个HTML文件,再继续选择该HTML文件中的其他超链。当不再有其他超链可选择时,说明搜索已经结束。

解释

思路

一般用矩阵表示,从当前点开始,依次向周围四个方向试探,在我们给定数值条件下依次搜索(1代表不能走,0代表能走),对走过的路进行标记,如果最终达到了要走的点,就会进行回溯,回溯时,会将已经走过的点再次标记为未走,回到出发点,进行别的方向的试探

当找到距离最短的,而且到达了终点时,停止访问,输出结果

案例题-单身的蒙蒙

题目描述

蒙蒙要找对象啦!但是对象在和他玩捉迷藏,现在有一个55的地图,蒙蒙就在(0,0)的位置,他的心上人就在(4,4)的位置,当然路上会有各种艰难险阻,现在说明一下规则。蒙蒙按照地图行动,一次走一步,而且他只能前后左右的移动,当然蒙蒙也不能穿越墙壁。地图上有两种图案,一种是‘0'表示可以走的路,另一种是‘1'表示不能走的墙

PS:(0,0)就是左上角,(4,4)就是右下角,都懂吧!

输入:

输入一个55的矩阵表示地图,‘0'表示可以走的路,‘1'表示不能走的墙,蒙蒙就在(0,0)的位置,他的心上人就在(4,4)的位置

输出:

输出蒙蒙到心上人那里最少要走多少步,若蒙蒙永远走不到心上人那里,则输出-1

输入样例:

0 1 0 0 0

0 0 0 1 0

0 1 0 1 0

0 1 0 0 0

0 0 0 1 0

输出样例:

8

题解

分析: 首先分析下,主人公要想能够找到对象,就需要走到左下角,而去的过程显然不是一帆风顺的,它会遇到墙壁,遇到墙壁就会返回,返回到前一个点之后向其他方向进行搜索,如果有通路,就会接着执行这步的操作,直到找到终点。题目中问的是最少要通过多少步才能找到对象,那么显然可能一次搜索找不到最短的路径,这里就需要回溯,把回溯的点设置为未标记,回溯到最初的点之后进行其他方向的遍历,如果第二次到达终点的值小于第一次的就更新路径,将第二次的路径作为最小的路径,直到所有点遍历完

//回溯算法
flag[xx][yy]=1//标记
dfs(1,1,step+1)
//flag[xx][yy]=0;设置为未标记的点,进行回溯

方向数组 因为要进行四个方向的试探,所以要定义一个方向数组:方向数组的定义可以使用一维数组,亦可以使用二维数组,建议大家使用一维数组,直观明了,这里解释下便于方便,将标准坐标轴顺时针方向旋转了90度,令x=0;y=0则可有四个方向坐标 右:(0,1),下:(1,0),左:(0,-1),上:(-1,0),依次取dx一次,dy一次,就和上面的坐标一致了

    static int[] dx = {0, 1, 0, -1};//方向数组,顺时针:右 下 左 上
    static int[] dy = {1, 0, -1, 0};

注意事项: 这里因为输入的是从原点开始,而外界临界值也是等同于墙壁,为了免去试探,可以将四边的设置为“1”墙壁,这样可以避免数组越界

 //试探墙壁,避免越界
        for(int i = 0; i <=6;i++){
           s[0][i]=1;
           s[i][0]=1;
           s[6][i]=1;
           s[i][6]=1;
        }

整体代码

import java.util.Scanner;
public class test2 {

    static int[][] s = new int[10][10];
    static int[][] flag = new int[10][10];

    static int min = 99;//初始化认为该路径很大
    static int[] dx = {0, 1, 0, -1};//方向数组,顺时针:右 下 左 上
    static int[] dy = {1, 0, -1, 0};

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        //试探墙壁,避免越界
        for (int i = 0; i <= 6; i++) {
            s[0][i] = 1;
            s[i][0] = 1;
            s[6][i] = 1;
            s[i][6] = 1;
        }
        //将外围墙壁左上角顶点设置为(0,0)
        for (int i = 1; i < 6; i++)//这里的从1开始,省去外围墙壁带来的不便
        {
            for (int j = 1; j < 6; j++) {
                s[i][j] = sc.nextInt();
            }
        }
        int sx = 1, sy = 1;//从(1,1)开始
        flag[sx][sy] = 1;//进行标记
        dfs(sx, sy, 0);//搜索
        if (min == 99)//如果值还是原来的,就说明不存在
            System.out.println("-1");
        else
            System.out.println(min);
    }

    public static void dfs(int x, int y, int step) {
        if (x == 5 && y == 5) {//到达了右下角,终点
            if (step < min) {//如果当前步数小于之前的
                min = step;//标记更新
            }
            return;//否则返回空
        }
        for (int i = 0; i < 4; i++) {//控制方向数组
            int xx = x + dx[i];//进行右,下,左,上搜索
            int yy = y + dy[i];
            if (flag[xx][yy] == 0 && s[xx][yy] == 0) {//如果未被标记,并且原来该位置的值为0
                flag[xx][yy] = 1;//标记
                dfs(xx, yy, step + 1);
                flag[xx][yy] = 0;//回溯
            }
        }

    }
} 

加载全部内容

相关教程
猜你喜欢
用户评论