问题描述

农夫知道一头牛的位置，想要抓住它。农夫和牛都位于数轴上，农夫起始位于点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的最短路径？

深度优先搜索

从起点出发，随机挑一个方向，能往前走就往前走，走不动了则回溯。不能走已经走过的点。
运气好的话：
3->4->5或 3->6->5
问题解决！
运气不太好的话：
3->2->4->5
运气最坏的话：
3->2->1->0->4->5
要想求最优解，则要遍历所有走法。
可以用各种手段优化，比如，若已经找到路径长度为n的解，则所有长度大于n的走法就不必尝试。
运算过程中需要存储路径上的节点，数量较少。用栈存节点。

广度优先搜索

给节点分层。起点是第0层。从起点最少需n步就能到达的点属于第n层。
第1层： 2,4,6
第2层： 1,5
第3层： 0
依层次顺序，从小到大扩展节点。把层次低的点全部扩展出来后，才会扩展层次高的点。
搜索过程（节点扩展过程）：
3
2 4 6
1 5
问题解决。
扩展时，不能扩展出已经走过的节点。
可确保找到的第一个解即为最优解，但是因扩展出来的节点较多，且多数节点都需要保存，因此需要的存储空间较大。用队列存节点。
广度优先搜索算法如下
(1) 把初始节点S₀放入Open表中；
(2) 如果Open表为空，则问题无解，失败退出；
(3) 把Open表的第一个节点取出放入Closed表，并记该节点为n；
(4) 考察节点n是否为目标节点。若是，则得到问题的解，成功退出；
(5) 若节点n不可扩展，则转第(2)步；
(6) 扩展节点n，将其不在Closed表和Open表中的子节点放入Open表的尾部
，并为每一个子节点设置指向父节点的指针或记录节点的层次，然后转第(2)步。

程序实现

#include<iostream>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;

const int MAXN = 100001;
int N, K;
struct Step
{
    int prev;
    int x;
    int steps;
    Step(int prev_, int x_, int steps_): prev(prev_), x(x_), steps(steps_) {}
    Step() {}
    Step& operator = (const Step& s)
    {
        prev = s.prev;
        x = s.x;
        steps = s.steps;
    }
};
bool operator < (const Step& s1, const Step& s2)
{
    return s1.x < s2.x;
}
int visited[MAXN];
queue<Step> q;
vector<Step> v;
stack<int> s;//存path points

int main()
{

    cin >> N >> K;
    memset(visited, 0, sizeof(visited));
    q.push(Step(MAXN, N, 0));
    visited[N] = 1;
    while(!q.empty())
        {
            Step tmp = q.front();
            if(tmp.x == K)
                {
                    cout << "the optimal path length: " << tmp.steps << endl;
                    s.push(tmp.x);
                    int v_size = v.size();
                    while(tmp.prev < MAXN)
                        {
                            for(int i = 0; i < v_size; i++)
                                if(v[i].x == tmp.prev)
                                    {
                                        tmp = v[i];
                                        s.push(tmp.x);
                                    }
                        }
                    while(!s.empty())
                        {
                            cout << s.top() << " ";
                            s.pop();
                        }
                    cout << endl;

                    return 0;
                }
            if(tmp.x - 1 >= 0 && visited[tmp.x - 1] != 1)
                {
                    q.push(Step(tmp.x, tmp.x - 1, tmp.steps + 1));
                    visited[tmp.x - 1] = 1;
                }
            if(tmp.x + 1 <= MAXN && visited[tmp.x + 1] != 1)
                {
                    q.push(Step(tmp.x, tmp.x + 1, tmp.steps + 1));
                    visited[tmp.x + 1] = 1;
                }
            if(2 * tmp.x <= MAXN && visited[2 * tmp.x] != 1)
                {
                    q.push(Step(tmp.x, 2 * tmp.x, tmp.steps + 1));
                    visited[2 * tmp.x] = 1;
                }
            q.pop();
            v.push_back(tmp);
        }



    return 0;
}