小结

适用场景

输入数据：没什么特征，不像深搜，需要有“递归”的性质。如果是树或者图，概率更大。

状态转换图：树或者DAG图。

求解目标：多阶段最优化问题。

思考的步骤

  • 是求路径长度，还是路径本身（或动作序列）？

    • 如果是求路径长度，则状态里面要存路径长度（或双队列+一个全局变量）

    • 如果是求路径本身或动作序列

      • 要用一棵树存储宽搜过程中的路径
      • 是否可以预估状态个数的上限？能够预估状态总数，则开一个大数组，用树的双亲表示法；如果不能预估状态总数，则要使用一棵通用的树。这一步也是第4步的必要不充分条件。

  • 如何表示状态？即一个状态需要存储哪些些必要的数据，才能够完整提供如何扩展到下一步状态的所有信息。一般记录当前位置或整体局面。

  • 如何扩展状态？这一步跟第2步相关。状态里记录的数据不同，扩展方法就不同。对于固定不变的数据结构（一般题目直接给出，作为输入数据），如二叉树，图等，扩展方法很简单，直接往下一层走，对于隐式图，要先在第1步里想清楚状态所带的数据，想清楚了这点，那如何扩展就很简单了。

  • 如何判断重复？如果状态转换图是一颗树，则永远不会出现回路，不需要判重；如果状态转换图是一个图（这时候是一个图上的BFS），则需要判重。

    • 如果是求最短路径长度或一条路径，则只需要让“点”（即状态）不重复出现，即可保证不出现回路
    • 如果是求所有路径，注意此时，状态转换图是DAG，即允许两个父节点指向同一个子节点。具体实现时，每个节点要“延迟”加入到已访问集合visited，要等一层全部访问完后，再加入到visited集合。

    • 具体实现

      • 状态是否存在完美哈希方案？即将状态一一映射到整数，互相之间不会冲突。
      • 如果不存在，则需要使用通用的哈希表（自己实现或用标准库，例如unordered_set）来判重；自己实现哈希表的话，如果能够预估状态个数的上限，则可以开两个数组，head和next，表示哈希表，参考第 ??? 节方案2。
      • 如果存在，则可以开一个大布尔数组，来判重，且此时可以精确计算出状态总数，而不仅仅是预估上限。
  • 目标状态是否已知？如果题目已经给出了目标状态，可以带来很大便利，这时候可以从起始状态出发，正向广搜；也可以从目标状态出发，逆向广搜；也可以同时出发，双向广搜。

代码模板

广搜需要一个队列，用于一层一层扩展，一个hashset，用于判重，一棵树（只求长度时不需要），用于存储整棵树。

对于队列，可以用queue，也可以把vector当做队列使用。当求长度时，有两种做法：

  • 只用一个队列，但在状态结构体state_t里增加一个整数字段level，表示当前所在的层次，当碰到目标状态，直接输出level即可。这个方案，可以很容易的变成A*算法，把queue替换为priority_queue即可。
  • 用两个队列，current, next，分别表示当前层次和下一层，另设一个全局整数level，表示层数（也即路径长度），当碰到目标状态，输出level即可。这个方案，状态里可以不存路径长度，只需全局设置一个整数level，比较节省内存；
    对于hashset，如果有完美哈希方案，用布尔数组(bool visited[STATE_MAX]或vector<bool> visited(STATE_MAX, false))来表示；如果没有，可以用STL里的set或unordered_set。

对于树，如果用STL，可以用unordered_map<state_t, state_t > father表示一颗树，代码非常简洁。如果能够预估状态总数的上限（设为STATE_MAX），可以用数组(state_t nodes[STATE_MAX])，即树的双亲表示法来表示树，效率更高，当然，需要写更多代码。

如何表示状态

  1. /** 状态 */
  2. struct state_t {
  3.     int data1;  /** 状态的数据，可以有多个字段. */
  4.     int data2;  /** 状态的数据，可以有多个字段. */
  5.     // dataN;   /** 其他字段 */
  6.     int action; /** 由父状态移动到本状态的动作，求动作序列时需要. */
  7.     int level;  /** 所在的层次（从0开始），也即路径长度-1，求路径长度时需要；
  8.                     不过，采用双队列时不需要本字段，只需全局设一个整数 */
  9.     bool operator==(const state_t &other) const {
  10.         return true;  // 根据具体问题实现
  11.     }
  12. };
  14. // 定义hash函数
  16. // 方法1：模板特化，当hash函数只需要状态本身，不需要其他数据时，用这个方法比较简洁
  17. namespace std {
  18. template<> struct hash<state_t> {
  19.     size_t operator()(const state_t & x) const {
  20.         return 0; // 根据具体问题实现
  21.     }
  22. };
  23. }
  25. // 方法2：函数对象，如果hash函数需要运行时数据，则用这种方法
  26. class Hasher {
  27. public:
  28.     Hasher(int _m) : m(_m) {};
  29.     size_t operator()(const state_t &s) const {
  30.         return 0; // 根据具体问题实现
  31.     }
  32. private:
  33.     int m; // 存放外面传入的数据
  34. };
  36. /**
  37.  * @brief 反向生成路径，求一条路径.
  38.  * @param[in] father 树
  39.  * @param[in] target 目标节点
  40.  * @return 从起点到target的路径
  41.  */
  42. vector<state_t> gen_path(const unordered_map<state_t, state_t> &father,
  43.         const state_t &target) {
  44.     vector<state_t> path;
  45.     path.push_back(target);
  47.     for (state_t cur = target; father.find(cur) != father.end(); 
  48.             cur = father.at(cur))
  49.         path.push_back(cur);
  51.     reverse(path.begin(), path.end());
  53.     return path;
  54. }
  56. /**
  57.  * 反向生成路径，求所有路径.
  58.  * @param[in] father 存放了所有路径的树
  59.  * @param[in] start 起点
  60.  * @param[in] state 终点
  61.  * @return 从起点到终点的所有路径
  62.  */
  63. void gen_path(unordered_map<state_t, vector<state_t> > &father,
  64.         const string &start, const state_t& state, vector<state_t> &path,
  65.         vector<vector<state_t> > &result) {
  66.     path.push_back(state);
  67.     if (state == start) {
  68.         if (!result.empty()) {
  69.             if (path.size() < result[0].size()) {
  70.                 result.clear();
  71.                 result.push_back(path);
  72.             } else if(path.size() == result[0].size()) {
  73.                 result.push_back(path);
  74.             } else {
  75.                 // not possible
  76.                 throw std::logic_error("not possible to get here");
  77.             }
  78.         } else {
  79.             result.push_back(path);
  80.         }
  81.         reverse(result.back().begin(), result.back().end());
  82.     } else {
  83.         for (const auto& f : father[state]) {
  84.             gen_path(father, start, f, path, result);
  85.         }
  86.     }
  87.     path.pop_back();
  88. }

求最短路径长度或一条路径

单队列的写法

  1. #include "bfs_common.h"
  3. /**
  4.  * @brief 广搜，只用一个队列.
  5.  * @param[in] start 起点
  6.  * @param[in] data 输入数据
  7.  * @return 从起点到目标状态的一条最短路径
  8.  */
  9. vector<state_t> bfs(state_t &start, const vector<vector<int>> &grid) {
  10.     queue<state_t> q; // 队列
  11.     unordered_set<state_t> visited; // 判重
  12.     unordered_map<state_t, state_t> father; // 树，求路径本身时才需要
  14.     // 判断状态是否合法
  15.     auto state_is_valid = [&](const state_t &s) { /*...*/ };
  17.     // 判断当前状态是否为所求目标
  18.     auto state_is_target = [&](const state_t &s) { /*...*/ };
  20.     // 扩展当前状态
  21.     auto state_extend = [&](const state_t &s) {
  22.         unordered_set<state_t> result;
  23.         for (/*...*/) {
  24.             const state_t new_state = /*...*/;
  25.             if (state_is_valid(new_state) && 
  26.                     visited.find(new_state) != visited.end()) {
  27.                 result.insert(new_state);
  28.             }
  29.         }
  30.         return result;
  31.     };
  33.     assert (start.level == 0);
  34.     q.push(start);
  35.     while (!q.empty()) {
  36.         // 千万不能用 const auto&，pop() 会删除元素，
  37.         // 引用就变成了悬空引用
  38.         const state_t state = q.front();
  39.         q.pop();
  40.         visited.insert(state);
  42.         // 访问节点
  43.         if (state_is_target(state)) {
  44.             return return gen_path(father, target); // 求一条路径
  45.             // return state.level + 1; // 求路径长度
  46.         }
  48.         // 扩展节点
  49.         vector<state_t> new_states = state_extend(state);
  50.         for (const auto& new_state : new_states) {
  51.             q.push(new_state);
  52.             father[new_state] = state;  // 求一条路径
  53.             // visited.insert(state); // 优化：可以提前加入 visited 集合，
  54.             // 从而缩小状态扩展。这时 q 的含义略有变化，里面存放的是处理了一半
  55.             // 的节点：已经加入了visited，但还没有扩展。别忘记 while循环开始
  56.             // 前，要加一行代码, visited.insert(start)
  57.         }
  58.     }
  60.     return vector<state_t>();
  61.     //return 0;
  62. }

双队列的写法

  1. #include "bfs_common.h"
  3. /**
  4.  * @brief 广搜，使用两个队列.
  5.  * @param[in] start 起点
  6.  * @param[in] data 输入数据
  7.  * @return 从起点到目标状态的一条最短路径
  8.  */
  9. vector<state_t> bfs(const state_t &start, const type& data) {
  10.     queue<state_t> next, current; // 当前层，下一层
  11.     unordered_set<state_t> visited; // 判重
  12.     unordered_map<state_t, state_t> father; // 树，求路径本身时才需要
  14.     int level = -1;  // 层次
  16.     // 判断状态是否合法
  17.     auto state_is_valid = [&](const state_t &s) { /*...*/ };
  19.     // 判断当前状态是否为所求目标
  20.     auto state_is_target = [&](const state_t &s) { /*...*/ };
  22.     // 扩展当前状态
  23.     auto state_extend = [&](const state_t &s) {
  24.         unordered_set<state_t> result;
  25.         for (/*...*/) {
  26.             const state_t new_state = /*...*/;
  27.             if (state_is_valid(new_state) && 
  28.                     visited.find(new_state) != visited.end()) {
  29.                 result.insert(new_state);
  30.             }
  31.         }
  32.         return result;
  33.     };
  35.     current.push(start);
  36.     while (!current.empty()) {
  37.         ++level;
  38.         while (!current.empty()) {
  39.             // 千万不能用 const auto&，pop() 会删除元素，
  40.             // 引用就变成了悬空引用
  41.             const auto state = current.front();
  42.             current.pop();
  43.             visited.insert(state);
  45.             if (state_is_target(state)) {
  46.                 return return gen_path(father, state); // 求一条路径
  47.                 // return state.level + 1; // 求路径长度
  48.             }
  50.             const auto& new_states = state_extend(state);
  51.             for (const auto& new_state : new_states) {
  52.                 next.push(new_state);
  53.                 father[new_state] = state;
  54.                 // visited.insert(state); // 优化：可以提前加入 visited 集合，
  55.                 // 从而缩小状态扩展。这时 current 的含义略有变化，里面存放的是处
  56.                 // 理了一半的节点：已经加入了visited，但还没有扩展。别忘记 while
  57.                 // 循环开始前，要加一行代码, visited.insert(start)
  58.             }
  59.         }
  60.         swap(next, current); //!!! 交换两个队列
  61.     }
  63.     return vector<state_t>();
  64.     // return 0;
  65. }

求所有路径

单队列

  1. /**
  2.  * @brief 广搜，使用一个队列.
  3.  * @param[in] start 起点
  4.  * @param[in] data 输入数据
  5.  * @return 从起点到目标状态的所有最短路径
  6.  */
  7. vector<vector<state_t> > bfs(const state_t &start, const type& data) {
  8.     queue<state_t> q;
  9.     unordered_set<state_t> visited; // 判重
  10.     unordered_map<state_t, vector<state_t> > father; // DAG
  12.     auto state_is_valid = [&](const state_t& s) { /*...*/ };
  13.     auto state_is_target = [&](const state_t &s) { /*...*/ };
  14.     auto state_extend = [&](const state_t &s) {
  15.         unordered_set<state_t> result;
  16.         for (/*...*/) {
  17.             const state_t new_state = /*...*/;
  18.             if (state_is_valid(new_state)) {
  19.                 auto visited_iter = visited.find(new_state);
  21.                 if (visited_iter != visited.end()) {
  22.                     if (visited_iter->level < new_state.level) {
  23.                         // do nothing
  24.                     } else if (visited_iter->level == new_state.level) {
  25.                         result.insert(new_state);
  26.                     } else { // not possible
  27.                         throw std::logic_error("not possible to get here");
  28.                     }
  29.                 } else {
  30.                     result.insert(new_state);
  31.                 }
  32.             }
  33.         }
  35.         return result;
  36.     };
  38.     vector<vector<string>> result;
  39.     state_t start_state(start, 0);
  40.     q.push(start_state);
  41.     visited.insert(start_state);
  42.     while (!q.empty()) {
  43.         // 千万不能用 const auto&，pop() 会删除元素，
  44.         // 引用就变成了悬空引用
  45.         const auto state = q.front();
  46.         q.pop();
  48.         // 如果当前路径长度已经超过当前最短路径长度，
  49.         // 可以中止对该路径的处理，因为我们要找的是最短路径
  50.         if (!result.empty() && state.level + 1 > result[0].size()) break;
  52.         if (state_is_target(state)) {
  53.             vector<string> path;
  54.             gen_path(father, start_state, state, path, result);
  55.             continue;
  56.         }
  57.         // 必须挪到下面，比如同一层A和B两个节点均指向了目标节点，
  58.         // 那么目标节点就会在q中出现两次，输出路径就会翻倍
  59.         // visited.insert(state);
  61.         // 扩展节点
  62.         const auto& new_states = state_extend(state);
  63.         for (const auto& new_state : new_states) {
  64.             if (visited.find(new_state) == visited.end()) {
  65.                 q.push(new_state);
  66.             }
  67.             visited.insert(new_state);
  68.             father[new_state].push_back(state);
  69.         }
  70.     }
  72.     return result;
  73. }

双队列的写法

  1. #include "bfs_common.h"
  3. /**
  4.  * @brief 广搜，使用两个队列.
  5.  * @param[in] start 起点
  6.  * @param[in] data 输入数据
  7.  * @return 从起点到目标状态的所有最短路径
  8.  */
  9. vector<vector<state_t> > bfs(const state_t &start, const type& data) {
  10.     // 当前层，下一层，用unordered_set是为了去重，例如两个父节点指向
  11.     // 同一个子节点，如果用vector, 子节点就会在next里出现两次，其实此
  12.     // 时 father 已经记录了两个父节点，next里重复出现两次是没必要的
  13.     unordered_set<string> current, next;
  14.     unordered_set<state_t> visited; // 判重
  15.     unordered_map<state_t, vector<state_t> > father; // DAG
  17.     int level = -1;  // 层次
  19.     // 判断状态是否合法
  20.     auto state_is_valid = [&](const state_t &s) { /*...*/ };
  22.     // 判断当前状态是否为所求目标
  23.     auto state_is_target = [&](const state_t &s) { /*...*/ };
  25.     // 扩展当前状态
  26.     auto state_extend = [&](const state_t &s) {
  27.         unordered_set<state_t> result;
  28.         for (/*...*/) {
  29.             const state_t new_state = /*...*/;
  30.             if (state_is_valid(new_state) && 
  31.                     visited.find(new_state) != visited.end()) {
  32.                 result.insert(new_state);
  33.             }
  34.         }
  35.         return result;
  36.     };
  38.     vector<vector<state_t> > result;
  39.     current.insert(start);
  40.     while (!current.empty()) {
  41.         ++ level;
  42.         // 如果当前路径长度已经超过当前最短路径长度，可以中止对该路径的
  43.         // 处理，因为我们要找的是最短路径
  44.         if (!result.empty() && level+1 > result[0].size()) break;
  46.         // 1. 延迟加入visited, 这样才能允许两个父节点指向同一个子节点
  47.         // 2. 一股脑current 全部加入visited, 是防止本层前一个节点扩展
  48.         // 节点时，指向了本层后面尚未处理的节点，这条路径必然不是最短的
  49.         for (const auto& state : current)
  50.             visited.insert(state);
  51.         for (const auto& state : current) {
  52.             if (state_is_target(state)) {
  53.                 vector<string> path;
  54.                 gen_path(father, path, start, state, result);
  55.                 continue;
  56.             }
  58.             const auto new_states = state_extend(state);
  59.             for (const auto& new_state : new_states) {
  60.                 next.insert(new_state);
  61.                 father[new_state].push_back(state);
  62.             }
  63.         }
  65.         current.clear();
  66.         swap(current, next);
  67.     }
  69.     return result;
  70. }

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/cpp/bfs/bfs-summary.html