搜索算法思考

概述:本文主要讲述一些搜索算法的使用,以及其中奥妙思想的思考。

一:广度搜索与深度搜索---BFS与DFS

1:实现算法导论中的BSF

#include <deque>
#define MAX 1000000
struct Node
{
    int d;
    int p;
    int color;
    int id;
};
int _tmain(int argc, _TCHAR* argv[])
{
    Node arrNode[8];
    int arrGrid[8][8];
    deque<Node> q;
    for(int i=0;i<8;i++)
    {
        arrNode[i].color=0;
        arrNode[i].d=MAX;
        arrNode[i].p=MAX;
        arrNode[i].id=i;
    }
    for(int i=0;i<8;i++)
        for(int j=0;j<8;j++)
            arrGrid[i][j]=0;

    arrGrid[0][1]=1;
    arrGrid[0][3]=1;
    arrGrid[1][2]=1;
    arrGrid[3][4]=1;
    arrGrid[3][5]=1;
    arrGrid[4][5]=1;
    arrGrid[4][6]=1;
    arrGrid[5][6]=1;
    arrGrid[5][7]=1;
    arrGrid[6][7]=1;

    arrNode[0].color=1;
    arrNode[0].d=0;
    q.push_back(arrNode[0]);
    while(!q.empty())
    {
        Node u=q.front();
        q.pop_front();
        for(int i=0;i<8;i++)
        {
            if(arrGrid[u.id][i]==1||arrGrid[i][u.id]==1)
            {
                Node v=arrNode[i];
                if(v.color==0)
                {
                    arrNode[v.id].color=1;
                    arrNode[v.id].p=u.id;
                    arrNode[v.id].d=u.d+1;
                    q.push_back(arrNode[v.id]);
                }
                arrNode[u.id].color=2;
            }
        }
    }

    return 0;
}

2:实现算法导论中的DSF

int Map[6][6];
int Visit[6];
int Pre[6];
int Dis[6];
int Fin[6];
int time;

void DFS();
void DFSVisit(int u);
int _tmain(int argc, _TCHAR* argv[])
{
    for(int i=0;i<6;i++)
        for(int j=0;j<6;j++)
            Map[i][j]=0;
    Map[0][1]=1;
    Map[0][2]=1;
    Map[1][3]=1;
    Map[2][1]=1;
    Map[3][2]=1;
    Map[4][3]=1;
    Map[4][5]=1;
    Map[5][5]=1;

    for(int i=0;i<6;i++)
    {
        Visit[i]=0;
        Pre[i]=-1;
        Dis[i]=0;
        Fin[i]=0;
    }
    time=0;

    DFS();

    for(int i=0;i<6;i++)
    {
        cout<<Dis[i]<<"/"<<Fin[i]<<" ";
    }
    cout<<endl;
    for(int i=0;i<6;i++)
    {
        cout<<Pre[i]<<" ";
    }
    cout<<endl;
    char cc;
    cin>>cc;
    return 0;
}
//6个点的深度DFS;;;;
void DFS()
{
    for(int u=0;u<6;u++)
        if(Visit[u]==0)
            DFSVisit(u);
}
void DFSVisit(int u)
{
    Visit[u]=1;//表示灰色
    time++;
    Dis[u]=time;
    for(int i=0;i<6;i++)
    {
        if(Visit[i]==0&&Map[u][i]>0)
        {
            Pre[i]=u;
            DFSVisit(i);
        }
    }
    Visit[u]=2;//为黑色
    time++;
    Fin[u]=time;
}

共同点思想:不会陷入死循环,通过标记为黑而达到;都会搜索到通过非白达到。也就是需要达到全部搜索到则需要对节点标识位;使用结构体数据结构表示,用矩阵表示图;

不同点:BSF是一层一层的搜索,每次弄一次层,就必须知道该层所有房间;

DFS是像走迷宫,直到碰到墙位置才停住,而返回前一个元素,选择没有走过的路。这样可以全部走完整个地图。

 

搜索:这种适合枚举中选出自己想要的情况。

 

第二:Bellman_Ford算法与Dijkstra算法

1:Bellman_Ford算法

思想:从某个源头出发,寻找到达各个点的最小距离。会得到一个最小路径的树;

显然:该最小路径中,不能存在环,比如是正环,则通过取掉一条边而导致会变小,从而矛盾;

         若为负环:则通过不断走环值,也会导致值变小,而矛盾。

那么最小路径存在可能性就是不存在环路,那么这个最小路径表明是简单路径,对于点是V个的,又是简单路径,显然二点只有一个路径,则只能是V-1个边了。----针对这V-1个边,是路径中最小的情况,那么通过松弛,由于每次松弛都会得到一个边,故而需要V-1次松弛。由于V-1次松弛就能够得到V-1边。每次松弛都是对整个边的。

复杂度是O(VE)

实现思想:边用结构体来表示;点结构体的数组表示含有前驱和距离,下标为点标号;通过V-1次松弛达到求出了每个点的最小距离,以及一颗最小路径树。---可以判断出是否存在最小路径,可以求出最小路径-----且对边权值没有要求,有向。

实现如下:

 

#define MAX 1000000
struct Node
{
    int d;
    int p;
};
struct Edge
{
    int u;
    int v;
    int w;
};

int _tmain(int argc, _TCHAR* argv[])
{
    Node node[5];
    Edge edge[10];

    for(int i=0;i<5;i++)
    {
        node[i].d=MAX;
        node[i].p=MAX;
    }
    node[0].d=0;//源

    edge[0].u=0;
    edge[0].v=1;
    edge[0].w=6;

    edge[1].u=0;
    edge[1].v=2;
    edge[1].w=7;

    edge[2].u=1;
    edge[2].v=3;
    edge[2].w=5;

    edge[3].u=1;
    edge[3].v=4;
    edge[3].w=-4;

    edge[4].u=1;
    edge[4].v=2;
    edge[4].w=8;

    edge[5].u=2;
    edge[5].v=3;
    edge[5].w=-3;

    edge[6].u=2;
    edge[6].v=4;
    edge[6].w=9;

    edge[7].u=3;
    edge[7].v=1;
    edge[7].w=-2;

    edge[8].u=4;
    edge[8].v=0;
    edge[8].w=2;

    edge[9].u=4;
    edge[9].v=3;
    edge[9].w=7;

    for(int i=0;i<4;i++)
    {//V-1次
        for(int j=0;j<10;j++)
        {
            int sum=node[edge[j].u].d+edge[j].w;
            if(sum<node[edge[j].v].d)
            {
                node[edge[j].v].d=sum;
                node[edge[j].v].p=edge[j].u;
            }
        }
    }

    for(int j=0;j<10;j++)
    {
        int sum=node[edge[j].u].d+edge[j].w;
        if(sum<node[edge[j].v].d)
        {
            cout<<"False"<<endl;
            return 0;
        }
    }
    cout<<"True"<<endl;

    return 0;
}

 

2:Dijkstra算法

思想:该算法没有上个算法通用,但是效率高,时间复杂度可达到O(Vlg(V)+E);但是有限定,就是权重不能为负值。

过程思想:从源头出发,对每个节点处的边松弛,直到最后。由于是正值,所以又是从源头开始的,一旦确定它了,那么它就是最小距离了,因为不会通过环而让其更小了,这是因为没有负值的边。-----每次确定是取没有确定的最小值作为这个确定值。

实现如下:

#define MAX 1000000
struct Node
{
    int d;
    int p;
    int color;
};

int _tmain(int argc, _TCHAR* argv[])
{
    int edge[5][5];
    for(int i=0;i<5;i++)
        for(int j=0;j<5;j++)
            edge[i][j]=MAX;
    edge[0][1]=10;
    edge[0][2]=5;
    edge[1][2]=2;
    edge[1][3]=1;
    edge[2][1]=3;
    edge[2][3]=9;
    edge[2][4]=2;
    edge[3][4]=4;
    edge[4][0]=7;
    edge[4][3]=6;

    Node node[5];
    for(int i=0;i<5;i++)
    {
        node[i].d=MAX;
        node[i].p=MAX;
        node[i].color=0;
    }
    node[0].d=0;

    for(int i=0;i<5;i++)
    {
    //取最小值
        int minid;
        int min=MAX+100;
        for(int j=0;j<5;j++)
        {
            if(min>node[j].d&&node[j].color==0)
            {
                min=node[j].d;
                minid=j;
            }
        }

        node[minid].color=1;
        //松弛
        for(int j=0;j<5;j++)
        {
            if(edge[minid][j]+node[minid].d<node[j].d&&node[j].color==0)
            {
                node[j].d=edge[minid][j]+node[minid].d;
                node[j].p=minid;

            }
        }
    }

    return 0;
}

搜索算法思考

时间: 07-15

搜索算法思考的相关文章

数据结构与算法之四 搜索算法

目标 在本章中,你将学习: 使用线性搜索技术搜索数据和二叉搜索技术搜索数据 线性搜索: 是最简单的搜索方法,也称作顺序搜索,包括将用该条目逐一与列表中的条目进行比较,线性搜索通过比较所需的元素与列表中第一个元素进行. 如果值不匹配: 则所需的元素将与列表中的第二个元素作比较. 如果值还是不匹配: 则所需的元素将与列表中的第三个元素作比较. 这个过程将一直持续下去,直到: 找到所需的元素或到达列表的未尾为止. 使用线性搜索算法编写一个算法以搜索员工记录列表中给定的员工的工号: 1.  读取要搜索的

优化人员应如何应对搜索算法调整

优化人员应如何应对搜索算法调整,三点钟的时候,没等人去叫,阿北自己出现在了会议室的门口.从这点看,他还是保持着一个技术人员的习惯,而不像一个CEO. 不知道为什么,技术出身的阿北,别人谈起来却每每提到说他的一墙碟,两墙书,三大洲的车船票,把他描绘成一个文艺青年,把豆瓣描绘成一个文艺青年聚集地. 文艺也可能是来自商业世界的委婉评语:这家成立十年,拥有过亿用户的网站,一直没有盈利.人们认为豆瓣已经慢了,老了,甚至被移动互联网抛弃了. 阿北说,豆瓣做过尝试,犯过错误,现在找到了新方向. 在2014年的

五子棋AI算法第二篇-极大极小值搜索算法

AI实现的基本思路-极大极小值搜索算法 五子棋看起来有各种各样的走法,而实际上把每一步的走法展开,就是一颗巨大的博弈树.在这个树中,从根节点为0开始,奇数层表示电脑可能的走法,偶数层表示玩家可能的走法. 假设电脑先手,那么第一层就是电脑的所有可能的走法,第二层就是玩家的所有可能走法,以此类推. 我们假设平均每一步有50种可能的走法,那么从根节点开始,往下面每一层的节点数量是上一层的 50被,假设我们进行4层思考,也就是电脑和玩家各走两步,那么这颗博弈树的最后一层的节点数为 50^4 = 625W

我要好offer之 搜索算法大总结

1. 二分搜索 详见笔者博文:二分搜索的那些事儿,非常全面 2. 矩阵二分搜索 (1) 矩阵每行递增,且下一行第一个元素大于上一个最后一个元素 (2) 矩阵每行递增,且每列也递增 3. DFS 深度优先搜索 适用场景: (1) 输入数据:如果是 递归数据结构(如单链表.二叉树),则一定可以使用DFS (2) 求解目标:必须走到最深处(例如二叉树,必须走到叶子节点)才能得到一个解,这种情况一般适合用DFS 思考步骤: (1) DFS最常见的3个问题:求可行解的总数.求任一个可行解.求所有可行解 (

像计算机科学家一样思考Python (第2版)pdf

下载地址:网盘下载 内容简介  · · · · · · 本书以培养读者以计算机科学家一样的思维方式来理解Python语言编程.贯穿全书的主体是如何思考.设计.开发的方法,而具体的编程语言,只是提供了一个具体场景方便介绍的媒介. 全书共21章,详细介绍Python语言编程的方方面面.本书从基本的编程概念开始讲起,包括语言的语法和语义,而且每个编程概念都有清晰的定义,引领读者循序渐进地学习变量.表达式.语句.函数和数据结构.书中还探讨了如何处理文件和数据库,如何理解对象.方法和面向对象编程,如何使用

『嗨威说』算法设计与分析 - 算法第二章上机实践报告(二分查找 / 改写二分搜索算法 / 两个有序序列的中位数)

本文索引目录: 一.PTA实验报告题1 : 二分查找 1.1 实践题目 1.2 问题描述 1.3 算法描述 1.4 算法时间及空间复杂度分析 二.PTA实验报告题2 : 改写二分搜索算法 2.1 实践题目 2.2 问题描述 2.3 算法描述 2.4 算法时间及空间复杂度分析 三.PTA实验报告题3 : 两个有序序列的中位数 3.1 实践题目 3.2 问题描述 3.3 算法描述 3.4 算法时间及空间复杂度分析 四.实验心得体会(实践收获及疑惑) 一.PTA实验报告题1 : 二分查找 1.1 实践

[一些基础算法的小心得] -- 二分搜索算法

对分搜索算分也叫二分搜索算法也叫,英文则是binary-search  algorithm.其概念非常的基础,这里不再描述.但问题是我们能否不加思考的写出一个二分搜索算法并一次运行成功呢? 我们知道其核心部分的伪码非常简单(短): 并且我们也知道,对于一个规模为n的已排序数组,任何基于比较的搜索算分所需最坏情况时间为O(n). 那么下面这种算法是否正确呢?如果正确的话,最坏情况时间是什么? 那么下面这种算法呢? 以上三种写法,你能区分出哪种是正确的哪种是不正确的吗,不正确的部分是哪里如何修改呢.

搜索算法入门详解

什么是搜索算法 搜索算法是利用计算机的高性能来有目的的穷举一个问题解空间的部分或所有的可能情况,从而求出问题的解的一种方法.现阶段一般有枚举算法.深度优先搜索.广度优先搜索.A*算法.回溯算法.蒙特卡洛树搜索.散列函数等算法.在大规模实验环境中,通常通过在搜索前,根据条件降低搜索规模:根据问题的约束条件进行剪枝:利用搜索过程中的中间解,避免重复计算这几种方法进行优化. 搜索方式 首先给大家扫个盲在搜索中,不仅仅只有常见的递归式搜索,也存在着一部分正向迭代式搜索,但是在真正的使用中递归式搜索占到了

关于迭代測试的一些思考

作者:朱金灿 来源:http://blog.csdn.net/clever101 一个软件的功能的越来越多,怎样建立一个规范的測试流程来保证对开发的功能进行充分的測试,是摆在我们面前的难题.在改动bug中经常会出现一种"按下葫芦浮起瓢"情形--改动了A模块的bug,却造成了原来測试没有问题的B模块出现了新的问题.这就促使我们思考:怎样保证測试的百分百的覆盖率.为此我设想一种迭代測试和迭代公布的流程.这个流程详细是这种:全部功能測试分为常规功能測试和新功能測试.所谓常规功能測试是指之前測