精华内容
下载资源
问答
  • 深度搜索
    千次阅读
    2021-01-03 23:26:16

    深度优先搜索属于图算法的一种,是一个针对图和树的遍历算法,英文缩写为DFS即Depth First Search。深度优先搜索是图论中的经典算法,利用深度优先搜索算法可以产生目标图的相应拓扑排序表,利用拓扑排序表可以方便的解决很多相关的图论问题,如最大路径问题等等。一般用堆数据结构来辅助实现DFS算法。其过程简要来说是对每一个可能的分支路径深入到不能再深入为止,而且每个节点只能访问一次。

    搜索与回溯是计算机解题中常用的算法,很多问题无法根据某种确定的计算法则来求解,可以利用搜索与回溯的技术求解。回溯是搜索算法中的一种控制策略。它的基本思想是:为了求得问题的解,先选择某一种可能情况向前探索,在探索过程中,一旦发现原来的选择是错误的,就退回一步重新选择,继续向前探索,如此反复进行,直至得到解或证明无解。

    如迷宫问题:进入迷宫后,先随意选择一个前进方向,一步步向前试探前进,如果碰到死胡同,说明前进方向已无路可走,这时,首先看其它方向是否还有路可走,如果有路可走,则沿该方向再向前试探;如果已无路可走,则返回一步,再看其它方向是否还有路可走;如果有路可走,则沿该方向再向前试探。按此原则不断搜索回溯再搜索,直到找到新的出路或从原路返回入口处无解为止。



    参考链接:https://www.jianshu.com/p/bff70b786bb6
    更多相关内容
  • 进行深度搜索的程序,含有测试使用的小程序,可以直接运行
  • 深度优先搜索算法Matlab源码 % 此程序从国外网站收集得到,是标准的深度优先搜索算法,可实现节点遍历和检测回路的功能,详细情况请看原英文注释 % 我在此程序中添加了随机性,即遇到分叉时,随机选下一个节点,...
  • 深度搜索

    千次阅读 2018-12-08 21:49:46
    深度搜索DFS 深搜的奥义在于-------不撞南墙不回头 “可能我撞了南墙才会回头吧,可能我见了黄河才会死心吧。。。” 来自于8102年很火的一首歌 深度优先搜索,顾名思义,就是在搜索时要深入到不能再深入为止。 什么...

    深度搜索DFS

    深搜的奥义在于-------不撞南墙不回头

    “可能我撞了南墙才会回头吧,可能我见了黄河才会死心吧。。。”

    来自于8102年很火的一首歌

    深度优先搜索,顾名思义,就是在搜索时要深入到不能再深入为止

    什么意思呢,我们拿一棵树来举例吧。
    在这里插入图片描述

    这是一个树形的数据结构,在A处,有三个选择,选择一个之后判断还能不能继续深入,即判断是否到了叶子结点。假设选择了B,还能深入,那么继续往下走,假设这次选择了E。此时到了叶子节点,没法继续深入,那么就要往回走。退回到了B之后,发现还有另外一条路可以走,直到下一次撞到了“南墙”才会回头,这就是深搜。

    就像走迷宫一样,当然迷宫问题就是一类典型的深搜。
    网上找的图
    我们走迷宫的时候,除去我们来时的方向,总共有三个方向可以走,判断一下我们要去的方向是不是墙,一直这么走下去,直到三个方向都不能走的时候,就是我们所说的死胡同,这时,我们需要退回去(这其实就是回溯,深搜和回溯在一些问题上,其实是没什么差别的),退到我们上一个路口,看看还有没有路可以走,如果有就走,如果没有,就再退回到上上个路口,以此类推,如果此迷宫有一条路径,我们一定会找到,因为这样的走法我们枚举的此迷宫的所有路径。

    展开全文
  • 是非常有用的程序, 深度优先搜索可用于电网潮流,能运行,可在此基础上修改!
  • 深度搜索(DFS)和广度搜索(BFS)

    千次阅读 2019-07-18 10:52:34
    深度搜索(DFS) 一、搜索方法:  沿出发顶点的第一条路径尽量深入,遍历路径上所有顶点;然后退回到该顶点,搜索其它路径,直到以该顶点为始点的所有路径的顶点都被访问,深度搜索算法是递归算法,因为对于没一个...

    深度搜索(DFS)

    一、搜索方法:
     沿出发顶点的第一条路径尽量深入,遍历路径上所有顶点;然后退回到该顶点,搜索其它路径,直到以该顶点为始点的所有路径的顶点都被访问,深度搜索算法是递归算法,因为对于没一个节点来说,执行的是同样的操作。
     简单来说,深度搜素算法就是一条道走到黑,走不动了再回溯回去,选择其他路径,举个例子,对于下面的图,假设从1开始遍历:

    (1)第一步,访问结点1并标记




    (9)第九步,访问结点3并标记

    二、用途
     深度搜索常用于解决图的遍历问题(尤其是矩阵图如迷宫问题等),比如求解从某一个点到另一个点的最短距离,则只需遍历所有路径,在遍历同时记录路径长度,最后一定能找到最短的距离,但这种方法复杂度较高,因为要遍历完所有结点才能找到。
     深度搜索是回溯法的主要方法,沿着一条路一直走,走不通再回溯到上一节点,选择其他路径。
    三、深度搜索模板(对于矩阵图)

    int dxy[4][2]={//模拟上下左右四个方向
    	-1,0,//向上(x减一,y不变)
    	1, 0,//向下
    	0,-1,//向左
    	0, 1//向右
    	}
    void dfs(int x0,int y0,int x1,int y1)
    {
    	//(x0,y0)是出发点,(x1,y1)是目标点
    	if(x0==x1&&y0==y1)//找到目标点
    	{
    		//执行操作如输出路径等
    		return}
    	for(int i=0;i<4;i++)//遍历四个方向每一个分支,对每一个分支都进行深度搜索
    	{
    		int dx=dxy[i][0];//移动后的横坐标
    		int dy=dxy[i][1];//移动后的纵坐标
    		if(坐标越界||遇到障碍物||...)//不满足条件
    			continue;
    		//执行操作
    		dfs(dx,dy,x1,y1)//深度遍历
    		//遍历结束恢复操作
    	}
    }
    

    广度搜索(BFS)

    一、搜索方法
     广度搜索,顾名思义,就是更大范围内搜索,与深度搜索不同的是,深度搜索是一次搜索一条路径,一直搜索到走不通为止;而广度搜索是同时搜索所有路径,相当于一层一层地搜索,就好比波浪的扩展一样。此搜索方法跟树的层次遍历类似,因此宽度搜索一般都用队列存储结构。搜索原则:
    (1)访问遍历出发顶点,该顶点入队
    (2)队列不空,则队头顶点出队;
    (3)访问出队顶点所有的未访问邻接点并将其入队;
    (4)重复(2)(3),直到队空或者找到目标点
    举个例子,还是对下面这个图进行广度遍历:





    二、用途
     虽然看似广度搜索一次扩张了很多个点,但实际上任然是一个结点一个结点地搜索,只是它是以层层扩张的方式进行搜索。广度搜索也常用于解决图的遍历,在求一个点到另一个点的最短距离时,广度搜索比深度搜索更有优势,因为广度搜索是层层遍历的,所以一定存在某条路径最先到达目标点,只要找到目标点后就退出,就不用搜索所有点。
     广度搜索也是分支限界法的主要算法(当然,分支限界也可能是广度搜索和宽度搜索的结合)。广度搜索最常解决的问题类型是:求从某一个状态到另一个状态的最小步数,每一个状态对应多个(扩展结点个数)不同的操作。
    三、算法模板

    #include<iostream>
    #include<queue>
    using namespace std;
    struct state
    {
    	int a,b;//存储相应信息
    	int step;//存储当前结点的步数
    };
    queue<state>Q;
    int bfs(int a,int b,int A,int B)//返回最小步数
    {
    	//参数a,b是初始状态,
    	//参数A,B是目标状态判断条件;
    	while(!Q.empty())Q.pop();//清空队列
    	state P;
    	P.a=a;P.b=b;P.step=0;//初始结点
    	Q.push(P);//初始结点入队
    	while(!Q.empty())//队列非空
    	{
    		state head=Q.front();//保存队头
    		Q.pop();//队头出队
    		//以下扩展每个结点的邻接结点*************************
    		state p=head;
    		p.a=...//执行操作
    		p.b=...//执行操作
    		p.step++;//步数加一
    		//判断p.a,p.b是否合法(剪枝处理)
    		if(ok(p.a,p.b))
    		{
    			if(p.a==A&&p.b==B)//判断该状态是否满足目标状态
    			return p.step;//返回步数
    			Q.push(p);//否则入队
    		}
    		
    		//扩展其他结点
    		......
    		//扩展结点结束*************************************
    	}
    	return -1;//不能到达目标状态,返回-1;
    }
    

    经典例题
    迷宫问题

    展开全文
  • Python深度搜索迷宫游戏

    千次阅读 2022-01-30 17:31:40
    python动态演示深度搜索一个迷宫,小虫子找到终点后就不会动了.本程序用sprites做界面,需要安装这个模块才能运行, 安装方法: pip install sprites

     

    from sprites import *
    
    def cangoto(i,j):
        """返回是否能到达i,j位置"""
        if i<rows and j<cols:
            if maze[i][j]==0:
                return True
        return False
    
    maze=[[1,1,1,1,1,1,1,1,1,1,1,1,1,1],
          [1,0,0,0,1,1,0,0,0,1,0,0,0,1],
          [1,0,1,0,0,0,0,1,0,1,0,1,0,1],
          [1,0,1,0,1,1,1,1,0,1,0,1,0,1],
          [1,0,1,0,0,0,0,0,0,1,1,1,0,1],
          [1,0,1,1,1,1,1,1,1,1,0,0,0,1],
          [1,0,1,0,0,0,0,0,0,0,0,1,0,1],
          [1,0,0,0,1,1,1,0,1,0,1,1,0,1],
          [1,0,1,0,1,0,1,0,1,0,1,0,0,1],
          [1,0,1,0,1,0,1,0,1,1,1,1,0,1],
          [1,0,1,0,0,0,1,0,0,1,0,0,0,1],
          [1,1,1,1,1,1,1,1,1,1,1,1,1,1]]
    
    cols = 14                           # 列数
    rows = 12                           # 行数  
    
    screen = Screen()
    screen.tracer(0,0)
    screen.setup(800,600)
    
    bug = Sprite(shape='square')        # 新建方形对象
    bug.shapesize(2.5)
    cors = bug.draw_grid2(rows,cols)    # 画rows行,cols列,宽高各50的格子
    bug.clear()                         # 清除所有格子
    # 格子标为1的印上黑色正方形
    for r in range(rows):
        for c in range(cols):
            if maze[r][c]==1:           # 如果这个位置是1 
                bug.goto(cors[r][c])    # bug到达这个位置的坐标
                bug.stamp()             # 印黑正方形
    bug.shape('res/bug.png')            # bug 修改造型 
    bug.scale(1)                        # 修正比例
    bug.goto(cors[1][1])                # 到达起始点
    bug.dest= False                     # 自定义属性
    screen.update()
    def walk_maze(r,c,endr,endc):       # 递归函数(深度搜索)  
        """r,c:起点,endr,endc:终点"""
        # 寻找所有可用的方向
        for i,j in dirs:
            if cangoto(r+i,c+j):        # 如果前面这一格是空
                r += i
                c += j
                if bug.dest == False:   # 如果没到达目的地
                   bug.goto(cors[r][c]);bug.wait(0.2)
                maze[r][c] = 1
                stack.append((r,c))                
                if r==endr and c==endc: # 如果到达目的地了
                    bug.dest = True                     
                else:walk_maze(r,c,endr,endc)
        else:       
           if stack:
               r,c = stack.pop()
               if bug.dest == False:   # 如果没到达目的地
                   bug.goto(cors[r][c]);bug.wait(0.2)
               walk_maze(r,c,endr,endc)
    
    r,c = 1,1                          # 起点
    endr,endc = 10,12                  # 终点
    txt2image('起','res/起点.png')     # 文字转图
    txt2image('终','res/终点.png')     # 文字转图
    dummy = Sprite(visible=False)
    dummy.shape('res/起点.png')
    dummy.goto(cors[r][c])
    dummy.stamp()
    dummy.shape('res/终点.png')
    dummy.goto(cors[endr][endc])
    dummy.stamp()
    
    stack = []
    dirs = [(1,0),(0,1),(-1,0),(0,-1)]  # 4个方向
    stack.append((r,c))                 # 起点添加到stack中
    walk_maze(r,c,endr,endc)
    
    screen.mainloop()
                
    
    

    展开全文
  • 1.深度优先搜索中的关键 2.深度优先搜索小结 ...对于深度优先搜索,最重要的参数有两个,第一是 深度搜索的次数 step,可以看做需要将待搜索的结果放入到 step 个盒子中,直到放满为止。 第二个是每一...
  • 深度优先搜索是按照树的深度进行搜索的,所以又叫纵向搜索,在每一层只扩展一个节点,直到为树的规定深度或叶子节点为止。这个便称为深度优先搜索。 我先来说说两种算法的不同点。广度优先搜索,适用于所有情况下的...
  • 人工只能作业,利用python实现深度优先搜索解决八数码问题,测试通过,
  • 深度优先搜索 分析过程 实现代码 进出栈过程示意图 DFS算法应用-Leetcode相关题目 Leetcode 78 Subsets Leetcode 90 Subsets II Leetcode 47 Permutations II Leetcode 131 Palindrome Partitioning 答案 搜索...
  • 广度优先搜索深度优先搜索

    千次阅读 2021-11-22 09:59:27
    深度优先搜索算法框架1)二叉树深度优先搜索模板2)图深度优先搜索模板3)二维矩阵深度优先搜索模板4. 广度优先搜索算法框架1)单源广度优先搜索2)多源广度优先搜索3)双向广度优先搜索 1. 前言     深度优先...
  • 图的深度优先搜索(dfs)

    千次阅读 多人点赞 2022-03-11 11:53:46
    图的深度优先搜索(Depth First Search) 指的是在搜索时,如果遇到一个结点既有子结点,又有兄弟结点,那么先找子结点,然后找兄弟结点。 深度优先遍历,从初始访问结点出发,初始访问结点可能有多个邻接结点,深度...
  • 本C++代码解决了八数码问题,采用深度优先,广度优先和A*算法实现,基于visual studio 2017
  • 前面的递归算法,实际上是将整个数字三角形搜索了一遍,所以,完全可以用深度优先搜索算法。就是一条路走到黑,前面没有路就返回上一个路口,另选一条路走到黑…..如此反复,知道所有路全部走遍。 # //数字...
  • 数学建模 图论 课件 最小生成树 广度和深度搜索 matlab 程序 数学建模 图论 课件 最小生成树 广度和深度搜索 matlab 程序 数学建模 图论 课件 最小生成树 广度和深度搜索 matlab 程序 数学建模 图论 课件 最小生成树...
  • 代码 基于深度优先搜索算法图论代码代码 基于深度优先搜索算法图论代码代码 基于深度优先搜索算法图论代码代码 基于深度优先搜索算法图论代码代码 基于深度优先搜索算法图论代码代码 基于深度优先搜索算法图论代码...
  • 用C++写的迷宫程序,深度搜索,用C++写的迷宫程序,深度搜索
  • 1.八数码问题描述 在3×3的棋盘上,摆有八个棋子,每个棋子上标有1至8的某一数字。棋盘中留有一个空格,空格用0来表示。空格周围的棋子可以移到空格中(空格上下左右移动)。...2.广度优先搜索 ...
  • MATLAB源码集锦-基于深度优先搜索算法图论代码
  • 人工智能的作业,用深度优先遍历实现八数码问题,可以设置搜索深度。 人工智能的作业,用深度优先遍历实现八数码问题,可以设置搜索深度
  • 以用户指定的结点分别进行广度搜索和深度搜索 相应的生成树的边集 运行截图 源代码 public class AdjacencyList { public static void main(String[] args) { CreateGraph createGraph=new CreateGraph(); ...
  • 深度优先搜索求解八数码问题

    千次阅读 2022-03-18 19:31:36
    这里来看看深度优先搜索怎么完成。 深度优先的策略: 一种一直向下的搜索策略,初始节点 开始,按生成规则生成下一级各子节点,检查是否出现目标节点。若未出现,则按最新产生的(即最深的)节点优先的原则,再用...
  • 深度搜索和广度搜索

    千次阅读 2016-12-12 15:18:59
    深度优先搜索和广度优先搜索的深入讨论(一)深度优先搜索的特点是:(1)从上面几个实例看出,可以用深度优先搜索的方法处理的题目是各种各样的。有的搜索深度是已知和固定的,如例题2-4,2-5,2-6;有的是未知的,...
  • (DFS)深度优先搜索算法详解

    千次阅读 多人点赞 2021-09-13 01:37:08
    DFS 英文全称为(Depth First Search),中文简称深度优先搜索算法,其过程为沿着每一个可能的路径向下进行搜索,直到不能再深入为止,并且每一个节点只能访问一次。 算法的搜索遍历图的步骤 (1)首先找到初始...
  • 迷宫深度搜索和广度搜索 是否可以走出迷宫和最短路径 1234567890
  • 深度搜索算法C语言实现,以走迷宫为例子
  • Python图算法之深度优先搜索

    千次阅读 2019-04-13 10:04:43
    深度优先搜索(Depth First Search, DFS): 是一种用于遍历或搜索树或图的算法。沿着树的深度遍历树的节点,尽可能深的搜索树的分支。当节点v的所在边都己被探寻过,搜索将回溯到发现节点v的那条边的起始节点。这一...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 328,182
精华内容 131,272
关键字:

深度搜索