????????寬度優先搜索算法(BFS? Breadth first search) 又稱廣度優先搜索，這種搜索是逐層的，搜索完上層，才會搜索下一層，直到找到目標節點。

????????

????????搜索過程如圖中箭頭方向：

【例如】 八數碼難題：利用空格的移動，使無規律的圖案變成右側有順序的圖案，下圖所示：

思路如下：羅列所有可能情況；然后逐一檢查是否是答案。

主要算法：

1. 查找左右移動后的圖形：

/// <summary>
? ? ? ? /// 空格向左移動，前提是空格不在最左一列
? ? ? ? /// </summary>
? ? ? ? /// <returns></returns>
? ? ? ? public ChessPos MoveLeft()
? ? ? ? {
? ? ? ? ? ? //若空格在最左邊界上，無法左移
? ? ? ? ? ? if (ZeroColumn==0)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? return null;
? ? ? ? ? ? }
? ? ? ? ? ? //先拷貝當前的，然后把空格左移動一位，交換下兩個的數字
? ? ? ? ? ? ChessPos tmpPos = this.Clone() as ChessPos; ? ? ? ? ? ? ? ? ? ? ??
? ? ? ? ? ?
? ? ? ? ? ? tmpPos.father = this;
? ? ? ? ? ? tmpPos.position[ZeroRow, ZeroColumn] = position[ZeroRow, ZeroColumn - 1];
? ? ? ? ? ? tmpPos.position[ZeroRow, ZeroColumn - 1] = position[ZeroRow, ZeroColumn];
? ? ? ? ? ? return tmpPos;
? ? ? ? }

2.從Openlist中取節點、展開、然后添加到closedlist

?//當Open表中有內容，
? ? ? ? ? ? while (OpenList.Count > 0 && !bFindSolution)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? //1.從Open表表頭取一個對象，若該位置沒有在closed表出現過，則放入到Close表。
? ? ? ? ? ? ? ? ChessPos tmp = OpenList[0];
? ? ? ? ? ? ? ? OpenList.RemoveAt(0);

? ? ? ? ? ? ? ? //判斷該布局是否在close表中已經出現過
? ? ? ? ? ? ? ? bool bAlreadyExist = false;
? ? ? ? ? ? ? ? for (int i = 0; i <= CloseList.Count - 1; i++)
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? if (CloseList[i].Equals(tmp))
? ? ? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? ? ? bAlreadyExist = true;
? ? ? ? ? ? ? ? ? ? ? ? break;
? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? if (bAlreadyExist == false)
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? CloseList.Add(tmp);
? ? ? ? ? ? ? ? }

? ? ? ? ? ? ? ? //2.獲得新的4種空格的可能走法
? ? ? ? ? ? ? ? List<ChessPos> PossibleSteps = tmp.getNextPosition();
? ? ? ? ? ? ? ? foreach (ChessPos pos in PossibleSteps)
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? //看是否已經達到最終位置
? ? ? ? ? ? ? ? ? ? if (pos.IsSolution())
? ? ? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? ? ? bFindSolution = true;
? ? ? ? ? ? ? ? ? ? ? ? solution = pos;
? ? ? ? ? ? ? ? ? ? ? ? break;
? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? ? ? else if (CloseList == null || !CloseList.Contains(pos) ? ?)
? ? ? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? ? ? //若新的圖案在open&close表中都沒有出現過，則加入open表中
? ? ? ? ? ? ? ? ? ? ? ? if(OpenList == null || !OpenList.Contains(pos) )
? ? ? ? ? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? ? ? ? ? OpenList.Add(pos);
? ? ? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? ? ? }?
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? OnProgressChanged(new ChessPosEventArg(OpenList.Count, CloseList.Count));
? ? ? ? ? ? ? ? //超過3萬就不搜索了
? ? ? ? ? ? ? ? if (CloseList.Count > 30000)
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? break;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
?

代碼在可以下載： https://download.csdn.net/download/qq_34047402/90563588

深度搜索、寬度搜索算法(以八數碼、皇后、迷宮為例)資源-CSDN文庫

https://item.taobao.com/item.htm?spm=a21dvs.23580594.0.0.1d292c1bt6mw2Y&ft=t&id=905463299574