小结

适用场景

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

状态转换图:树或者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里的setunordered_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. };
  13. // 定义hash函数
  14. // 方法1:模板特化,当hash函数只需要状态本身,不需要其他数据时,用这个方法比较简洁
  15. namespace std {
  16. template<> struct hash<state_t> {
  17. size_t operator()(const state_t & x) const {
  18. return 0; // 根据具体问题实现
  19. }
  20. };
  21. }
  22. // 方法2:函数对象,如果hash函数需要运行时数据,则用这种方法
  23. class Hasher {
  24. public:
  25. Hasher(int _m) : m(_m) {};
  26. size_t operator()(const state_t &s) const {
  27. return 0; // 根据具体问题实现
  28. }
  29. private:
  30. int m; // 存放外面传入的数据
  31. };
  32. /**
  33. * @brief 反向生成路径,求一条路径.
  34. * @param[in] father 树
  35. * @param[in] target 目标节点
  36. * @return 从起点到target的路径
  37. */
  38. vector<state_t> gen_path(const unordered_map<state_t, state_t> &father,
  39. const state_t &target) {
  40. vector<state_t> path;
  41. path.push_back(target);
  42. for (state_t cur = target; father.find(cur) != father.end();
  43. cur = father.at(cur))
  44. path.push_back(cur);
  45. reverse(path.begin(), path.end());
  46. return path;
  47. }
  48. /**
  49. * 反向生成路径,求所有路径.
  50. * @param[in] father 存放了所有路径的树
  51. * @param[in] start 起点
  52. * @param[in] state 终点
  53. * @return 从起点到终点的所有路径
  54. */
  55. void gen_path(unordered_map<state_t, vector<state_t> > &father,
  56. const string &start, const state_t& state, vector<state_t> &path,
  57. vector<vector<state_t> > &result) {
  58. path.push_back(state);
  59. if (state == start) {
  60. if (!result.empty()) {
  61. if (path.size() < result[0].size()) {
  62. result.clear();
  63. result.push_back(path);
  64. } else if(path.size() == result[0].size()) {
  65. result.push_back(path);
  66. } else {
  67. // not possible
  68. throw std::logic_error("not possible to get here");
  69. }
  70. } else {
  71. result.push_back(path);
  72. }
  73. reverse(result.back().begin(), result.back().end());
  74. } else {
  75. for (const auto& f : father[state]) {
  76. gen_path(father, start, f, path, result);
  77. }
  78. }
  79. path.pop_back();
  80. }

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

单队列的写法

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

双队列的写法

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

求所有路径

单队列

  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
  11. auto state_is_valid = [&](const state_t& s) { /*...*/ };
  12. auto state_is_target = [&](const state_t &s) { /*...*/ };
  13. auto state_extend = [&](const state_t &s) {
  14. unordered_set<state_t> result;
  15. for (/*...*/) {
  16. const state_t new_state = /*...*/;
  17. if (state_is_valid(new_state)) {
  18. auto visited_iter = visited.find(new_state);
  19. if (visited_iter != visited.end()) {
  20. if (visited_iter->level < new_state.level) {
  21. // do nothing
  22. } else if (visited_iter->level == new_state.level) {
  23. result.insert(new_state);
  24. } else { // not possible
  25. throw std::logic_error("not possible to get here");
  26. }
  27. } else {
  28. result.insert(new_state);
  29. }
  30. }
  31. }
  32. return result;
  33. };
  34. vector<vector<string>> result;
  35. state_t start_state(start, 0);
  36. q.push(start_state);
  37. visited.insert(start_state);
  38. while (!q.empty()) {
  39. // 千万不能用 const auto&,pop() 会删除元素,
  40. // 引用就变成了悬空引用
  41. const auto state = q.front();
  42. q.pop();
  43. // 如果当前路径长度已经超过当前最短路径长度,
  44. // 可以中止对该路径的处理,因为我们要找的是最短路径
  45. if (!result.empty() && state.level + 1 > result[0].size()) break;
  46. if (state_is_target(state)) {
  47. vector<string> path;
  48. gen_path(father, start_state, state, path, result);
  49. continue;
  50. }
  51. // 必须挪到下面,比如同一层A和B两个节点均指向了目标节点,
  52. // 那么目标节点就会在q中出现两次,输出路径就会翻倍
  53. // visited.insert(state);
  54. // 扩展节点
  55. const auto& new_states = state_extend(state);
  56. for (const auto& new_state : new_states) {
  57. if (visited.find(new_state) == visited.end()) {
  58. q.push(new_state);
  59. }
  60. visited.insert(new_state);
  61. father[new_state].push_back(state);
  62. }
  63. }
  64. return result;
  65. }

双队列的写法

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

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