1.引子
中國有一句古話,叫做“不撞南牆不回頭",生動的說明了一個人的固執,有點貶義,但是在軟體程式設計中,這種思路确是一種解決問題最簡單的算法,它通過一種類似于蠻幹的思路,一步一步地往前走,每走一步都更靠近目标結果一些,直到遇到障礙物,我們才考慮往回走。然後再繼續嘗試向前。通過這樣的波浪式前進方法,最終達到目的地。當然整個過程需要很多往返,這樣的前進方式,效率比較低下。
2.适用範圍
适用于那些不存在簡明的數學模型以闡明問題的本質,或者存在數學模型,但是難于實作的問題。
3.應用場景
在8*8國際象棋棋盤上,要求在每一行放置一個皇後,且能做到在豎方向,斜方向都沒有沖突。國際象棋的棋盤如下圖所示:
4.分析
基本思路如上面分析一緻,我們采用逐漸試探的方式,先從一個方向往前走,能進則進,不能進則退,嘗試另外的路徑。首先我們來分析一下國際象棋的規則,這些規則能夠限制我們的前進,也就是我們前進途中的障礙物。一個皇後q(x,y)能被滿足以下條件的皇後q(row,col)吃掉
1)x=row(在縱向不能有兩個皇後)
2) y=col(橫向)
3)col + row = y+x;(斜向正方向)
4) col - row = y-x;(斜向反方向)
遇到上述問題之一的時候,說明我們已經遇到了障礙,不能繼續向前了。我們需要退回來,嘗試其他路徑。
我們将棋盤看作是一個8*8的數組,這樣可以使用一種蠻幹的思路去解決這個問題,這樣我們就是在8*8=64個格子中取出8個的組合,C(64,80) = 4426165368,顯然這個數非常大,在蠻幹的基礎上我們可以增加回溯,從第0列開始,我們逐列進行,從第0行到第7行找到一個不受任何已經現有皇後攻擊的位置,而第五列,我們會發現找不到皇後的安全位置了,前面四列的擺放如下:
第五列的時候,擺放任何行都會上圖所示已經存在的皇後的攻擊,這時候我們認為我們撞了南牆了,是回頭的時候了,我們後退一列,将原來擺放在第四列的皇後(3,4)拿走,從(3,4)這個位置開始,我們再第四列中尋找下一個安全位置為(7,4),再繼續到第五列,發現第五列仍然沒有安全位置,回溯到第四列,此時第四列也是一個死胡同了,我們再回溯到第三列,這樣前進幾步,回退一步,最終直到在第8列上找到一個安全位置(成功)或者第一列已經是死胡同,但是第8列仍然沒有找到安全位置為止
總結一下,用回溯的方法解決8皇後問題的步驟為:
1)從第一列開始,為皇後找到安全位置,然後跳到下一列
2)如果在第n列出現死胡同,如果該列為第一列,棋局失敗,否則後退到上一列,在進行回溯
3)如果在第8列上找到了安全位置,則棋局成功。
8個皇後都找到了安全位置代表棋局的成功,用一個長度為8的整數數組queenList代表成功擺放的8個皇後,數組索引代表棋盤的col向量,而數組的值為棋盤的row向
量,是以(row,col)的皇後可以表示為(queenList[col],col),如上圖中的幾個皇後可表示為:
queenList[0] = 0; queenList[1] = 3; queenList[2] = 1; queenList[3] = 4; queenList = 2;
我們看一下如何設計程式:
首先判斷(row,col)是否是安全位置的算法:
bool IsSafe(int col,int row,int[] queenList)
{
//隻檢查前面的列
for (int tempCol = 0; tempCol < col; tempCol++)
{
int tempRow = queenList[tempCol];
if (tempRow == row)
{
//同一行
return false;
}
if (tempCol == col)
//同一列
if (tempRow - tempCol == row - col || tempRow + tempCol == row + col)
}
return true;
}
設定一個函數,用于查找col列後的皇後擺放方法:
/// <summary>
/// 在第col列尋找安全的row值
/// </summary>
/// <param name="queenList"></param>
/// <param name="col"></param>
/// <returns></returns>
public bool PlaceQueue(int[] queenList, int col)
int row = 0;
bool foundSafePos = false;
if (col == 8) //結束标志
//當處理完第8列的完成
foundSafePos = true;
else
while (row < 8 && !foundSafePos)
if (IsSafe(col, row, queenList))
{
//找到安全位置
queenList[col] = row;
//找下一列的安全位置
foundSafePos = PlaceQueue(queenList, col + 1);
if (!foundSafePos)
{
row++;
}
}
else
row++;
return foundSafePos;
調用方法:
static void Main(string[] args)
EightQueen eq = new EightQueen();
int[] queenList = new int[8];
for (int j = 0; j < 8; j++)
Console.WriteLine("-----------------"+j+"---------------------");
queenList[0] = j;
bool res = eq.PlaceQueue(queenList, 1);
if (res)
Console.Write(" ");
for (int i = 0; i < 8; i++)
Console.Write(" " + i.ToString() + " ");
Console.WriteLine("");
Console.Write(" "+i.ToString()+" ");
for (int a = 0; a < 8; a++)
{
if (i == queenList[a])
{
Console.Write(" q ");
}
else
Console.Write(" * ");
Console.WriteLine("");
Console.WriteLine("---------------------------------------");
else
Console.WriteLine("不能完成棋局,棋局失敗!");
Console.Read();
遞歸算法PlaceQueue,完成這樣的功能:它尋找第col列後的皇後的安全擺放位置,如果該函數傳回了false,表示目前進入了死胡同,需要進行回溯,直到為0-7列都找
到了安全位置或者找遍這些列都找不到安全位置的時候終止。
用遞歸算法解決8皇後問題的示例程式:
<a href="http://files.cnblogs.com/jillzhang/EightQueens.rar">/Files/jillzhang/EightQueens.rar</a>
歡迎大家下載下傳;
-----------------------------------------------------------------------------------------------------------------
遞歸算法到這篇為止,已經學習到了分而治之,動态程式設計,回溯等重要思想,也用這些問題解決了一些具體問題,比如排序,背包,8皇後問題等,通過對理論的學習
和對實際問題的解決,充分了解遞歸算法的使用方法。在編寫學習系列的過程中,絕大多數都參考資料結構C++語言描述-應用标準模闆庫 ,特此感謝原書作者:
William Ford,William Topp,和譯者陳軍。
下一系列主要想通過6-8篇的篇幅來學習圖論的基礎知識。多謝大家支援。