迭代加深搜索-POJ 3134 Power Calculus

素颜马尾好姑娘i 2023-07-19 12:09 29阅读 0赞

### 文章目录 ###

*  迭代加深搜索
 *  例题
 *   *  题意
     *  分析
     *  代码
 *  小结

# 迭代加深搜索 #

--------------------

**什么是迭代加深搜索？**  
迭代加深搜索(Iterative Deepening DFS,IDDFS)是一种结合了DFS和BFS思想的搜索方法。当搜索树很深且很宽的时候，用DFS会陷入递归无法返回，用BFS队列空间会爆炸，那么可以试试IDDFS，简单来说，就是**每次限制搜索深度**的DFS。比如DFS搜索k层，若没有找到可行解则立即返回，再DFS搜索k+1层，直到找到可行解为止，在层数上采用BFS思想来逐步扩大DFS的搜索深度。

**IDA**\*  
估价函数对迭代加深搜索的优化，即乐观估计剪枝。当找到解需要的至少层数+当前层数>层数限制时，直接退出。

# 例题 #

--------------------

传送门: [POJ-3134][]

> Starting with x and repeatedly multiplying by x, we can compute x31 with thirty multiplications:  
> x2 = x × x, x3 = x2 × x, x4 = x3 × x, …, x31 = x30 × x.  
> The operation of squaring can be appreciably shorten the sequence of multiplications. The following is a way to compute x31 with eight multiplications:  
> x2 = x × x, x3 = x2 × x, x6 = x3 × x3, x7 = x6 × x, x14 = x7 × x7, x15 = x14 × x, x30 = x15 × x15, x31 = x30 × x.  
> This is not the shortest sequence of multiplications to compute x31. There are many ways with only seven multiplications. The following is one of them:  
> x2 = x × x, x4 = x2 × x2, x8 = x4 × x4, x8 = x4 × x4, x10 = x8 × x2, x20 = x10 × x10, x30 = x20 × x10, x31 = x30 × x.  
> If division is also available, we can find a even shorter sequence of operations. It is possible to compute x31 with six operations (five multiplications and one division):  
> x2 = x × x, x4 = x2 × x2, x8 = x4 × x4, x16 = x8 × x8, x32 = x16 × x16, x31 = x32 ÷ x.  
> This is one of the most efficient ways to compute x31 if a division is as fast as a multiplication.  
> Your mission is to write a program to find the least number of operations to compute xn by multiplication and division starting with x for the given positive integer n. Products and quotients appearing in the sequence should be x to a positive integer’s power. In others words, x−3, for example, should never appear.

**input:**

> The input is a sequence of one or more lines each containing a single integer n. n is positive and less than or equal to 1000. The end of the input is indicated by a zero.

**output:**

> Your program should print the least total number of multiplications and divisions required to compute xn starting with x for the integer n. The numbers should be written each in a separate line without any superfluous characters such as leading or trailing spaces.

**Sample Input:**

1
    31
    70
    91
    473
    512
    811
    953
    0

**Sample Output:**

0
    6
    8
    9
    11
    9
    13
    12

## 题意 ##

给定数x和n，求xn ，只能用乘法和除法，算过的结果可以被利用，问最少算多少次？

## 分析 ##

等价于从数字1开始，用加减法，最少算多少次得到n?  
用当前值和之前产生的值进行加减运算得到新的值，判断是否等于n。  
估价函数：如果当前值用最快的方式（连乘2倍增）都不能到达n则退出。

## 代码 ##

#include<stdio.h>
    #include<string.h>
    #include<stdlib.h>
    const int maxn = 1010;
    int a[maxn];
    int n, k;
    bool ida(int now,int curk) { 
    	if (curk > k)return true;//当前层数大于层数限制
    	//剩下的层数(层数限制-当前层)用最乐观的倍增也不能达到n
    	if (now << (k - curk) < n)return true;
    	return false;
    }
    bool iddfs(int now, int curk) { 
    	if (ida(now, curk))return false;
    	if (now == n)return true;
    	a[curk] = now;
    	for (int i = 0; i <= curk; i++) { //遍历之前算过的值
    		//加
    		if (iddfs(now + a[i], curk + 1))return true;
    		//减
    		else if (iddfs(abs(now - a[i]), curk + 1))return true;
    	}
    	return false;
    }
    int main() { 
    	while (~scanf("%d", &n) && n) { 
    		for (k = 0;; k++) { //每次最大搜索k层
    			memset(a, 0, sizeof(a));
    			if (iddfs(1, 0))break;//从数字1开始，当前层0
    		}
    		printf("%d\n", k);
    	}
    	return 0;
    }

# 小结 #

--------------------

1.  空间复杂度相对较小（其实前面k-1层的浪费对于复杂度来说可以忽略），如果广/深搜爆栈可以一试。
2.  适用于时间充裕，空间较小，没有明确搜索深度上限的题。
3.  剪枝!!!

> **原创不易，请勿转载**（本不富裕的访问量雪上加霜 ）  
> 博主首页：[https://blog.csdn.net/qq\_45034708][https_blog.csdn.net_qq_45034708]  
> *如果文章对你有帮助，记得关注点赞收藏❤*

[POJ-3134]: https://vjudge.net/problem/POJ-3134/origin
[https_blog.csdn.net_qq_45034708]: https://blog.csdn.net/qq_45034708