淺析迷宮搜索類的雙向bfs問題(附例題解析)

2020 年 2 月 26 日
筆記

前言

在搜索問題中，以迷宮問題最具有代表性，無論是八皇后的回溯問題，還是dfs找出口，bfs找最短次數等等題目的問題。在我們剛開始ac的時候、可能有著很多滿足感！感覺是個迷宮問題咱么都可以給他這麼搜出來！！

然而，當數據達到一定程度，我們使用簡單的方法肯定會爆炸的，各種TLE(超時)，不分析原因還會一直提交一直TLE。就可能需要一些特殊的巧妙方法處理，比如各種剪枝、優先隊列、A*、dfs套bfs，又或者利用一些非常厲害的數學方法比如康托展開(逆展開)等等。而今天，我們談談雙向bfs。(通常可以將時間複雜度優化為原時間的根號級別)

bfs類問題

bfs又稱廣度優先搜索

估計大部分人第一次接觸bfs的時候是在學習數據結構的二叉樹的層序遍歷！藉助一個隊列一層一層遍歷。
第二次估計就是在學習圖論的時候，給你一個圖，讓你寫出一個bfs遍歷的順序。

此後再無bfs…

而很多筆試面試還是其他機試其實對bfs的要求遠遠不止那麼低的，需要能夠處理一些小問題、寫出對應程式碼。而且bfs可以處理很多問題，很多dfs搜索能夠解決的問題bfs也能解決很多(相反也成立)，並且很多跟狀態有些關係的用bfs更好控制，因為bfs藉助的是一個隊列實現，隊列中儲存節點就可以保存一些節點的狀態。

不過bfs並不是萬能的，具體問題要看迷宮的大小的，迷宮長寬沒增加一個數，那麼這個數量級增加是非常大的，因為搜索次數大概和邊長的指數級別有關係。當然這裡不詳細介紹bfs了，大家可以看以前的一篇文章。數據結構與演算法—深度、寬度優先(dfs,bfs)搜索

雙向bfs

什麼樣的情況可以使用雙向bfs來優化呢?其實雙向bfs的主要思想是問題的拆分吧，比如在一個迷宮中可以往下往右行走，問你有多少種方式從左上到右下。

正常情況下，我們就是搜索遍歷，如果迷宮邊長為n，那麼這個複雜度大概是2^n^級別.
但是實際上我們可以將迷宮拆分一下，比如根據對角線(比較多)，將迷宮一分為二。其實你的結果肯定必然經過對角線的這些點對吧！我們只要分別計算出各個對角線各個點的次數然後相加就可以了！
怎麼算？ 就是從(0,0)到中間這個點mid的總次數為n1，然後這個mid到(n,n)點的總次數為n2，然後根據排列組合總次數就是n1*n2(n1和n2正常差不多大)這樣就可以通過乘法減少加法的運算次數啦！
簡單的說，從數據次數來看如果直接搜索全圖經過下圖的那個點的次數為 n1 * n2 次，如果分成兩個部分相乘那就是n1+n2次。兩者差距如果n1,n2=1000左右，那麼這麼一次差距是平方(根號)級別的。從搜索圖形來看其實這麼一次搜索是本來一個n*n大小的搜索轉變成n次(每次大概是(n/2) * (n/2)大小的迷宮搜索兩次)。也就是如果18*18的迷宮如果使用直接搜索，那麼大概2^18次方量級，而如果採用雙向bfs，那麼就是2^9這個量級。

例題實戰

題目鏈接：http://oj.hzjingma.com/contest/problem?id=20&pid=8#problem-anchor

分析：對於題目的要求還是很容易理解的，就是找到所有的路徑種類，再判斷其中是對稱路徑的有幾個輸出即可！

對於一個普通思考是這樣的，首先是進行dfs，然後動態維護一個字元串，每次跑到最後判斷這個路徑字元串是否滿足對稱要求，如果滿足那麼就添加到容器中進行判斷。可惜很遺憾這樣是超時的，僅能通過40%的樣例。

接著用普通bfs進行嘗試，維護一個node節點，每次走的時候路徑儲存起來其實這個效率跟dfs差不多依然超時。只能通過40%數據。

接下來就開始雙向bfs進行分析！

既然只能右下，那麼對角線的那個位置的肯定是中間的那個字元串的！它的存在不影響是否對稱的(n*n的迷宮路徑長度為n-1 + n為奇數).
我們判斷路徑是否對稱，只需要判斷從(1,1)到對角節點k(設為k節點)的路徑有沒有和從(n,n)到k相同的。如果有路徑相同的那麼就說明這一對構成對稱路徑
在具體實現上，我們對每個對角線節點可以進行兩次bfs(一次左上到(1,1),一次右下到(n,n)).並且將路徑放到兩個hashset(set1,set2)中，跑完之後用遍歷其中一個hashset中的路徑，看看另一個set是否存在該路徑，如果存在就說明這個是對稱路徑放到 總的hashset(set) 中。對角線每個位置都這樣判斷完最後只需要輸出總的hashset(set)的集合大小即可！

ac程式碼如下：

import java.util.ArrayDeque;  import java.util.HashSet;  import java.util.Queue;  import java.util.Scanner;  import java.util.Set;    public class test2 {      static class node{           int x;           int y;          String path="";          public node() {}          public node(int x,int y,String team)          {              this.x=x;              this.y=y;              this.path=team;          }      }      public static void main(String[] args) {          Scanner sc=new Scanner(System.in);          Set<String>set=new HashSet<String>();//儲存最終結果          int n=Integer.parseInt(sc.nextLine());          char map[][]=new char[n][n];          for(int i=0;i<n;i++)          {              String string=sc.nextLine();              map[i]=string.toCharArray();          }          Queue<node>q1=new ArrayDeque<node>();//左上的隊列          Queue<node>q2=new ArrayDeque<node>();//右下的隊列          for(int i=0;i<n;i++)          {              q1.clear();q2.clear();              Set<String>set1=new HashSet<String>();//儲存zuoshang              Set<String>set2=new HashSet<String>();//儲右下              q1.add(new node(i,n-1-i,""+map[i][n-1-i]));              q2.add(new node(i,n-1-i,""+map[i][n-1-i]));              while(!q1.isEmpty()&&!q2.isEmpty())              {                  node team=q1.poll();                  node team2=q2.poll();                  if(team.x==n-1&&team.y==n-1)//到終點，將路徑儲存                  {                      //System.out.println(team2.path);                      set1.add(team.path);                      set2.add(team2.path);                  }                  else {                      if(team.x<n-1)//可以向下                      {                          q1.add(new node(team.x+1, team.y, team.path+map[team.x+1][team.y]));                      }                      if(team.y<n-1)//可以向右                      {                          q1.add(new node(team.x, team.y+1, team.path+map[team.x][team.y+1]));                      }                      if(team2.x>0)//上                      {                          q2.add(new node(team2.x-1, team2.y, team2.path+map[team2.x-1][team2.y]));                      }                      if(team2.y>0)//左                      {                          q2.add(new node(team2.x, team2.y-1, team2.path+map[team2.x][team2.y-1]));                      }                  }                }              for(String va:set1)              {                  if(set2.contains(va))                  {                      set.add(va);                  }              }            }          System.out.println(set.size());      }  }