定义:
记忆化搜索(Memory search)是指一种结合了搜索和动态规划思想的算法策略。它的基本思想是,在搜索的过程中,对于已经计算过的状态,将其结果保存下来,以便在后续的计算中可以直接使用,而不需要重新进行计算。这样可以避免大量的重复计算,提高算法的效率。
适用范围:
记忆化搜索的适用范围主要是那些需要重复计算的问题,即问题的解可以通过子问题的解来推导得到。这类问题通常具有重叠子问题的特性,即子问题会被多次求解。通过将子问题的解保存下来,记忆化搜索可以在求解过程中直接利用这些解,避免了重复的计算。
记忆化搜索的实现通常使用一个哈希表或者数组来保存已经计算过的状态的结果。在搜索的过程中,每次遇到一个新的状态,都先检查这个状态的结果是否已经在哈希表或数组中保存过。如果是,则直接使用这个结果;如果不是,则计算这个状态的结果,并将其保存到哈希表或数组中,以便后续使用。
优点和缺点:
记忆化搜索的优点主要包括:
- 避免重复计算:通过记忆已经计算过的状态的结果,避免了大量的重复计算,从而提高了算法的效率。
- 可以处理复杂的问题:记忆化搜索结合了搜索和动态规划的思想,可以处理一些比较复杂的问题,特别是那些具有重叠子问题特性的问题。
- 易于实现:记忆化搜索的实现相对简单,只需要使用一个哈希表或数组来保存已经计算过的状态的结果即可。
缺点主要包括:
- 空间复杂度较高:由于需要保存已经计算过的状态的结果,因此需要使用额外的空间来存储这些结果。这可能会导致空间复杂度较高,特别是对于大规模的问题。
- 不适用于所有问题:虽然记忆化搜索可以处理具有重叠子问题特性的问题,但并不是所有的问题都适合使用记忆化搜索。对于一些不具有重叠子问题特性的问题,记忆化搜索可能无法提高算法的效率。
- 可能存在状态爆炸的问题:在一些复杂的问题中,状态的数量可能非常大,导致哈希表或数组的大小过大,从而引发状态爆炸的问题。这可能会导致算法的效率降低,甚至无法解决问题。
总的来说,记忆化搜索是一种非常有效的算法策略,它可以显著提高算法的效率,特别是对于那些具有重叠子问题特性的问题。在实际应用中,记忆化搜索被广泛应用于各种领域,如计算机科学、运筹学、人工智能等。
有关练习题目:(【CSGRound1】天下第一)
题目背景
天下第一的 cbw 以主席的身份在 8102 年统治全宇宙后,开始了自己休闲的生活,并邀请自己的好友每天都来和他做游戏。由于 cbw 想要显出自己平易近人,所以 zhouwc 虽然是一个蒟蒻,也有能和 cbw 玩游戏的机会。
题目描述
游戏是这样的:
给定两个数 x,y,与一个模数 p。
cbw 拥有数 x,zhouwc 拥有数 y。
第一个回合:x←(x+y)modp。
第二个回合:y←(x+y)modp。
第三个回合:x←(x+y)modp。
第四个回合:y←(x+y)modp。
以此类推....
如果 x 先到 0,则 cbw 胜利。如果 y 先到 0,则 zhouwc 胜利。如果 x,y 都不能到 0,则为平局。
cbw 为了捍卫自己主席的尊严,想要提前知道游戏的结果,并且可以趁机动点手脚,所以他希望你来告诉他结果。
输入格式
有多组数据。
第一行:T 和 p 表示一共有 T 组数据且模数都为 p。
以下 T 行,每行两个数 x,y。
输出格式
共 T 行
1 表示 cbw 获胜,2 表示 zhouwc 获胜,
error
表示平局。输入输出样例
输入 #1复制
1 10 1 3
输出 #1复制
error
输入 #2复制
1 10 4 5
输出 #2复制
1
说明/提示
1≤T≤200。
1≤x,y,p≤10000。
代码详解:
#include<bits/stdc++.h> // 引入了一个头文件,包含了大多数标准库
using namespace std; // 使用标准命名空间
// 定义了一个二维数组a,大小为10001x10001,用于存储计算结果
short a[10001][10001];
// 全局变量,x和y是待计算的值,t表示测试用例的数量,p是模数
int x,y,t,p;
// fun函数用于计算给定x和y的值,并返回结果
int fun(int x,int y){
// 如果a[x][y]的值为-1,表示该位置正在计算中,直接返回-1表示错误
if(a[x][y]==-1)return -1;
// 如果a[x][y]的值不为0,表示该位置已经计算过,直接返回存储的结果
if(a[x][y])return a[x][y]; <--记忆化搜索
// 设置a[x][y]为-1,表示该位置正在计算中
a[x][y]=-1;
// 如果x为0,返回1
if(x==0)return 1;
// 如果y为0,返回2
if(y==0)return 2;
// 递归计算fun((x+y)%p, ((x+y)%p+y)%p)的值,并将结果存储在a[x][y]中
// 注意:这里可能存在语法错误,正确的递归调用应该是fun(((x+y)%p, (x+y)%p+y))
return a[x][y]=fun((x+y)%p,((x+y)%p+y)%p);
}
int main()
{
// 读取测试用例的数量t和模数p
scanf("%d%d",&t,&p);
// 循环处理每个测试用例
while(t--){
int arr=0; // 定义一个变量arr,用于存储计算结果
// 读取x和y的值
scanf("%d%d",&x,&y);
// 调用fun函数计算x和y的值,并将结果存储在arr中
arr=fun(x,y);
// 根据arr的值输出不同的结果
if(arr==-1)printf("error\n");
if(arr==1)printf("1\n");
if(arr==2)printf("2\n");
}
return 0; // 程序结束
}