搜索、DP.pptx

搜索、动态规划
搜索
搜索
盲目搜索算法
深度优先搜索(DFS)
广度优先搜索(BFS)
迭代加深搜索(Iterative Deepening)
限制最大深度DMAX搜索,无答案就继续增大DMAX,用于搜索树又宽又深,可行解却不是很深的题目。
迭代加宽搜索(Iterative Broadening)(限制BMAX,应用不多)
启发式搜索
A*算法
IDA*算法( Iterative Deepening A-star——迭代加深A*算法)
盲目搜索算法
搜索——DFS(Depth-First-Search)
DFS,深度优先搜索(Depth-First-Search)是搜索算法的一种。是沿着树的深度遍历树的节点,尽可能深的搜索树的分支。当节点v的所有边都己被探寻过,搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点,则选择其中一个作为源节点并重复以上过程,整个进程反复进行直到所有节点都被访问为止。属于盲目搜索。
WIKIOI P1294 全排列
题目描述 Description
给出一个n, 请输出n的所有全排列
输入描述 Input Description
读入仅一个整数n (1<=n<=10)
输出描述 Output Description
一共n!行,每行n个用空格隔开的数,表示n的一个全排列。并且按全排列的字典序输出。
样例输入 Sample Input
3
样例输出 Sample Output
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
搜索——BFS(Breadth-First-Search)
BFS,其英文全称是Breadth First Search。从算法的观点,所有因为展开节点而得到的子节点都会被加进一个先进先出的队列中。
一般的实验里,其邻居节点尚未被检验过的节点会被放置在一个被称为 open 的容器中(例如队列或是链表),而被检验过的节点则被放置在被称为 closed 的容器中。(open-closed表)
VIJOS P1026毒药?解药?
题目描述:
几种对付某些疾病的解药,因为粗心都配错了一点原料,所以这些药都有可能在治愈某些病症的同时又使人患上某些别的病症。你现在有一张记录每种药的具体性能的清单,请你根据这张清单找出能治愈所有病症的最少药剂组合。病症的数目不超过10种,每种药剂都可以被重复使用。
输入:
第一行是病症的总数n,第二行是药剂的种类m(0<m<=100),以下有m行,每行有n个数字用空格隔开,文件的第i+2行的n个数字中,如果第j个数为1,就表示第i种药可以治愈病症j(如果患有这种病的话则治愈,没有这种病则无影响),如果为0表示无影响,如果为-1表示反而能使人得上这种病(无病患上,有病无影响)。
输出:
一行,给出治愈所有病症最少的药剂数。无法治愈则输出“The patient will be dead.”。
样例输入:
3
2
1 0 1
-1 1 0
样例输出:
2
VIJOS P1026毒药?解药?
BFS+HASH+位运算:
把不患病,患病看做0、1。这样就是把n中病患与不患转换为了二进制串,按n=10来看,总共的状态就有0~2^10-1=1024种。我们假定对于第k个病,患病为1,不患为0。为了方便,我定义两个数描述一种药,那么对于药i就有二进制数a来描述,a的二进制如果第j位为1,表示用药i会使患上j病,a二进制如果第j为为0表示,用药i会解除j病。那么(每种状态 or a)and(a)=用i后的新状态。
由上面的分析,初始状态为1111…,目标状态为0000…。
还有一个问题,怎么判断当前状态是否已经搜过?
Hash判重:把状态转化为10进制,因为有1024种状态,我们开1024+1的布尔数组,判断状态是否搜过。
启发式搜索