进阶搜索算法 学习笔记

这篇具有很好参考价值的文章主要介绍了进阶搜索算法 学习笔记。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

搜索——进阶搜索算法

DATE 20231031:补充一道好题 P4872 OIer们的东方梦(Dijkstra 分层图最短路)。

前情提要~

  1. 双向广搜、双向深搜
  2. 堆优化的 Dijkstra
  3. 一颗小小的 A-STAR
  4. 不大聪明的 IDDFS(IDS)
  5. 可爱的 IDA-STAR

广搜、深搜

这是进阶搜索算法,不说了直接上例题:

以“P1514 引水问题”为例:

点击查看代码
const int N = 510;
const int dx[4] = {-1, 0, 0, 1};
const int dy[4] = {0, -1, 1, 0};
int n, m, a[N][N];
bool vis[N][N][N];
vector<pair<int, int>> nodes;
int main()
{
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            scanf("%d", a[i] + j);

    queue<pair<int, int>> q;
    for (int start = 1; start <= m; ++start)
    {
        q.push({1, start});
        vis[0][1][start] = true;
        vis[start][1][start] = true;

        while (q.size())
        {
            auto now = q.front();
            int x = now.first, y = now.second;
            q.pop();

            for (int i = 0; i < 4; ++i)
            {
                int tx = x + dx[i];
                int ty = y + dy[i];

                if (tx < 1 || tx > n || ty < 1 || ty > m || vis[start][tx][ty])
                    continue;
                if (a[tx][ty] < a[x][y])
                    q.push({tx, ty}), vis[0][tx][ty] = 1, vis[start][tx][ty] = 1;
            }
        }

        vector<int> g;
        for (int i = 1; i <= m; ++i)
            if (vis[start][n][i])
                g.push_back(i);

        if (g.size())
            nodes.push_back({g.front(), g.back()});
    }

    int connected = 0;
    for (int i = 1; i <= m; ++i)
        connected += vis[0][n][i];

    if (connected < m)
        printf("0\n%d\n", m - connected);
    else
    {
        sort(nodes.begin(), nodes.end());

        int now = 1, res = 0;
        for (size_t i = 0; i < nodes.size(); ++i, ++res)
        {
            while (nodes[i].first <= now)
                ++i;
            now = nodes[i - 1].second + 1;
        }

        printf("1\n%d\n", res);
    }

    return 0;
}

双向广搜、双向深搜

算法思想

  • 在搜索的时候,搜索出来的树太大了
  • 从起始状态和目标状态同时开始搜索一定层数
  • 把搜索出来的所有状态扔到 hash 表里面,看看有没有重复的
  • 能够提升一倍答案的效率,比如原来复杂度是 \(O(2^n)\),现在可以变成 \(O(2^{n / 2})\),相当于复杂度开根号

代码

以“U319719 八城堡问题”为例:

点击查看代码
using namespace std;

const int N = 21;
const int M = (1 << 20) + 1;

int n, m;
int a[N];

int n2, ans;
int g[M];
int f[N][M];

void dfs1(int k, int now)
{
    if (g[now] > m)
        return;
    if (k > n2)
    {
        int r = now ^ ((1 << n) - 1);
        if (g[now] == m)
            ++f[m][0];
        for (int t = r; t; t = (t - 1) & r)
            ++f[g[now]][t];
        return;
    }

    dfs1(k + 1, now);
    for (int i = 1; i <= n; ++i)
    {
        int t = 1 << (n - i);
        if ((a[k] & t) && (now & t) == 0)
            dfs1(k + 1, now | t);
    }
}

void dfs2(int k, int now)
{
    if (g[now] > m)
        return;
    if (k > n)
    {
        ans += f[m - g[now]][now];
        return;
    }

    dfs2(k + 1, now);
    for (int i = 1; i <= n; ++i)
    {
        int t = 1 << (n - i);
        if ((a[k] & t) && (now & t) == 0)
            dfs2(k + 1, now | t);
    }
}

int main()
{
    for (int i = 1; i < M; ++i)
        g[i] = g[i & (i - 1)] + 1;

    scanf("%d%d", &n, &m);
    while (n && m)
    {
        memset(f, 0, sizeof f);
        ans = 0;

        char line[N];
        for (int i = 1; i <= n; ++i)
        {
            scanf("%s", line);
            for (int j = 1; j <= n; ++j)
                a[i] = a[i] << 1 | (line[j - 1] == 'H');
        }

        n2 = n >> 1;
        dfs1(1, 0);
        dfs2(n2 + 1, 0);

        printf("%d\n", ans);
        scanf("%d%d", &n, &m);
    }
    return 0;
}

堆优化的 Dijkstra

算法思想

考虑当前走过的距离,不考虑剩下的距离,当前走的少的优先考虑

优先队列里不允许出现相同的元素,但是同一个元素可以入队和出队多次,当第二及更多次入队是,必然是遇到了更加优化的路径(到起点的距离更近)

代码

以“P3371 P4779 单源最短路径”为例:

点击查看代码
typedef pair<int, int> PII;

const int INF = 2147483647;
const int N = 1e5 + 10;
const int M = 5e5 + 10;

int n, m;

int h[N], e[M], w[M], ne[M], idx;

void add(int u, int v, int d)
{
	e[idx] = v;
	w[idx] = d;
	ne[idx] = h[u];
	h[u] = idx++;
}

int dis[N];
bool st[N];

void dijkstra(int s)
{
	memset(dis, 0x3f, sizeof dis);
	dis[s] = 0;

	priority_queue<PII, vector<PII>, greater<PII>> heap;
	heap.push({0, s});

	while (heap.size())
	{
		int v = heap.top().second, d = heap.top().first;
		heap.pop();

		if (st[v])
			continue;
		st[v] = true;

		for (int i = h[v] ; i != -1 ; i = ne[i])
		{
			int j = e[i];
			if (dis[j] > d + w[i])
			{
				dis[j] = d + w[i];
				heap.push({dis[j], j});
			}
		}
	}
}

unordered_map<int, int> dist[N];

int main()
{
	memset(h, -1, sizeof(h));

	int s;
	scanf("%d %d %d", &n, &m, &s);

	int u, v, w;
	for (int i = 1 ; i <= m ; ++i)
	{
		scanf("%d %d %d", &u, &v, &w);
		if (dist[u].count(v))
			dist[u][v] = min(dist[u][v], w);
		else
			dist[u][v] = w;
	}

	for (int i = 1 ; i <= n ; ++i)
		for (PII j : dist[i])
			add(i, j.first, j.second);

	dijkstra(s);

	for (int i = 1 ; i <= n ; ++i)
	{
		if (dis[i] == 0x3f3f3f3f)
			dis[i] = INF;
		printf("%d ", dis[i]);
	}
	return 0;
}

一颗小小的 A-STAR

基础知识

  • 估价函数 \(f(i) = g(i) + h(i)\),每次要选取 \(f(i)\) 最小的更新
  • \(g(i)\):从起始状态到当前状态 \(i\) 的代价
  • \(h(i)\):从当前状态 \(i\) 到目标状态的估计代价

基础思想

好东西:https://zhuanlan.zhihu.com/p/54510444

重点在设计估价函数,估价函数 \(h(i)\) 若选取不当,则可能找不到解,或找到的解也不是最优解。

  • 定义 \(h^*(i)\) 为从当前状态 \(n\) 到目标状态的实际代价
  • 必须满足 \(h(i) \le h^*(i)\),否则嘿嘿嘿
  • 估计总是过于乐观的

常见的估价函数

对于网格形式的图,有以下这些启发函数可以使用:

  1. 如果图形中只允许朝上下左右四个方向移动,则可以使用曼哈顿距离
function heuristic(node) =
	dx = abs(node.x - goal.x)
	dy = abs(node.y - goal.y)
	return D * (dx + dy)
  1. 如果图形中允许朝八个方向移动,则可以使用对角距离
function heuristic(node) =
	dx = abs(node.x - goal.x)
	dy = abs(node.y - goal.y)
	return D * (dx + dy) + (D2 - 2 * D) * min(dx, dy)
	// 这里的D2指的是两个斜着相邻节点之间的移动代价
  1. 如果图形中允许朝任何方向移动,则可以使用欧几里得距离
function heuristic(node) =
	dx = abs(node.x - goal.x)
	dy = abs(node.y - goal.y)
	return D * sqrt(dx * dx + dy * dy)
  1. 对于类似八数码问题的,可以使用各数码使用距离目标位置的曼哈顿距离之和
int f(string state)
{
	int res = 0;
	for (int i = 0; i < 9; ++i)
	{
		if (state[i] != '0')
		{
			int t = tar[state[i] - '1'];
			res += abs(i / 3 - t / 3) + abs(i % 3 - t % 3);
		}
	}
	return res;
}
  1. 对于数列(二维也可以)问题的,可以使用有多少个元素位置不正确,或其前驱、后继不正确
int f(string state)
{
	int res = 0;
	for (int i = 0; i < 9; ++i)
		res += state[i] != gend[i];
	return res;
}
int f()
{
	int res = 0;
	for (int i = 0; i + 1 < n; ++i)
		if (q[i + 1] != q[i] + 1)
			++res;
	return (res + 2) / 3;
}

设计要求

  • 不要太过分就好,一般来说没问题的
  • 脑洞要大

代码

以“P1379 八数码问题”为例:

点击查看代码
typedef pair<int, string> PIS;

const int dx[4] = {-1, 0, 0, 1};
const int dy[4] = {0, -1, 1, 0};

const char op[4] = {'u', 'l', 'r', 'd'};

string gend = "123804765";
int tar[9] = {0, 1, 3, 5, 8, 7, 6, 3};

int f(string state)
{
	int res = 0;
	for (int i = 0; i < 9; ++i)
	{
		if (state[i] != '0')
		{
			int t = tar[state[i] - '1'];
			res += abs(i / 3 - t / 3) + abs(i % 3 - t % 3);
		}
	}
	return res;
}

string a_star(string start, string end = gend)
{
	unordered_map<string, int> dist;
	unordered_map<string, pair<char, string>> prev;
	priority_queue<PIS, vector<PIS>, greater<PIS>> heap;

	dist[start] = 0;
	heap.push({f(start), start});

	while (heap.size())
	{
		auto t = heap.top();
		heap.pop();

		string state = t.second;
		if (state == end)
			break;

		int x, y;
		for (int i = 0; i < 9; ++i)
		{
			if (state[i] == '0')
			{
				x = i / 3, y = i % 3;
				break;
			}
		}

		string source = state;
		for (int i = 0; i < 4; ++i)
		{
			int a = x + dx[i];
			int b = y + dy[i];
			if (a < 0 || a > 2 || b < 0 || b > 2)
				continue;
			state = source;
			swap(state[x * 3 + y], state[a * 3 + b]);
			if (!dist.count(state) || dist[state] > dist[source] + 1)
			{
				dist[state] = dist[source] + 1;
				prev[state] = {op[i], source};
				heap.push({dist[state] + f(state), state});
			}
		}
	}

	string res;
	while (end != start)
	{
		res = prev[end].first + res;
		end = prev[end].second;
	}
	return res;
}

int main()
{
	string start;
	cin >> start;
	// 保证可以达到目标
	// int cnt = 0;
	// for (int i = 0 ; i < 9 ; ++i)
	//	if (start[i] != '0')
	//		for (int j = i + 1 ; j < 9 ; ++j)
	//			if (start[j] != '0' && start[i] > start[j])
	//				++cnt;
	// if (cnt & 1 == 0)
	//	cout << "-1" << endl;
	// else
	cout << a_star(start).size() << endl;
	return 0;
}

不大聪明的 IDDFS(IDS)

算法思想

迭代加深是一种每次限制搜索深度的深度优先搜索,目的是寻找最优解。

  • 给出一个限制 limit,规定:当 搜索层数 > limit 时直接剪枝
  • 在最外层 循环枚举 limit,如果无解就继续

特点

缺点:重复计算

与BFS的区别:BFS 的基础是队列,空间复杂度大,当状态比较多或者单个状态比较大时,迭代加深就类似于用 DFS 方式实现的 BFS,空间复杂度相对较小。

在大多数的题目中,广度优先搜索还是比较方便的,而且容易判重。当发现广度优先搜索在空间上不够优秀,而且要找最优解的问题时,就应该考虑迭代加深。

代码

以“LOJ10021 Addition Chains(加成序列问题)”为例:

点击查看代码
const int N = 110;

int read()
{
    int num = 0, flag = 1;
    char ch = getchar();
    for (; !isdigit(ch); ch = getchar())
        if (ch == '-')
            flag = -1;
    for (; isdigit(ch); ch = getchar())
        num = (num << 3) + (num << 1) + ch - '0';
    return num * flag;
}

int n;
int path[N];

bool iddfs(int k, int limit)
{
    if (k > limit)
        return false;
    if (path[k - 1] == n)
        return true;

    bool st[N] = {0};
    for (int i = k - 1; i >= 0; --i)
    {
        for (int j = i; j >= 0; --j)
        {
            int s = path[i] + path[j];
            if (s > n || s <= path[k - 1] || st[s])
                continue;
            st[s] = true;
            path[k] = s;
            if (iddfs(k + 1, limit))
                return true;
        }
    }
    return false;
}

int main()
{
    path[0] = 1;
    while (n = read())
    {
        int depth = 1;
        while (!iddfs(1, depth))
            ++depth;
        for (int i = 0; i < depth; ++i)
            printf("%d ", path[i]);
        putchar('\n');
    }
    return 0;
}

可爱的 IDA-STAR

算法思想

IDA-STAR 为采用了迭代加深(IDDFS)算法的 A-STAR 算法。

所以,在一般的问题中是这样使用 IDA-star 算法的:

  • (类似 IDDFS)循环枚举 limit,当 \(h(i) + g(i) >\) limit 时, 就停止继续往下搜索
  • 写成代码就是:if depth + h() > limit then return;
  • 没了

估价函数

往上门口(见 A-STAR)

特点

  • 省空间:各种游戏求最少步数,普通搜索会爆炸
  • 省时间:不需要判重,不需要排序,利于深度剪枝
  • 费时间(?):每次深度变大都要再次从头搜索,有时可能双向广搜会更快

代码

以“P2324 骑士精神”为例:

点击查看代码
const int dx[8] = {-2, -2, -1, -1, 1, 1, 2, 2};
const int dy[8] = {-1, 1, -2, 2, -2, 2, -1, 1};
const int gcount[2][5] = {{0, 1, 2, 4, 5},
                          {5, 4, 2, 1, 0}};
string mp[5];

int f()
{
    int res = 0;
    for (int i = 0; i < 5; ++i)
    {
        for (int j = 0; j < gcount[0][i]; ++j)
            if (mp[i][j] != '0')
                ++res;
        for (int j = 0; j < gcount[1][i]; ++j)
            if (mp[i][5 - j - 1] != '1')
                ++res;
    }
    return res;
}

bool ida_star(int now, int limit)
{
    if (now + f() > limit)
        return false;
    if (!f())
        return true;

    int a, b;
    for (int i = 0; i < 5; ++i)
        for (int j = 0; j < 5; ++j)
            if (mp[i][j] == '*')
                a = i, b = j;

    for (int i = 0; i < 8; ++i)
    {
        int x = a + dx[i];
        int y = b + dy[i];
        if (x < 0 || x > 4 || y < 0 || y > 4)
            continue;
        swap(mp[a][b], mp[x][y]);
        if (ida_star(now + 1, limit))
            return true;
        swap(mp[a][b], mp[x][y]);
    }
    return false;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;

    while (T--)
    {
        for (int i = 0; i < 5; ++i)
            cin >> mp[i];

        int limit = 0;
        while (limit <= 15 && !ida_star(0, limit))
            ++limit;

        if (limit > 15)
            limit = -1;
        printf("%d\n", limit);
    }

    return 0;
}

练习题

见:https://www.luogu.com.cn/training/401467

Reference

[1] https://github.com/huzecong/oi-slides
[2] https://zhuanlan.zhihu.com/p/54510444
[3] https://oi-wiki.org/
[4] https://www.acwing.com/文章来源地址https://www.toymoban.com/news/detail-703746.html

到了这里,关于进阶搜索算法 学习笔记的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • AcWing算法学习笔记:动态规划(背包 + 线性dp + 区间dp + 计数dp + 状态压缩dp + 树形dp + 记忆化搜索)

    算法 复杂度 时间复杂度0(nm) 空间复杂度0(nv) 代码 算法 通过滚动数组对01背包朴素版进行空间上的优化 f[i] 与 f[i - 1]轮流交替 若体积从小到大进行遍历,当更新f[i, j]时,f[i - 1, j - vi] 已经在更新f[i, j - vi]时被更新了 因此体积需要从大到小进行遍历,当更新f[i, j]时,f[i - 1,

    2024年02月21日
    浏览(43)
  • C++ 树进阶系列之探讨深度搜索算法查找环的细枝末节

    对于 基环树 的讲解,分上、下 2 篇,上篇以理解连通分量、环以及使用深度搜索算法检查连通性和环为主,下篇以基于基环树结构的应用为主。 什么是基环树? 所谓基环树指由 n 个节点 n 条边所构建而成的连通图 。 如下图所示,树结构中共有 7 个节点, 6 条边。此时在树

    2024年02月02日
    浏览(30)
  • 深度学习实战20(进阶版)-文件智能搜索系统,可以根据文件内容进行关键词搜索,快速找到文件

    大家好,我是微学AI,今天给大家带来深度学习实战项目-文件智能搜索系统,文件智能搜索系统是一种能够帮助用户通过文件的内容快速搜索和定位文件的软件系统。 随着互联网和数字化技术的普及,数据和信息呈现爆炸式增长的趋势,文件管理和搜索变得越来越困难。传统

    2024年02月13日
    浏览(45)
  • 深度优先搜索(DFS)(算法笔记)

    本文内容基于《算法笔记》和官方配套练题网站“晴问算法”,是我作为小白的学习记录,如有错误还请体谅,可以留下您的宝贵意见,不胜感激。 深度优先搜索是一种枚举所有完整路径以遍历所有情况的搜索方法,总是以“深度”作为前进的。实现方式是有很多,最

    2024年02月08日
    浏览(53)
  • 深度学习图像搜索算法-图像搜索引擎

    深度学习图像搜索算法-图像搜索引擎 文章目录 ✍🏻作者简介: 机器学习,深度学习,卷积神经网络处理,图像处理 🚀B站项目实战:https://space.bilibili.com/364224477 😄 如果文章对你有帮助的话, 欢迎评论 💬点赞👍🏻 收藏 📂加关注+ 🤵‍♂代码获取:@个人主页 给定一个

    2024年02月03日
    浏览(79)
  • Acwing-基础算法课笔记之搜索与图论

    bellman-ford算法适用于负权边的图,求 1 到 n 的最多经过k条边的最短距离。 如图所示: 1 2 3 dist 0 ∞ infty ∞ ∞ infty ∞ ⇓ Downarrow ⇓ 1 2 3 dist 0 1 ∞ infty ∞ ⇓ Downarrow ⇓ 1 2 3 dist 0 1 2 此过程中出现了串联的结果,所以是错误的,此时需要进行备份操作。 备份操作如下: 为了

    2024年01月20日
    浏览(55)
  • 算法毕业设计 深度学习图像搜索算法-图像搜索引擎(源码分享)

    今天学长向大家分享一个毕业设计项目 毕业设计 深度学习图像搜索算法-图像搜索引擎(源码分享) 项目运行效果: 毕业设计 深度学习图像搜索算法-图像搜索引擎 项目获取: https://gitee.com/sinonfin/algorithm-sharing 图像检索:是从一堆图片中找到与待匹配的图像相似的图片,就是

    2024年02月03日
    浏览(59)
  • 算法毕设分享 深度学习图像搜索算法-图像搜索引擎(源码分享)

    今天学长向大家分享一个毕业设计项目 毕业设计 深度学习图像搜索算法-图像搜索引擎(源码分享) 项目运行效果: 毕业设计 深度学习图像搜索算法-图像搜索引擎 项目获取: https://gitee.com/sinonfin/algorithm-sharing 图像检索:是从一堆图片中找到与待匹配的图像相似的图片,就是

    2024年02月04日
    浏览(59)
  • 读改变未来的九大算法笔记07_搜索引擎

    1.1.1.1. 惠普(Hewlett-Packard) 1.2.1.1. 从一间卧室开始的,空间很快就不够用了,于是他们转移到了车库 1.3.1.1. 谷歌 1.3.1.1.1. 门洛帕克车库 2.1.1.1. 美国工程师范内瓦·布什(Vannevar Bush) 2.1.1.2. 论文《诚若所思》(As We May Think) 2.1.1.3. 一台被称作麦麦克斯(memex)的机器

    2024年02月08日
    浏览(73)
  • 「学习笔记」记忆化搜索

    由于我一直对搜索情有独钟,因此,如果能写记忆化搜索的绝不会写 for 循环 DP。 文章部分内容来自 (texttt{OI-Wiki}) 记忆化搜索是一种通过记录已经遍历过的状态的信息,从而避免对同一状态重复遍历的搜索实现方式。 因为记忆化搜索确保了每个状态只访问一次,它也是一

    2024年02月08日
    浏览(38)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包