抓住那头牛(广搜)--算法学习
题目描述
农夫知道一头牛的位置，想要抓住它。农夫和牛都位于数轴上
，农夫起始位于点N(0<=N<=100000)，牛位于点
K(0<=K<=100000)。农夫有两种移动方式：
1、从X移动到X-1或X+1，每次移动花费一分钟
2、从X移动到2*X，每次移动花费一分钟
假设牛没有意识到农夫的行动，站在原地不动。农夫最少要
花多少时间才能抓住牛？
思路(北大郭炜)
假设农夫起始位于点3，牛位于5
N=3,K=5，最右边是6。
如何搜索到一条走到5的路径？
策略1）深度优先搜索
从起点出发，随机挑一个方向，能
往前走就往前走(扩展），走
不动了则回溯。不能走已经走
过的点(要判重）。
运气好的话：
3->4->5
或3->6->5
问题解决
运气不太好的话：
3->2->4->5
运气最坏的话：
3->2->1->0->4->5
想求最优(短）解，则要遍历所有走法。可以用
各种手段优化，比如，若已经找到路径长度为n
的解，则所有长度大于n的走法就不必尝试。
运算过程中需要存储路径上的节点，数量较少。
用栈存节点
策略2）广度优先搜索：
给节点分层。起点是第0层。从起
点最少需n步就能到达的点属于第n
层。
第1层：2,4,6
第2层：1,5
第3层：0
给节点分层。起点是第0层。从起
点最少需n步就能到达的点属于第n
层。
依层次顺序，从小到大扩展节点。
把层次低的点全部扩展出来后，才
会扩展层次高的点。
搜索过程（节点扩展过程）：
3
2 4 6
1 5
问题解决。
扩展时，不能扩展出已经走过的节
点(要判重） 。
可确保找到最优解，但是因扩展出
来的节点较多，且多数节点都需要
保存，因此需要的存储空间较大。
用队列存节点。
队列就是先进先出
若要遍历所有节点：
深搜
1-2-4-8-5-6-3-7
广搜
1-2-3-4-5-6-7-8
广搜算法：
1：首先，把初始节点So放入到open表中
2:如果问题误解，那么就失败退出
3：把open表的第一个节点取出放入closed表，并及该节点为n
4：考察节点n是不是目标节点，如果是的话就成功找到解，退出
5：若节点n不可扩展，则转向判断open表是否为空
6：拓展节点n，将其不在closed表和open表中的子节点判重放入open表的尾部，并为每一个子节点设置指向父节点的指针，然后转向判断是否open为空？
广度优先搜索队列变化过程：
1:
Closed:
Open: 3
2
Closed: 3
Open: 2 4 6
3
Closed: 3 2
Open: 4 6 1
4
Closed: 3 2 4
Open: 6 1 5
5
Closed: 3 2 4 6
Open: 1 5
6
Closed: 3 2 4 6 1
Open: 5 0
7
Closed:3 2 4 6 1 5
Open: 0
目标节点5出队列，问题解决。
代码
#include
#include
#include
using namespace std;
int N,K;
const int MAXN = 100000;
int visited[MAXN + 10];//判重标记，visited[i]=true表示i已经拓展过
struct Step {
int x;//位置
int steps;//到大x所需要的步数
Step(int xx, int s) :x(xx), steps(s) {}
};
queueq;//队列，即open表
int main() {
cin >> N >> K;
memset(visited, 0, sizeof(visited));
q.push(Step(N, 0));
visited[N] = 1;
while (!q.empty()) {
Step s = q.front();
if (s.x == K) {//找到目标
cout << s.steps <= 0 && !visited[s.x - 1]) {//向左边扩展
q.push(Step(s.x - 1, s.steps + 1));
visited[s.x - 1] = 1;//设置访问标记
}
if (s.x + 1 <= MAXN && !visited[s.x + 1]) {//向右边扩展
q.push(Step(s.x + 1, s.steps + 1));
visited[s.x + 1] = 1;
}
if (s.x * 2 <= MAXN && !visited[s.x * 2]) {
q.push(Step(s.x * 2, s.steps + 1));
visited[s.x * 2] = 1;
}
q.pop();
}
}
return 0;
}
作者：Available time
