精华内容
下载资源
问答
  • 图搜索算法

    千次阅读 2018-05-05 13:27:44
    本文作者: lemon ... 版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 3.0 许可协议。...所谓的G=(V,E)G=(V,E),由顶点(Vertex) VV 和边(Edges) EE 组成。可以用两种标准方式来表示: 邻接...
    
    

    图的表示

    所谓的图G=(V,E)G=(V,E),由顶点(Vertex) VV 和边(Edges) EE 组成。可以用两种标准方式来表示:

    • 邻接链表
    • 邻接矩阵

    Alt text

    根据图是否有向,可以将图分为有向图和无向图。

    邻接链表

    邻接链表由 |V||V| 条链表构成,即每个顶点 Vi∈VVi∈V有一条链表,链表中存储该顶点的相邻顶点。一般来说,邻接链表更适合表示稀疏图(边的条数|E||E| 远远小于|V|2|V|2的图)。
    邻接链表表示图
    如上图所示,图C为无向图A(G=(V,E),|V|=5,|E|=7G=(V,E),|V|=5,|E|=7)的邻接链表表示,共有5条链表,且所有邻接链表的长度之和等于 2|E|2|E|, 即14。图D为有向图B(G=(V,E),|V|=5,|E|=7G=(V,E),|V|=5,|E|=7)得邻接链表表示,邻接链表的长度之和等于 2|E|2|E| 。不论是有向图还是无向图均需要的存储空间为 Θ(V+E)Θ(V+E)。

    邻接矩阵

    对于邻接链表而言,存在一个明显的不足就是无法快速判断边(u,v)(u,v) 是否为图中的边,而邻接矩阵恰恰克服了这一缺陷。
    邻接矩阵,对于图GG而言,其邻接矩阵由 |V|×|V||V|×|V|的矩阵 A=(aij)A=(aij) 表示, 并满足以下关系:

    • aij=1,如果(i,j)∈Eaij=1,如果(i,j)∈E
    • aij=0,其他aij=0,其他

    图E、图F分别给出了无向图与有向图的邻接矩阵表示,其空间需求皆为Θ(V2)Θ(V2)。与邻接链表相反,邻接矩阵更适合表示稠密图(边的条数|E||E| 接近 |V|2|V|2的图)。
    Alt text

    图的遍历

    广度优先搜索(BFS)

    给定图G=(V,E)G=(V,E)以及源点 SS, 通过调用广度优先算法可以发现从源点到达的所有顶点,同时生产一颗 “广度优先搜索树”。这里我们将借助一个先进先出(FIFO)的队列 QueueQueue 实现算法。
    下面给出该算法的文字描述:

    1. 初始化所有顶点,将顶点标记为未访问。
    2. 将顶点 SS 存入队列 QueueQueue 中。
    3. 如果队列 QueueQueue 非空,进入下一步,否则退出。
    4. 出队列 DeQueueDeQueue ,得到顶点 uu,如果 uu 未被访问,进入下一步,否则回到步骤3。
    5. 将 uu 标记为已访问,并将顶点 uu 的所有满足条件(1.未访问,2.队列中不存在该结点)的邻接结点存入QueueQueue 中,。
    6. 打印顶点 uu,跳转到步骤3.

    为了便于理解,我们结合图A中表示的无向图,源点为A,给出BFS的执行过程:
    Alt text

    <1>. 如图(a)所示,我们初始化所有顶点状态未访问(用绿色表示),将源点AA存入队列 QueueQueue。

    <2>. 如图(b)所示,弹出AA并将其邻接结点B,EB,E加入队列中,输入AA。

    <3>. 如图(c)所示,弹出队列头部元素BB,将其满足条件的邻接结点 C,DC,D 存入队列,输出 BB。

    <4>. 如图(d)所示,弹出队列头部元素EE,其邻接结点均已入队列,输出 EE。

    <5>. 如图(e)所示,弹出队列头部元素CC,其邻接结点均已入队列,输出 CC。

    <5>. 如图(f)所示,弹出队列头部元素DD,其邻接结点均已入队列,输出 DD。

    <6>. 队列 QueueQueue 为空,终止算法。最终得到输出数列 A,B,E,C,DA,B,E,C,D,其广度优先搜索树如下图G所示:

    Alt text

    深度优先搜索(DFS)

    深度优先搜索总是对最近才发现的结点 vv 的出发边遍历直到结点的所有出发边均被发现,然后再“回溯”到 vv 的前驱结点来搜索其出发边。这里我们借助栈 StackStack 的思想来描述算法。
    下面给出该算法的文字描述:

    1. 初始化所有顶点,将顶点标记为未访问。
    2. 将出发点 SS 压入栈 StackStack 中。
    3. 如果栈非空,进入下一步,否则退出结束算法。
    4. 弹出栈顶结点 uu,如果 uu 未被访问,进入下一步,否则回到步骤3。
    5. 将 uu 标记为已访问,并将顶点 uu 的所有满足条件(1.未访问,2.栈中不存在该结点)的邻接结点存入StackStack 中。
    6. 打印结点 uu,跳转到步骤3.

    为了更加直观的描述DFS的思路,我们结合图B 与源点 AA ,给出算法DFS的执行过程:
    Alt text

    图的实现(Java)

    邻接链表实现

    图的邻接链表表示

    我们知道描述一张图有两个最基本的元素结点 VV 和边 EE,在这里我们首先定义一个类Graph.java来表示图,将Vertex.java作为其内部类表示结点,实现代码如下。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    
    package com.pty.graph;
    
    import java.util.ArrayList;
    import java.util.LinkedHashMap;
    
    public class Graph<T> {
    	private LinkedHashMap<T, Vertex> vertexs;// 使用LinkedHashMap存放图中的结点,结点标识T作为key能快速查找图中是否包含某结点
    	private LinkedHashMap<T, ArrayList<Vertex>> adjList; // 采用邻接链表的方式表示图,每个结点T对应于一个ArrayList链表,存放其相邻结点。
    	private int numOfVertex; // 图的结点数
    	private int numOfEdge; // 图的边数
    	private boolean directed; // 是否为有向图
    
    	public Graph(boolean directed) {
    		vertexs = new LinkedHashMap<T, Vertex>();
    		numOfVertex = 0;
    		adjList = new LinkedHashMap<T, ArrayList<Vertex>>();
    		this.directed = directed;
    	}
    	//省略相应的get、set方法
    	/**
    	 * 内部类,表示结点
    	 * 
    	 * @author john
    	 *
    	 */
    	public class Vertex {
    		private T lable; // 标识结点,比如A0,A1,A2,...或者1,2,3,...
    		private boolean visited; // 标识结点是否被访问
    
    		public Vertex(T tag, double score) {
    			lable = tag;
    			visited = false;
    		}
    		//省略相应的get、set方法
    	}
    }
    

     

    图的基本操作

    添加新的结点
    每新增一个结点,将会创建一个ArrayList列表,用于存放新增结点的邻接结点。

    1
    2
    3
    4
    5
    
    public void insertVertex(T tag) {
    	vertexs.put(tag, new Vertex(tag)); //新增结点 tag,如果定点中存在该结点将会被替换最新的
    	adjList.put(tag, new ArrayList<Vertex>()); //每新增一个结点,将会创建一个ArrayList列表,用于存放新增结点的邻接结点。
    	numOfVertex++; //结点数自增
    }
    

     

    添加新的边
    这里暂时不考虑边的权值

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    
    public boolean addEdges(T start, T end) {
    	if (vertexs.containsKey(start) && vertexs.containsKey(end)) { // 判断输入起始点是否合法
    		adjList.get(start).add(vertexs.get(end)); // 首先获取结点start的链表,然后将其邻接结点end加入其中
    		if (!directed) { //如果是无向图,则添加结束点到开始点的边
    			adjList.get(end).add(vertexs.get(start));
    		}
    	} else {
    		System.out.println("输入结点不合法");
    		return false;
    	}
    	return true;
    }
    

     

    测试
    打印图的链表结构

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    
    /**
     * 打印图的邻接链表
     */
    public void displayGraph() {
        System.out.println("邻接链表表示如下:");
    	Iterator<Map.Entry<T, ArrayList<Vertex>>> iterator = adjList.entrySet().iterator();
    	while (iterator.hasNext()) {
    		Map.Entry<T, ArrayList<Vertex>> element = iterator.next();
    		System.out.print(element.getKey() + ":");
    		displayList(element.getValue());
    	}
    }
    
    /**
     * 打印链表ArrayList
     * 
     * @param list
     */
    public void displayList(ArrayList<Vertex> list) {
    	int size = list.size();
    	for (int i = 0; i < size; i++) {
    		System.out.print(list.get(i).getLable());
    		if (i < size - 1) {
    			System.out.print("-->");
    		}
    	}
    	System.out.println();
    }
    

     

    测试数据(无向图A)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    
    package com.pty.graph;
    
    public class Test {
    	public static void main(String[] args) {
    		Graph<String> graph = new Graph<String>(false);
    		graph.insertVertex("A");
    		graph.insertVertex("B");
    		graph.insertVertex("C");
    		graph.insertVertex("D");
    		graph.insertVertex("E");
    		graph.addEdges("A", "B");
    		graph.addEdges("A", "E");
    		graph.addEdges("B", "C");
    		graph.addEdges("B", "D");
    		graph.addEdges("B", "E");
    		graph.addEdges("C", "D");
    		graph.addEdges("D", "E");
    		graph.displayGraph();
    	}
    }
    

     

    控制台输出结果:
    A:B–>E
    B:A–>C–>D–>E
    C:B–>D
    D:B–>C–>E
    E:A–>B–>D

    图的相关算法

    BFS实现

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    
    public void BFS(T start) {
    	ArrayList<T> list = new ArrayList<T>(); // 存放遍历结点数列
    	LinkedList<Vertex> tempList = new LinkedList<Vertex>(); // 辅助BFS的队列
    	initialize(); //初始化所有结点访问属性为false
    	tempList.add(vertexs.get(start));
    	while (!tempList.isEmpty()) {
    		Vertex node = tempList.poll(); // 弹出队列头
    		if (!node.isVisited()) {
    			node.setVisited(true);
    			ArrayList<Vertex> neighbor = adjList.get(node.getLable()); // 获取结点node的邻接表
    			int size = neighbor.size();
    			for (int i = 0; i < size; i++) {
    				if ((!neighbor.get(i).isVisited()) && (!tempList.contains(neighbor.get(i)))) {
    					tempList.offer(neighbor.get(i)); // 将未被访问且不包含在辅助BFS队列中的结点存入队列
    				}
    			}
    			list.add(node.getLable());
    		}
    		}
    	/**
    	 * 输出遍历序列
    	 */
    	System.out.print("广度优先:");
    	int size = list.size();
    	for (int i = 0; i < size; i++) {
    		System.out.print(list.get(i));
    		if (i < size - 1) {
    			System.out.print("-->");
    		}
    	}
    	System.out.println();
    }
    

    控制台输出图A的 广度优先:A–>B–>E–>C–>D

    DFS实现

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    
    public void DFS(T start) {
    	ArrayList<T> list = new ArrayList<T>(); // 存放遍历结点数列
    	Stack<Vertex> stack = new Stack<Vertex>(); // 辅助DFS栈
    	initialize(); // 初始化所有结点访问属性为false
    	stack.push(vertexs.get(start));
    	while (!stack.isEmpty()) {
    		Vertex node = stack.pop(); //弹出栈顶元素
    		if (!node.isVisited()) {
    			node.setVisited(true);
    			ArrayList<Vertex> neighbor = adjList.get(node.getLable()); // 获取结点node的邻接表
    			int size = neighbor.size();
    			for (int i = 0; i < size; i++) {
    				if ((!neighbor.get(i).isVisited()) && (!stack.contains(neighbor.get(i)))) // 将未被访问且不包含在辅助DFS栈中的结点压入栈
    					stack.push(neighbor.get(i));
    			}
    			list.add(node.getLable());
    		}
    	}
    	System.out.print("深度优先:");
    	int size = list.size();
    	for (int i = 0; i < size; i++) {
    		System.out.print(list.get(i));
    		if (i < size - 1) {
    			System.out.print("-->");
    		}
    	}
    	System.out.println();
    }
    

    控制台输出图A的 深度优先:A–>E–>D–>C–>B

    附件

    完整代码以及相应示例图见 https://github.com/lemon2013/algorithm

    坚持原创技术分享,您的支持将鼓励我继续创作!

    展开全文
  • 相似图片搜索算法介绍

    万次阅读 2017-08-21 15:16:14
    相似图片搜索算法介绍

    前言

    之前对图片聚类有一丢丢的研究,最近发现,使用一些相似图片搜索算法也可以实现图片聚类的目标:将同类别或差不多的图片聚在一起。所以整理出相似图片搜索算法介绍这篇文章,主要介绍AutoEncoder、based CNN、Hash等算法,细分又包括:AutoEncoder、Siamese Network、2-channel、Central-surround two-stream network、aHash、pHash、dHash等算法。

    AutoEncoder

    AE作为一种无监督算法,通过encode和decode两个过程实现,当encode和decode过程均为一层时,AE很类似PCA;多层时,又有些类似神经网络。

    如上图所示,code左侧的为encode层,右侧为decode层,目的是使得输入的x和输出的x_head越接近越好,所以在误差反向传播时需要优化x和x_head的差异值。通过encode和decode两个过程,AE可以提取图片特征,不断的训练之后就可以通过得到的特征参数对相似图片进行搜索。AutoEncoder详细介绍 点击这里
    我的 一篇文章实现了AutoEncoder对MNIST数据集的特征提取; 另一篇文章实现了AutoEncoder对相似图片的搜索。

    Based CNN

    这个板块中的算法来自 这篇论文,主要介绍了Siamese Network、2-channel、Central-surround two-stream network、SSP几种算法,并对比他们之间的联系和区别。

    Siamese Network

    这个算法最初用于手写签字的识别,之后又应用在相似图片的处理上面,如下图所示,patch1和patch2为输入图片,两张图片分别经过卷积层(包括卷积、ReLU、最大池化等过程),得到两个特征向量,接着进入黄色的全连接层,最后输出两个图片的相似度。在Siamese Network算法中,两个patch在卷积层中的权值共享。
    论文中有对Siamese Network算法进行改进,变为Pseudo-siamese算法,这个算法与Siamese Network的区别为:卷积层中的权值不共享,在下图中间部分可以看到。

    2-channel

    channel这个词最先是在图片灰度上面提到的,像MNIST数据集,图片都是黑白的,channel为1,彩色图片channel为3,分为R、G、B三个channel,顾名思义,这个算法就是由两个channel组成,这两个channel就是要比较的两张图片,如下图所示,与上面Siamese Network算法的不同之处在于,这个算法合并了上面的两个卷积层,使两张图片编程一张,举个例子,有两张(1,32,32)的黑白图片,放在这个算法中,就相当于是对卷积层输入一个(2,32,32)的图片,然后在经过一层全连接,输出一个值,这个输出的值就表示两张图片的差异。

    Central-surround two-stream network

    这个算法在2-channel的基础上进行了改进,对比上下两张图,如果不考虑右侧蓝色块,仅考虑左侧的结构,和2-channel是一样的,这个算法的改进之处在于:
    首先,左侧输入的图片不再是原图,而是经过了处理,如图所示,经过了下采样,使得图像变小,Paper中介绍的原图patch大小为64*64,那么在左侧的输入为32*32。其次,右侧的输入图片为原始图片的中心部分,大小也是32*32,这样一来,左右两侧的输入图片大小相等。

    SSP

    我们平时的输入图片多为32*32、64*64、128*128这种,图片的长和宽都是确定的,如果原始图片的长和宽不确定,我们使用前需要进行预处理,这样就影响了图片的精度,SSP算法就是为了解决这个问题。

    Hash Method

    Hash算法作为大多图片搜索引擎的核心算法,其准确率和效率均很高,本板块将介绍Hash的三种核心算法:aHash、pHash、dHash。

    aHash

    此算法是基于比较灰度图每个像素与平均值来实现的。
    步骤:
    1.缩放图片:为了保留结构去掉细节,去除大小、横纵比的差异,把图片统一缩放到8*8,共64个像素的图片。
    2.转化为灰度图:把缩放后的图片转化为256阶的灰度图。
    3.计算平均值: 计算进行灰度处理后图片的所有像素点的平均值。
    4.比较像素灰度值:遍历灰度图片每一个像素,如果大于平均值记录为1,否则为0.
    5.得到信息指纹:组合64个bit位,顺序随意保持一致性即可。
    6.对比指纹:计算两幅图片的指纹,计算汉明距离(从一个指纹到另一个指纹需要变几次),汉明距离越大则说明图片越不一致,反之,汉明距离越小则说明图片越相似,当距离为0时,说明完全相同。(通常认为距离>10 就是两张完全不同的图片)

    pHash

    平均哈希算法过于严格,不够精确,更适合搜索缩略图,为了获得更精确的结果可以选择感知哈希算法,它采用的是DCT(离散余弦变换)来降低频率的方法
    步骤:
    1.缩小图片:32 * 32是一个较好的大小,这样方便DCT计算
    2.转化为灰度图:把缩放后的图片转化为256阶的灰度图。(具体算法见平均哈希算法步骤)
    3.计算DCT:DCT把图片分离成分率的集合
    4.缩小DCT:DCT是32*32,保留左上角的8*8,这些代表的图片的最低频率
    5.计算平均值:计算缩小DCT后的所有像素点的平均值。
    6.进一步减小DCT:大于平均值记录为1,反之记录为0.
    7.得到信息指纹:组合64个信息位,顺序随意保持一致性即可。
    8.对比指纹:计算两幅图片的指纹,计算汉明距离(从一个指纹到另一个指纹需要变几次),汉明距离越大则说明图片越不一致,反之,汉明距离越小则说明图片越相似,当距离为0时,说明完全相同。(通常认为距离>10 就是两张完全不同的图片)

    dHash

    相比pHash,dHash的速度要快的多,相比aHash,dHash在效率几乎相同的情况下的效果要更好,它是基于渐变实现的。
    步骤:
    1.缩小图片:收缩到9*8的大小,一遍它有72的像素点
    2.转化为灰度图:把缩放后的图片转化为256阶的灰度图。(具体算法见平均哈希算法步骤)
    3.计算差异值:dHash算法工作在相邻像素之间,这样每行9个像素之间产生了8个不同的差异,一共8行,则产生了64个差异值
    4.获得指纹:如果左边的像素比右边的更亮,则记录为1,否则为0.

    参考资料

    展开全文
  • 图像搜索算法

    千次阅读 2015-03-26 16:44:01
    对于这种图像搜索算法,一般是三个步骤: 1. 将目标图片进行特征提取,描述图像的算法很多,用的比较多的是:SIFT描述子,指纹算法函数,bundling features算法,hash function(散列函数)等。也可以根据不同的...

    对于这种图像搜索的算法,一般是三个步骤:

    1. 将目标图片进行特征提取,描述图像的算法很多,用的比较多的是:SIFT描述子,指纹算法函数,bundling features算法,hash  function(散列函数)等。也可以根据不同的图像,设计不同的算法,比如图像局部N阶矩的方法提取图像特征。

    2. 将图像特征信息进行编码,并将海量图像编码做查找表。对于目标图像,可以对分辨率较大的图像进行降采样,减少运算量后在进行图像特征提取和编码处理。

    3.  相似度匹配运算:利用目标图像的编码值,在图像搜索引擎中的图像数据库进行全局或是局部的相似度计算;根据所需要的鲁棒性,设定阈值,然后将相似度高的图片预保留下来;最后应该还有一步筛选最佳匹配图片,这个应该还是用到特征检测算法。

    其中每个步骤都有很多算法研究,围绕数学,统计学,图像编码,信号处理等理论进行研究。

    下面是阮一峰的一个最简单的实现:

    你输入Google图片的网址,或者直接上传图片,Google就会找出与其相似的图片。下面这张图片是美国女演员Alyson Hannigan。

    Google图片搜索的原理

    上传后,Google返回如下结果:

    Google图片搜索的原理

    这种技术的原理是什么?计算机怎么知道两张图片相似呢?

    根据Neal Krawetz博士的解释,原理非常简单易懂。我们可以用一个快速算法,就达到基本的效果。

    这里的关键技术叫做"感知哈希算法"(Perceptual hash  algorithm),它的作用是对每张图片生成一个"指纹"(fingerprint)字符串,然后比较不同图片的指纹。结果越接近,就说明图片越相似。

    下面是一个最简单的实现:

    第一步,缩小尺寸。

    将图片缩小到8x8的尺寸,总共64个像素。这一步的作用是去除图片的细节,只保留结构、明暗等基本信息,摒弃不同尺寸、比例带来的图片差异。

    Google图片搜索的原理

    第二步,简化色彩。

    将缩小后的图片,转为64级灰度。也就是说,所有像素点总共只有64种颜色。

    第三步,计算平均值。

    计算所有64个像素的灰度平均值。

    第四步,比较像素的灰度。

    将每个像素的灰度,与平均值进行比较。大于或等于平均值,记为1;小于平均值,记为0。

    第五步,计算哈希值。

    将上一步的比较结果,组合在一起,就构成了一个64位的整数,这就是这张图片的指纹。组合的次序并不重要,只要保证所有图片都采用同样次序就行了。

    Google图片搜索的原理

    得到指纹以后,就可以对比不同的图片,看看64位中有多少位是不一样的。在理论上,这等同于计算"汉明距离"(Hamming  distance)。如果不相同的数据位不超过5,就说明两张图片很相似;如果大于10,就说明这是两张不同的图片。

    具体的代码实现,可以参见Wote用python语言写的imgHash.py。代码很短,只有53行。使用的时候,第一个参数是基准图片,第二个参数是用来比较的其他图片所在的目录,返回结果是两张图片之间不相同的数据位数量(汉明距离)。

    这种算法的优点是简单快速,不受图片大小缩放的影响,缺点是图片的内容不能变更。如果在图片上加几个文字,它就认不出来了。所以,它的最佳用途是根据缩略图,找出原图。

    实际应用中,往往采用更强大的pHash算法和SIFT算法,它们能够识别图片的变形。只要变形程度不超过25%,它们就能匹配原图。这些算法虽然更复杂,但是原理与上面的简便算法是一样的,就是先将图片转化成Hash字符串,然后再进行比较。

    展开全文
  • 对于全局路径规划的设计,我们先要了解什么是图搜索,在此之前,要先知道什么是: 可以看到,有很多种,有无向,有向,节点之间还可以有不同的weight, 用于表述从节点与节点直接迁移的代价。 而图搜索算...

    对于全局路径规划的设计,我们先要了解什么是图搜索,在此之前,要先知道什么是图:
    在这里插入图片描述
    可以看到,图有很多种,有无向图,有向图,节点之间还可以有不同的weight, 用于表述从节点与节点直接迁移的代价。
    而图搜索算法则是把我们的搜索对象抽象成state space gragh 来处理。
    在这里插入图片描述
    基本的理论无外乎用树的理论对图进行搜索,当找到终点后在回溯这一分支,最后获得从起点到终点的路径,而可以优化的地方就是如何有效减少这些搜索,从而加速搜索,同时还要保证搜索结果的最优性。
    在这里插入图片描述
    伪代码的流程如下:
    我们会不断地更新一个open list, 我们也可以称之为container容器。用于不断地从父节点更新子节点,更新完后,将父节点放到closed集合中,表示这个点已经被搜索过。
    在这里插入图片描述
    主要的最基础的四个路径搜索算法是BFS, DFS, Dja, A*

    BFS 和 DFS的很大的一个区别就是深度优先搜索是队列搜索,先进去的先出来。 而广度优先搜索怎么堆栈,总是最后进去的先出来。
    在这里插入图片描述
    具体的说,DFS总是向最深的方向搜索,如果失败,则把这一支删除:
    在这里插入图片描述
    在这里插入图片描述
    相比之下, BFS则是以广度作为搜索优先,总是搜索最浅的层级:
    在这里插入图片描述
    在这里插入图片描述
    所以,这里可以看到,广度优先搜索会 比深度优先搜索范围更大,虽然可以绝对保证最优性结果,但是效率远不及深度优先,而深度优先的问题则在于无法保证最优。

    展开全文
  • 深度理解基本图搜索算法

    千次阅读 2015-07-25 09:25:29
    这篇随笔是在综合看了多本书,包括算法导论,人工智能等之后,写自己的一些感悟。 适合的读者:如果你已经能够思路清晰的回答以下问题,那么请直接忽略本文~ ...图搜索三种基本算法,BFS,DFS,
  • 图搜索算法(一):搜索的一般算法

    万次阅读 2012-12-29 17:46:33
    按照搜索的方式不同,图搜索一般分为树式搜索和线式搜索。两者最大的区别就在于搜索过程中所记录的轨迹不同,顾名思义,树式搜索记录的是一颗搜索树,而线式搜索是一条折线。我们一般用一个Closed表的数据结构来记录...
  • 图搜索算法UCS(一致代价搜索)通俗易懂图示详解

    千次阅读 多人点赞 2020-11-17 22:04:52
    一致代价搜索实际上是在BFS(广度优先搜索算法)的基础上进行扩展的,我们在上一篇博客图搜索算法BFS和DFS通俗易懂图示详解中提到,BFS是基于队列数据结构的,既然UCS是BFS的扩展,那么UCS一定也是基于队列的,由此...
  • 一般图搜索算法

    千次阅读 2011-09-06 09:37:59
    给出一般图搜索算法如下: */ OPEN , CLOSED Ø, PREDs , found ; while(OPEN != Ø && !found) { x 表第一个节点; OPEN ; CLOSED; if(x == T) found; else { 对节点x进行扩展,其子节点集合为{y1,y2,......
  • 参考: 清华大学出版社....内容: 使用python实现了三种不同启发函数的A*搜索算法搜索),以及宽度优先搜索和深度优先搜索,并计算扩展结点数和生成结点数,可以输出解路径。有GUI交互界面。 License: MIT ...
  • 的遍历算法 的遍历都可以理解为,将非线性结构转化为半线性结构的过程。经遍历而确定的边类型中,最重要的一类即所谓的树边,它们与所有顶点共同构成了原的一棵支撑树(森林),称作遍历树(traversal tree)。   ...
  • 矩形区域其实就是x、y左右每次加一定数值,矩形有四个坐标。 ...例如深圳地区的矩形区域是:22.449954,22.866712,113....通过这种算法我们可以做很多事情,调用对方的地图接口查询写字楼、餐厅、企业、园区等。
  • 谈到图算法和广度优先搜索,我认为首先要明白这两种算法是用来干嘛的。在这里我引用《算法图解》一书举的一个很经典的例子来讲解。 很多时候我们希望能够找出两样东西之间的最短距离,这里的距离不是单单是相距多少...
  • 前言 魔兽世界、仙剑奇侠传这类 MMRPG(Multiplayer Online Role-PlayingGame) 游戏中,有一个非常重要的功能,那就是人物角色...实际上,这是一个非常典型的路径搜索问题。人物的起点就是他当下所在的位置,终点就...
  • 【算法】图解A* 搜索算法

    千次阅读 多人点赞 2019-01-11 00:57:25
    A* 算法是启发式搜索算法,是根据Dijkstra算法改进而来。 问题引入 如下所示,S为起始(start)节点,G为目标(goal)节点。 节点之间连线是两点的路径长度,如A到E的路径长度c(A,E) = 9。 节点旁的h值时当前...
  • 图搜索的通用算法

    千次阅读 2012-01-22 07:49:44
    这里提出一个通用的图搜索算法,它允许各种用户—偏爱启发式的或盲目的,进行定制。我把这个算法叫做搜索(GRAPHSEARCH)。 下面是(第一个版本)它的定义。 GRAPHSEACH: 1) 生成一个仅包含开始节点n0的搜索...
  • 基本算法——深度优先搜索(DFS)和广度优先搜索(BFS) 安然若知 12018.07.13 08:38:53字数 753阅读 101,761 ...深度优先搜索是图论中的经典算法,利用深度优先搜索算法可以产生目标的相应...
  • 先考究一种特殊的---二叉树的深度优先搜索算法---即二叉树的递归遍历方法. 二叉树的前序遍历算法:   void TreeWalk(node* root) { if(root) { visit(root); TreeWalk(root-&gt;left); TreeWalk...
  • 基于搜索的路径规划算法

    千次阅读 2020-01-28 00:03:00
    基于搜索的路径规划算法是较为成熟和广泛使用的一种路径规划算法,常常被用于移动机器人或者游戏中的人物的路径规划。
  • 文章目录前言一、局部搜索算法(local search)二、 爬山法(HILL-CLIMBING)模拟退火(SIMULATED ANNEALING)集束搜索(Beam Search)遗传算法(Genetic algorithm)总结 前言 局部搜索算法简介 ​ 局部搜索算法是...
  • a*算法流程(只是流程)A*算法是一种在静态路网中求解最短路径最有效的直接搜索方法,也是解决许多其他搜索问题的有效算法算法中的距离估算值与实际值越接近,扩展的节点数越少, 搜索速度越快。
  • 2011年6月,Google把”相似图片搜索”正式放上了首页。你可以用一张图片,搜索互联网上所有与它相似的图片。点击搜索框中照相机的图标。 一个对话框会出现。 你输入网片的网址,或者直接上传图片,...
  • 人工智能之搜索算法

    千次阅读 多人点赞 2020-03-21 21:41:32
    通过搜索来解决问题 文章目录通过搜索来解决问题1. 什么是算法?2. 什么是搜索?3. 搜索算法3.1 如何做路径规划?3.2 搜索过...
  • 人工智能--贪婪算法(启发式搜索

    千次阅读 2020-07-06 16:08:53
    相对于来说,在树的搜索过程中,贪婪算法会遇到很多不可行解,这就需要程序能否返回到最近的一个节点,重新寻找其他的可行路径。下面通过一个示例说明贪婪最佳优先搜索和改进贪婪优化算法具体过程。 问题描述 下...
  • 智能优化算法:麻雀搜索算法-附代码

    万次阅读 多人点赞 2020-09-27 16:34:00
    2020智能优化算法:麻雀搜索算法-附代码 文章目录2020智能优化算法:麻雀搜索算法-附代码1.算法原理2.算法结果3.参考文献4.Matlab代码 摘要:麻雀搜索算法(Sparrow Search Algorithm, SSA)是于2020年提出的。SSA ...
  • A*搜索算法(python)

    千次阅读 2018-09-14 16:22:02
    先了解一下什么是A*算法。 A*搜寻算法,俗称A星算法。这是一种在图形平面上,有多个节点的路径,求出最低通过成本的算法。常用于游戏中的NPC(Non-Player-ControlledCharacter... A*算法是一种启发式搜索算法,启...
  • 相似图片搜索的三种哈希算法

    万次阅读 多人点赞 2013-03-01 04:32:00
    想必大家都用google或...此算法是基于比较灰度每个像素与平均值来实现的,最适用于缩略,放大图搜索。 步骤: 1.缩放图片:为了保留结构去掉细节,去除大小、横纵比的差异,把图片统一缩放到8*8,共64个像素的
  • 再谈启发式搜索算法

    千次阅读 2015-12-05 09:17:46
    启发式搜索算法有点像广度优先搜索,不同的是,它会优先顺着有启发性和具有特定信息的节点搜索下去 ,这些节点可能是到达目标的最好路径。 我们称这个过程为最优(best-first)或启发式搜索。 下面是其基本思想:...
  • 经典算法研究系列:八、再谈启发式搜索算法作者:July 二零一一年二月十日本文参考:I、 维基百科、II、 人工智能-09 启发式搜索、III、本BLOG内,经典算法研究系列:一、A*搜索算法----------------------------...
  • 引力搜索算法

    千次阅读 2020-07-03 21:10:37
    最近在论文中看到有学者用改进的引力搜索算法解优化问题,有一个较好的效果,于是去了解了一下这个算法。 引力搜索算法(Gravitational Search Algorithm,GSA)是Esmat Rashedi等人在2009年提出的一种随机性启发式...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 703,039
精华内容 281,215
关键字:

图搜索算法

友情链接: STM32PUCOSPLED.zip