首页 > 其他分享 >搜索笔记

搜索笔记

时间：2023-07-23 17:24:55浏览次数：41  
标签：结点 return int 笔记 current step 搜索

搜索

双向搜索

双向同时搜索

定义：

双向同时搜索的基本思路是从状态图上的起点和终点同时开始进行BFS 和 DFS。

如果发现搜索的两端相遇了，那么可以认为是获得了可行解。

模版实现：

if(start==finish)
      return 0;
初始化visited数组里每个值为0; //这里visited值为1则为向后搜索过的值，为2则为向前搜索过的值
初始化起始点start.step=true; //这里step属性为真则表示为某一搜索步数中的最后一个点,例如对于poj1915中第2步有八个点，只有第八个点的step为true,其余为false
初始化目标点finish.step=true;
visited[start]=true;
visited[finish]=true;
queue<type> frontSearch;       //记录从前向后搜索的队列
queue<type> backSearch;       //记录从后向前搜索的队列
fstep=0;                                 //记录从前向后搜索的步数
bstep=0;                                   //记录从后向前搜索的步数
frontSearch.push(start);
backSearch.push(finish);
while(!frontSearch.empty() || !backSearch.empty())
    {
       if(!frontSearch.empty())
         {
           do{
                current=frontSearch.front();//从队列中弹出当前搜索的点
                frontSearch.pop();
                for(每一个current的相邻点v)
                {
                    if(visited[v]==2)return fstep+bstep+1;//如果遇到了从后向前搜索搜过的点则终止，并且返回总步数
                    if(!visited[v])
                        {
                            visited[v]=1;
                            frontSearch.push(v);
                        }
                }
              }while(!current.step)               //同一步的点已经全部搜完，结束循环
                        fstep++;                                //增加从前向后搜索的步数
                        current=frontSearch.front();
                        frontSearch.pop();
                        current.step=true;
                        frontSearch.push(current);      //将当前步数最后一个点的step属性设为true；
 
         }
                  if(!backSearch.empty())
                {
                    do{
                     		current=backSearch.front();//从队列中弹出当前搜索的点
                        	backSearch.pop();
                        	for(每一个current的相邻点v)
                        	{
                            	if(visited[v]==1) return fstep+bstep+1;//如果遇到了从前向后搜索搜过的点则终止，并且返回总步数
                            	if(!visited[v])
                            	{
                                	visited[v]=2;
                                	backSearch.push(v);
                            	}
                        	}
                    	}
                     while(!current.step)               //同一步的点已经全部搜完，结束循环
                        bstep++;                                //增加从后向前搜索的步数
                        current=backSearch.front();
                        backSearch.pop();
                        current.step=true;
                        backSearch.push(current);      //将当前步数最后一个点的step属性设为true；
 
                }
	}

Meet in the middle

警示后人：

Meet in the middle ≠ 二分搜索（因为二分搜索有个译名是折半搜索）

定义与作用：

Meet in the middle 常见翻译是「折半搜索」、「 双向搜索」、「中途相遇」以下称为折半搜索

适用于输入数据较小，但是还没有小到直接使用暴力的情况

过程：

折半搜索顾名思义，当然要折半啊，将整个搜索过程分为两半，分别搜索，然后合并

性质：

暴力往往是指数级别的，但是改用 折半搜索后，时间复杂度可以从 $O(a^ b)$ 降到 $O(a^{b/2})$。

经典例题：

快乐的例题时间又到了，看看是哪个幸运的题目呢？

不错是我们亲爱的 P2962 [USACO09NOV] Lights G

大意：

有n盏灯，每盏灯与若干盏灯相连，每盏灯上都有一个开关，如果按下一盏灯的开关，这盏灯以及与之相连的所以灯的开关状态会改变，一开始所有灯是关着的，你需要将所以灯打开，且最小开关次数，1 ≤ n ≤ 35

解题思路 ：

若直接暴力殴打本题，那么本题会还你一个时间复杂度$O(2n)$将你重重击倒在地，然后一个TLE完全打败你，但是，你先把它踢倒后，再把它打趴下，就简简单单的$O(n2)$，也就是折半搜索，找出 1 到 mid 的开关能够到达的状态，再找出只使用另一半开关能到达的状态，如果前半段和后半段开启的灯互补，将这两段合并起来就得到了一种将所有灯打开的方案。具体实现时，可以把前半段的状态以及到达每种状态的最少按开关次数储存在$map$中，搜索后半段时，每搜出一种方案，就把它与互补的第一段方案合并来更新答案。

代码：
#include <bits/stdc++.h>

using namespace std;

int n, m, ans = 0x7fffffff;
map<long long, int> f;
long long a[40];

int main() {
  cin >> n >> m;
  a[0] = 1;
  for (int i = 1; i < n; ++i) a[i] = a[i - 1] * 2;  // 进行预处理

  for (int i = 1; i <= m; ++i) {  // 对输入的边的情况进行处理
    int u, v;
    cin >> u >> v;
    --u;
    --v;
    a[u] |= ((long long)1 << v);
    a[v] |= ((long long)1 << u);
  }

  for (int i = 0; i < (1 << (n / 2)); ++i) {  // 对前一半进行搜索
    long long t = 0;
    int cnt = 0;
    for (int j = 0; j < n / 2; ++j) {
      if ((i >> j) & 1) {
        t ^= a[j];
        ++cnt;
      }
    }
    if (!f.count(t))
      f[t] = cnt;
    else
      f[t] = min(f[t], cnt);
  }

  for (int i = 0; i < (1 << (n - n / 2)); ++i) {  // 对后一半进行搜索
    long long t = 0;
    int cnt = 0;
    for (int j = 0; j < (n - n / 2); ++j) {
      if ((i >> j) & 1) {
        t ^= a[n / 2 + j];
        ++cnt;
      }
    }
    if (f.count((((long long)1 << n) - 1) ^ t))
      ans = min(ans, cnt + f[(((long long)1 << n) - 1) ^ t]);
  }

  cout << ans;

  return 0;
}

启发式搜索

定义：

启发式搜索是一种在普通搜索算法的基础上引入了启发式函数的搜索算法。

作用

启发式函数的作用是基于已有的信息对搜索的每一个分支选择都做估价，进而选择分支。简单来说，启发式搜索就是对取和不取都做分析，从中选取更优解或删去无效解。

（估价函数）

例题：

P1048 [NOIP2005 普及组] 采药 （srds 我怎么记得这是个01背包？？？）

题目大意：

有N种物品和一个容量为W的背包，每种物品有重量$w_ i$和价值$v_i$两种属性，要求选若干个物品（每种物品只能选一次）放入背包，使背包中物品的总价值最大，且背包中物品的总重量不超过背包的容量。(果不其然它可以用背包做，在这里不展示了)

阶梯思路：

我们写一个估价函数$f$，可以剪掉所有无效的$0$枝条（就是剪去大量无用不选枝条）。

估价函数$f$的运行过程如下：

我们在取的时候判断一下是不是超过了规定体积（可行性剪枝）；在不取的时候判断一下不取这个时，剩下的药所有的价值 + 现有的价值是否大于目前找到的最优解（最优性剪枝）。

代码：
#include <bits/stdc++.h>

using namespace std;

const int N = 105;
int n, m, ans;

struct Node {
  int a, b;  // a 代表时间，b 代表价值
  double f;
} node[N];

bool operator<(Node p, Node q) { return p.f > q.f; }

int f(int t, int v) {  // 计算在当前时间下，剩余物品的最大价值
  int tot = 0;
  for (int i = 1; t + i <= n; i++)
    if (v >= node[t + i].a) 
    {
      v -= node[t + i].a;
      tot += node[t + i].b;
    } else
      return (int)(tot + v * node[t + i].f);
  return tot;
}

void work(int t, int p, int v) {
  ans = max(ans, v);
  if (t > n) return;                         // 边界条件：只有n种物品
  if (f(t, p) + v > ans) work(t + 1, p, v);  // 最优性剪枝
  if (node[t].a <= p) work(t + 1, p - node[t].a, v + node[t].b);  // 可行性剪枝
}

int main() {
  scanf("%d %d", &m, &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d %d", &node[i].a, &node[i].b);
    node[i].f = 1.0 * node[i].b / node[i].a;  // f为性价比
  }
  sort(node + 1, node + n + 1);  // 根据性价比排序
  work(1, m, 0);
  printf("%d\n", ans);
  return 0;
}

迭代加深搜索

定义：

迭代加深是一种 每次限制搜索深度的 深度优先搜索

目的：

找最优解

等等，既然是要找最优解，那么BFS不是TOP 1？no no no，想想它那要爆炸的空间复杂度吧，但是，迭代加深类似于用 DFS 方式实现的 BFS， 空间复杂度较小

模版代码：

每次限定一个maxdep 最大深度，使得搜索树的深度不超过 maxdep。

for(R int maxdep = 1; maxdep <= 题目中给的最大步数; maxdep ++)
{
    dfs(0, maxdep);// 0 为出入函数中当前步数，maxdep 为传入的最大深度
    if(success) break; // 如果搜索成功则会在 DFS 函数中将 success 赋值为 1。
}

使用范围:

  1. 在有一定的限制条件时使用（例如骑士精神中“如果能在15步以内（包括15步）到达目标状态，则输出步数，否则输出−1。）。

  2. 题目中说输出所以解中的任何一组解即可。

  3. A, IDA

A*

定义：

是一种在图形平面上，对于有多个节点的路径求出最低通过成本的算法。它属于图遍历和最佳优先搜索算法，亦是BFS的改进。

过程：

定义起点 s , 终点 t, 从起点（初始状态）开始的距离函数 g(x)，到终点（最终状态）的距离函数 h(x)，h^*(x) ，以及每个点的估价函数 f(x) = g(x) + h(x)。

A* 算法每次从优先队列中取出一个f 最小元素，燃火更新相邻的状态。

如果 h ≤ h，则A算法能找到最优解。

上述条件下，如果 h满足三角形不等式，则A*算法不会将重复结点加入队列。

当$h = 0 时，A* 算法变为 Dijistra

当$h = 0 并且权变为1 时变为BFS。

例题：

快乐的例题时光又到了

今天的幸运儿是 P4467 [SCOI2007] k短路

题目大意：

按顺序求一个有向图上从节点s 到结点 t 的所有路径最小的前任意多（不妨设 k ）个

分析：

非常非常容易发现是用 A* 去做（不然为什么是A*的标准例题？？？）

初始状态为处于结点 s，最终状态为处于结点t，距离函数为从 s 到当前结点已经走过的距离，估值函数为从当前结点到结点t 至少要走过的距离，依旧是当前结点到结点 t 的最短路。（等等，这就最短路了？没错，就是最短路）

就这样，我们在预处理的时候反向建图，计算出结点t到所有点的最短路，然后将初始状态塞入优先队列，每次取出f(x) = g(x) + h(x) 最小的一项，计算出其所连结点的信息并将其塞入队列，当我们第k次走到结点 t 时，也就算出了结点 s 到结点 t 的 k 短路。

由于设计的距离函数和估价函数，每个状态需要存储两个参数，当前结点 x 和已经走过的距离 v。

我们可以在此基础上加一点点小优化：由于只需要求第 k 短路，所以当我们第k + 1次或以上走到该结点时，直接跳过该状态。因为前面的 k 次走到这个点的时候肯定能因此构造出第 k 条路径，所以之后再加边更无必要。

代码：

#include <bits/stdc++.h>

using namespace std;

const int maxn = 5010;
const int maxm = 400010;
const double inf = 2e9;
int n, m, k, u, v, cur, h[maxn], nxt[maxm], p[maxm], cnt[maxn], ans;
int cur1, h1[maxn], nxt1[maxm], p1[maxm];
double e, ww, w[maxm], f[maxn];
double w1[maxm];
bool tf[maxn];

void add_edge(int x, int y, double z) {  // 正向建图函数
  cur++;
  nxt[cur] = h[x];
  h[x] = cur;
  p[cur] = y;
  w[cur] = z;
}

void add_edge1(int x, int y, double z) {  // 反向建图函数
  cur1++;
  nxt1[cur1] = h1[x];
  h1[x] = cur1;
  p1[cur1] = y;
  w1[cur1] = z;
}

struct node {  // 使用A*时所需的结构体
  int x;
  double v;

  bool operator<(node a) const { return v + f[x] > a.v + f[a.x]; }
};

priority_queue<node> q;

struct node2 {  // 计算t到所有结点最短路时所需的结构体
  int x;
  double v;

  bool operator<(node2 a) const { return v > a.v; }
} x;

priority_queue<node2> Q;

int main() {
  scanf("%d%d%lf", &n, &m, &e);
  while (m--) {
    scanf("%d%d%lf", &u, &v, &ww);
    add_edge(u, v, ww);   // 正向建图
    add_edge1(v, u, ww);  // 反向建图
  }
  for (int i = 1; i < n; i++) f[i] = inf;
  Q.push({n, 0});
  while (!Q.empty()) {  // 计算t到所有结点的最短路
    x = Q.top();
    Q.pop();
    if (tf[x.x]) continue;
    tf[x.x] = true;
    f[x.x] = x.v;
    for (int j = h1[x.x]; j; j = nxt1[j]) Q.push({p1[j], x.v + w1[j]});
  }
  k = (int)e / f[1];
  q.push({1, 0});
  while (!q.empty()) {  // 使用A*算法
    node x = q.top();
    q.pop();
    cnt[x.x]++;
    if (x.x == n) {
      e -= x.v;
      if (e < 0) {
        printf("%d\n", ans);
        return 0;
      }
      ans++;
    }
    for (int j = h[x.x]; j; j = nxt[j])
      if (cnt[p[j]] <= k && x.v + w[j] <= e) q.push({p[j], x.v + w[j]});
  }
  printf("%d\n", ans);
  return 0;
}

IDA*

定义：采用了迭代加深算法的 A* 算法

与 A* 的区别：

优点：

  1. 不需要判重，不需要排序，利于深度剪枝。

  2. 空间需求减少：每个深度下实际是一个DFS，不过有深度限制，使用DFS可以减少空间消耗。

缺点
  1. 重复搜索：即使前后两次搜索相差微小，回溯过程中每次深度变大都要再次从头搜索。

模版实现：

bool IDAstar(int u,int deep){
	if(predict() > deep){//预测以最快的速度都得超过剩余深度才能达到终点
		return false;
	}
	if(isTarget(u)){//如果u是目标
		//记录u
		return true;
	}
	bool flag = false;
	if(deep > 0){//还可以继续加深
		for(int i = head[u]; i; last[i]){//访问u的连接结点
			int v = to[i];
			flag = flag|IDAstar(v, deep-1);//只要有一个是true就行,所以用|
		}
	}
	return flag;
}

例题：

这可不是普通的例题，这是王维诗里的例题

P2324 [SCOI2005] 骑士精神

题目大意：

没什么好概括的，就是个马走日呗。

分析：

  1. 由于答案较小且要求最优解，可以使用迭代加深搜索。

  2. 直接搜会完美TLE，需要加一些剪枝。

  3. 假设我们当前枚举的深度为 d，已经走了 k 步，那么如果已经不能在 k - d 步内走完，那么可以直接剪枝掉。

  4. 因此，我们希望能够计算一个状态最少多少步走完。计算的越接近真实值，剪枝优化力度越大。

  5. 但是注意，计算的必须要 <= 真实值，否则会剪掉不该剪的。

方案：

记录一下当前状态和目标状态的不同个数记为 k。

  1. 当 k = 0 时， 代表已经完成了

  2. 当空格位置相同时，至少需要 k + 1 步

  3. 否则，至少需要 k - 1 步。

代码实现：
#include <bits/stdc++.h>

using namespace std;

int read()
{
    int f = 1,x = 0;
    char ss = getchar();
    while(ss < '0' || ss > '9'){if(ss == '-')f = -1;ss = getchar();}
    while(ss >= '0' && ss <= '9'){x = x * 10 + ss - '0';ss = getchar();}
    return f * x;
}

int n;
int ans[6][6] =
{{0,0,0,0,0,0},
 {0,1,1,1,1,1},
 {0,0,1,1,1,1},
 {0,0,0,2,1,1},
 {0,0,0,0,0,1},
 {0,0,0,0,0,0}};
int nxtx[] = {1,1,2,2,-2,-2,-1,-1};
int nxty[] = {2,-2,1,-1,1,-1,2,-2};
int a[10][10], k;
int judge;

int check()
{
    for(int i = 1;i <= 5; ++i)
    for(int j = 1; j <= 5; ++j)
    if(ans[i][j] != a[i][j])return 0;
    return 1;
}

int test(int step)
{
    int cnt = 0;
    for(int i = 1;i <= 5; ++i)
    for(int j = 1;j <= 5; ++j)
    if(ans[i][j] != a[i][j]){ if(++cnt + step > k) return 0;}
    return 1;
}

void A_star(int step,int x,int y,int pre)//pre记录上一步怎么到当前状态
{
    if(step==k){ if(check())judge=1; return;}
    if(judge) return;
    for(int i=0;i<8;++i)
    {
        int nx=x+nxtx[i],ny=y+nxty[i];
        if(nx<1||nx>5||ny<1||ny>5||i+pre==7) continue;//加入了上述的最优性剪枝
        swap(a[x][y],a[nx][ny]);
        if(test(step)&&!judge) A_star(step+1,nx,ny,i);//A*估价再向下搜索
        swap(a[x][y],a[nx][ny]);
    }
}

int main()
{
    n=read();
    while(n--)
    {
        int x,y; judge=0;
        for(int i=1;i<=5;++i)
        {
            char ss[7]; scanf("%s",&ss);
            for(int j=0;j<5;++j)
            if(ss[j]=='*') a[i][j+1]=2,x=i,y=j+1;
            else a[i][j+1]=ss[j]-'0';
        }
        for(k=1;k<=15;++k)
        {
            A_star(0,x,y,-1);
            if(judge) { printf("%d\n",k); break;}
        }
        if(!judge)printf("-1\n");
    }
    return 0;
}

标签：结点,return,int,笔记,current,step,搜索
From： https://www.cnblogs.com/Auditorymoon-yue/p/17575275.html

相关文章

  • 3b1b 线性代数本质 学习笔记
    导航向量基向量特征向量矩阵行列式逆矩阵矩阵与方程组秩满秩列空间零空间核点积叉积基变换向量空间中的箭头\(\vec{v}\)可以自由移动/一般以原点为起点有序的数字列表\(\begin{bmatrix}a\\\vdots\\b\end{bmatrix}\)相加相乘有意义的东西......
  • C#学习笔记 —— LINQ
    LINQ1、什么是LINQ使用LINQ可以轻松查询对象集合LINQ代表语言集成查询LINQ是.NET框架的扩展，允许我们使用SQL查询数据库的类似方式来查询数据集合LINQ可以从数据库、对象集合、XML文档中查询数据2、LINQ提供程序对于每一种数据源类型，一定有根据该数据源类型实现LI......
  • 在尚硅谷学习docker 笔记
    尚硅谷docker学习笔记1.docker简介（基础篇）2.docker的安装3.docker的常用命令3.1帮助启动类命令3.2镜像命令3.3容器命令4.对docker镜像的深入理解4.1镜像的一些重要概念4.2docker镜像commit操作案例4.3本地镜像发布到阿里云/私有库5.docker容器数据卷（实现持久......
  • 公司财报分析（读书笔记）
    一、财报财报：一般分为一季报、半年报（中报）、三季报（三季报）、年报（年报）四种。我国上市公司一般每年四次披露财务报表，分别是一季报、中报、三季报和年报。一季报和三季报是未经审计的财务报表，中报和年报是经审计的财务报表。季报和年报区别：季报是未经审计的财务报表，年报是经审......
  • 暑假OI做题笔记
    P1525关押罪犯题意翻译：给定一张图，将图中结点分为两个互补的集合，求集合间边权最小值知识点：并查集做法：对权值排序，尽量分成两个不同的集合（如果一方无敌人，则另一方成为其敌人；否则将另一方丢到另一监狱里面），出现矛盾时的权值即为答案P2024食物链知识点：并查集做法：把每个动物分成......
  • 《Maven实战》笔记（长文警告⚠️
    本文是《Maven实战》的读书笔记，实战代码仓库：https://github.com/goSilver/mvn_in_action第五章坐标和依赖5.1坐标的定义Maven定义了这样一组规则：世界上任何一个构件都可以使用Maven坐标唯一标识，Maven坐标的元素包括groupId、artifactId、version、packaging、classifier。只......
  • 数据结构练习笔记——顺序栈的基本操作
    顺序栈的基本操作【问题描述】按照要求完成顺序栈的设计【输入形式】无【输出形式】2019181716151413121110987654321#include<iostream>usingnamespacestd;#include<stdlib.h>#include<stdio.h>#defineSTACKSIZE10#defineINCRE2......
  • 网络流学习笔记
    1.一些基本定义网络网络是指一个有向图\(G=(V,E)\)。每条边\((u,v)\inE\)都有一个权值\(c(u,v)\)，称之为容量（Capacity），当\((u,v)\notinE\)时有\(c(u,v)=0\)。其中有两个特殊的点：源点（Source）\(s\inV\)和汇点（Sink）\(t\inV,(s\neqt)\)。流设\(f(u,v)\)定义在二元组......
  • 读数据压缩入门笔记09_多媒体数据压缩
    1. 压缩分类1.1. 多媒体数据压缩（media-specificcompression）1.2. 通用压缩（generalpurposecompression）2. 有损压缩算法2.1. 为了使数据压缩得更小，可以牺牲多媒体的质量这样的数据转换2.2. 针对特定的多媒体文件2.2.1. 针对图像文件的算法就不太适用于音频文件2.3.......
  • Django学习笔记：第三章D的路由和视图
    1.网站的入口--路由和视图URL是网站Web服务的入口。用户在浏览器输入URL发出请求后，django会根据路由系统，运行对应的视图函数，然后返回信息到浏览器中。1.1认识路由创建项目时，会自动生成urls.文件，文件中定义了项目的路由信息，成为项目的路由解析入口。在自建的应用中可以手动配置......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99