ACM之搜索

1.什么是搜索(算法)?

搜索算法是利用计算机的高性能来有目的的穷举一个问题的部分或所有的可能情况,从而求出问题的解的一种方法。搜索过程实际上是根据初始条件和扩展规则构造一棵解答树并寻找符合目标状态的节点的过程。

给一个实例来了解这两种算法:

2.深度优先搜索(DFS)

一般形容深度搜索就是不撞南墙不回头,这个形容算非常贴切了,因为它相当于按照一定的顺序不断地走,直到走到终点位置,然后形成一种解,判断这种解符不符合我们题目的最优解。

那我们如何实现呢?首先,我们先规定它走的顺序,我们先让他向下,直到撞墙不能再向下的时候改变方向,我们用递归实现

1.什么是搜索(算法)?

搜索算法是利用计算机的高性能来有目的的穷举一个问题的部分或所有的可能情况,从而求出问题的解的一种方法。搜索过程实际上是根据初始条件和扩展规则构造一棵解答树并寻找符合目标状态的节点的过程。

给一个实例来了解这两种算法:

2.深度优先搜索(DFS)

一般形容深度搜索就是不撞南墙不回头,这个形容算非常贴切了,因为它相当于按照一定的顺序不断地走,直到走到终点位置,然后形成一种解,判断这种解符不符合我们题目的最优解。

那我们如何实现呢?首先,我们先规定它走的顺序,我们先让他向下,直到撞墙不能再向下的时候改变方向,我们用递归实现

这种情况我们就可以有多种选择从A走出。而我们又不知道该怎么走才能到达G点,那么我们选择一直走我们没走过的路,这样就有可能到达G。 比如,我们可以从A到达B,C,D三个点,这是我们选择E点。 当我们从A走到E后,又可以到B,C,D,F四个点,于是我们走到B点。 当我们到达B过后,发现有三条路,分别指向A,C,E三点。 因为我们不走回头路!所以只能走到C点。 当我们走到C过后,有通往B,E,G的三个点的路,我们就可以直接走到G点了。

下面是深搜思路

1.把所有点标记为“未走过”;//把数组全标记为0或者其他

2.找到起点,终点并看看可以走到哪里;//准备循环

3.选择一节点并判断本节点是否走出地图;//

4.判断这一节点走过没啊;//3、4两步是判断走到该节点是否合法

5.如果没走过就走进该节点;//标记该节点

6.再寻找下一个节点;//深入下一层搜索

7.走到头了就可以回头了//得到返回这就可以回溯了

模板:

#include <iostream>
#include <cstdio>
using namespace std;
void dfs(/*起始坐标*/){
    if(/*找到出口*/){
        //操作
        return ; 
    }
    for(/*循环遍历所有方向*/){
        if(/*新的坐标不符合条件*/)
            continue;
        //操作
        dfs(/*继续向下搜索新的坐标*/);
        //回溯 
    } 
}
int main(){
    //读入数据 
    dfs(/*起点坐标*/);
    
    return 0;
}

help庞学姐:

#include<stdio.h>
int n,m;
char mp[51][51];
int vis[51][51];
int dx[]={-1,1,0,0},dy[]={0,0,1,-1};
int ans=0,step=0,min=999999;
void dfs(int x,int y,int step){
    if(x<0||x>=n||y<0||y>m) return ;
    if(x==n-1&&y==m-1){ans=1;
    if(step<min) min=step;
    return ;}
    for(int i=0;i<4;i++){
        int nowx=x+dx[i];
        int nowy=y+dy[i];
        if(mp[nowx][nowy]=='*'&&vis[nowx][nowy]==0){
            vis[nowx][nowy]=1;
            dfs(nowx,nowy,step+1);
            vis[nowx][nowy]=0;
        }
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++)
    scanf("%s",mp[i]);
    dfs(0,0,0);
    printf("%d",min);
    return 0;
}

其实这里的代码看上去好像很复杂很繁琐,但是只要仔细一想,就可以看懂,深度搜索就是把所有的路都走一遍然后最短的路程就出来了,控制比如第一步

通过一个个的搜索和条件约束就可以使算法按我们的意图运行

3.广度优先搜索(BFS)

广度优先搜索算法(Breadth-First Search,BFS)是一种盲目搜寻法,目的是系统地展开并检查图中的所有节点,以找寻结果。换句话说,它并不考虑结果的可能位置,彻底地搜索整张图,直到找到结果为止。BFS并不使用经验法则算法。

广度优先搜索让你能够找出两样东西之间的最短距离,不过最短距离的含义有很多!

假设你经营着一个芒果农场,需要寻找芒果销售商,以便将芒果卖给他。在Facebook,你与芒果销售商有联系吗?为此,你可在朋友中查找。

这种查找很简单。首先,创建一个朋友名单

然后,依次检查名单中的每一个人,看看他是否是芒果销售商。

重点 假设你没有朋友是芒果销售商,那么你就必须在朋友的朋友中查找。

在这个过程中就要用到队列的思想

先从你开始,关系表为下图

先概述一下这种算法的工作原理。

但这样可能会出现一些问题,Peggy既是Alice的朋友又是Bob的朋友,因此她将被加入队列两次:一次是在添加Alice的朋友时,另一次是在添加Bob的朋友时。因此,搜索队列将包含两个Peggy。

但你只需检查Peggy一次,看她是不是芒果销售商。如果你检查两次,就做了无用功。因此,检查完一个人后,应将其标记为已检查,且不再检查他。 如果不这样做,就可能会导致无限循环。假设你的人际关系网类似于下面这样。

检查一个人之前,要确认之前没检查过他,这很重要。为此,你可使用一个列表来记录检查过的人。

首先,需要使用代码来实现图。图由多个节点组成。 每个节点都与邻近节点相连,如果表示类似于“你→Bob”这样的关系呢?好在你知道的一种结构让你能够表示这种关系,它就是散列表! 记住,散列表让你能够将键映射到值。在这里,你要将节点映射到其所有邻居。

引用 https://blog.csdn.net/qq_37482202/article/details/89513877

依然用help庞小姐作为例子

这道题的广度搜索源代码:

#include<bits/stdc++.h>
using namespace std;
int n,m;
struct node {
    int x,y,step;
    node(int _a,int _b,int _c){x=_a,y=_b,step=_c;}
};
string mp[57];
int vis[57][57];
int dx[]={-1,1,0,0};
int dy[]={0,0,-1,1};
int bfs()
{
    queue<node> q;
    q.push(node(0,0,0));
    while(!q.empty()){
        node f=q.front();
        q.pop();

        for(int i=0;i<4;i++){
            int nowx=f.x+dx[i];
            int nowy=f.y+dy[i];

            if(nowx<0||nowy<0||nowx>=n||nowy>=m)
                continue;
            if(nowx==n-1&&nowy==m-1)
                return f.step+1;

            if(mp[nowx][nowy]=='*'&&vis[nowx][nowy]==0)
            {
                q.push(node(nowx,nowy,f.step+1));
                vis[nowx][nowy]=1;
            }
        }
    }
}
int main()
{
    cin>>n>>m;
    for(int i=0;i<n;i++) cin>>mp[i];

    cout<<bfs();

    return 0;
}

可能有人也看出来了,为什么这里的算法不需要像深度搜索那样,整个min,就可以得到最小值了呢? 这是因为每一步都打上了标记,每一步都是基于前面的尝试得到的最优解,所以不存在去考虑什么最优解,这也是广度搜索比深度搜索好的方面,在实际运行时可以极大的缩减时间,但是占用内存较大,深度搜索刚刚好反过来。

有时候面对题目的时候真的觉得深度搜索的局限性太高了,比如求x->y的时候,用深度搜索真的不如广度搜索,比如求2->37结果是6,但是广度搜索就是一直走下去,如果你拟规定的边界不太好的话,可能还输出不了 但是,广度搜索真的比较好用,他会挨个挨个寻找,这样比较好,他的挨个挨个找并不是毫无根据的,他通过一些关系紧密联系在一起的规律找。


下面的内容比较深奥,建议好好掌握上面的再来掌握下面的(更新中)

4.爬山法(Hill Climbing)

5.最佳优先算法(Best-first search strategy)

6.回溯法 (Backtracking)

步骤:

算法改进:搜索剪枝

回溯法框架:

递归法

迭代法

7.分支限界算法(Branch-and-bound Search Algorithm)

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 《搜索和推荐中的深度匹配》——1.2 搜索和推荐中匹配统一性

    Garcia-Molina等【1】指出,搜索和推荐中的根本问题是识别满足用户信息需求的信息对象。还表明搜索(信息检索)和推荐(信息过滤)是同一枚硬币的两个方面,...

    用户1621453
  • 学界 | 2018年ACM杰出会员公布,华人学者占四分之一

    ACM 杰出会员必须具备至少 15 年专业经验和连续 5 年专业会员资格,并在计算领域取得了杰出成就或做出巨大贡献。今年美国计算机学会一共为 49 位科学家授予...

    机器之心
  • 动态 | 2018 ACM 杰出科学家名单最新公布,12 位华裔学者上榜

    AI 科技评论:日前,ACM(国际计算机学会)公布了 2018 年度 ACM 杰出科学家名单,全球共有 49 名研究人员入选。其中,华裔学者的表现非常出色,上榜...

    AI科技评论
  • 重磅!2018 ACM 杰出科学家名单最新公布,12 位华人学者上榜

    雷锋网AI 科技评论:日前,ACM(国际计算机学会)公布了 2018 年度 ACM 杰出科学家名单,全球共有 49 名研究人员入选。其中,华人学者的表现非常出色...

    昱良
  • 信息标记

    soup.find_all(…)等价于soup(…) .find_all(…)等价于(…)

    Cloud-Cloudys
  • 深入搜索之结构化搜索

    结构化搜索是指针对具有内在结构的数据进行检索的过程。比如日期、时间和数字都是结构化的,它们有精确的格式。文本也是可以 格式化的,比如彩色笔的颜色可以有red、g...

    开发架构二三事
  • 《搜索和推荐中的深度匹配》——2.5 延伸阅读

    Query重构是解决搜索中查询文档不匹配的另一种方法,即将Query转换为另一个可以进行更好匹配的Query。Query转换包括Query的拼写错误更正。例如,...

    用户1621453
  • 机器之心论文解读:可用于十亿级实时检索的循环二分嵌入模型(RBE)

    论文链接:https://arxiv.org/pdf/1802.06466.pdf

    机器之心
  • 《搜索和推荐中的深度匹配》——经典匹配模型 2.1 匹配学习

    已经提出了使用传统的机器学习技术进行搜索中的查询文档匹配和推荐中的用户项目匹配的方法。这些方法可以在一个更通用的框架内形式化,我们称之为“学习匹配”。除了搜索和...

    用户1621453
  • 《搜索和推荐中的深度匹配》——2.3 搜索中的潜在空间模型

    接下来,我们以潜在空间为基础介绍匹配模型。【1】中找到了搜索中语义匹配的完整介绍。具体来说,我们简要介绍了在潜在空间中执行匹配的代表性搜索方法,包括偏最小二乘(...

    用户1621453
  • 地表最强14大超级程序员,游戏开发者比肩谷歌天才

    虽然我们没办法真正证明谁是在世程序员中谁最牛,但总有开发人员不停讨论这个话题。ITworld网站在各种相关论坛里研究输入设备及编码器,看看有没有谁是大家普遍赞同...

    企鹅号小编
  • 【学术盛宴 】多媒体顶级会议ACM Multimedia 2017 China Pre-conference论文宣讲研讨会

    【导读】第25届ACM国际多媒体会议(ACM International Conference on Multimedia, 简称ACMMM)于2017年10月...

    WZEARW
  • 独家 | 一文读懂社交网络分析-上(附学习资源)

    (点击可查看大图) 本文主要阐述: 社交网络的结构特性与演化机理 社交网络群体行为形成与互动规律 社交网络信息传播与演化机理 浏览后四章的内容请见下篇(2017...

    数据派THU
  • ACM MM 2020大奖项出炉!南开获最佳论文奖,西安交大获最佳学生论文奖

    刚刚!第28届ACM国际多媒体会议(ACM MM)最佳论文奖、最佳学生论文奖、最佳demo奖、 最佳开源软件奖在内的所有多媒体领域大奖都已出炉。

    AI科技评论
  • 新手ACM算法学习建议

    一般要做到50行以内的程序不用调试、100行以内的二分钟内调试成功。ACM主要是考算法的,主要时间是花在思考算法上,不是花在写程序与debug上。

    ACM算法日常
  • CMU博士、姚班助理教授张焕晨获SIGMOD Jim Gray博士论文奖,华人首次

    SIGMOD 年度吉姆 · 格雷博士论文奖旨在表彰上一年度数据库领域的最优秀博士论文。以前,该奖项被称为 SIGMOD 博士论文奖。2008 年,为了纪念 19...

    机器之心
  • 业界 | 前微软亚洲研究院资深研究员梅涛博士加盟京东,担纲计算机视觉与多媒体研发

    机器之心
  • 前阿里P10大神AI创业,主打决策智能,从《星际争霸II》开始

    在北京大学第42届ACM-ICPC国际大学生程序设计竞赛全球总决赛现场,一款基于《星际争霸II》的AI人机协作挑战赛也在同期进行,主办方启元世界,一家主打决策智...

    量子位
  • 干货 | 携程个性化推荐算法实践

    作者简介 携程基础业务研发部-数据产品和服务组,专注于个性化推荐、自然语言处理、图像识别等人工智能领域的先进技术在旅游行业的应用研究并落地产生价值。目前,团队已...

    携程技术

扫码关注云+社区

领取腾讯云代金券