摘要:八皇后問題是十九世紀著名的數學家高斯年提出。同時可以擴展為九皇后,十皇后問題。解決方案回溯與遞歸。這樣,編譯器或者解釋器就可以把尾遞歸做優化,使遞歸本身無論調用多少次,都只占用一個棧幀,不會出現棧溢出的情況。
八皇后問題是十九世紀著名的數學家高斯1850年提出 。以下為python語言的八皇后代碼,摘自《Python基礎教程》,代碼相對于其他語言,來得短小且一次性可以打印出92種結果。同時可以擴展為九皇后,十皇后問題。
問題:在一個8*8棋盤上,每一行放置一個皇后旗子,且它們不沖突。沖突定義:同一列不能有兩個皇后,每一個對角線也不能有兩個皇后。當然,三個皇后也是不行的,四個也是不行的,憑你的智商應該可以理解吧。
解決方案:回溯與遞歸。
介紹:
1.回溯法
回溯法是一種選優搜索法,按選優條件向前搜索,以達到目標。當探索到某一步時,發現原先選擇并不優或達不到目標,就退回一步重新選擇,這種走不通就退回再走的技術為回溯法,而滿足回溯條件的某個狀態的點稱為“回溯點”。參見百度百科
2.遞歸法
階乘 n! = 1 x 2 x 3 x ... x n
用函數fact(n)表示,可以看出:
fact(1) = 1 fact(n) = n! = 1 x 2 x 3 x ... x (n-1) x n = (n-1)! x n = fact(n-1) x n
于是,fact(n)用遞歸的方式寫出來就是:
def fact(n): if n==1: return 1 return n * fact(n - 1)
如果計算fact(5),結果如下:
===> fact(5) ===> 5 * fact(4) ===> 5 * (4 * fact(3)) ===> 5 * (4 * (3 * fact(2))) ===> 5 * (4 * (3 * (2 * fact(1)))) ===> 5 * (4 * (3 * (2 * 1))) ===> 5 * (4 * (3 * 2)) ===> 5 * (4 * 6) ===> 5 * 24 ===> 120
使用遞歸函數需要注意防止棧溢出。在計算機中,函數調用是通過棧(stack)這種數據結構實現的,每當進入一個函數調用,棧就會加一層棧幀,每當函數返回,棧就會減一層棧幀。由于棧的大小不是無限的,所以,遞歸調用的次數過多,會導致棧溢出。可以試試fact(1000):
>>> fact(1000) Traceback (most recent call last): File "", line 1, in File " ", line 4, in fact ... File " ", line 4, in fact RuntimeError: maximum recursion depth exceeded
解決遞歸調用棧溢出的方法是通過尾遞歸優化。
尾遞歸是指,在函數返回的時候,調用自身本身,并且,return語句不能包含表達式。這樣,編譯器或者解釋器就可以把尾遞歸做優化,使遞歸本身無論調用多少次,都只占用一個棧幀,不會出現棧溢出的情況。如:
def factorial(n, acc=1): if n == 0: return acc return factorial(n-1, n*acc)
函數返回時只調用了它本身factorial(n-1, n*acc)
問題是Python標準的解釋器沒有針對尾遞歸做優化,任何遞歸函數都存在棧溢出的問題。
python源碼:
# -*- coding: utf-8 -*- #python默認為ascii編碼,中文編碼可以用utf-8 import random #隨機模塊 def conflict(state,col): #沖突函數,row為行,col為列 row=len(state) for i in range(row): if abs(state[i]-col) in (0,row-i):#重要語句 return True return False def queens(num=8,state=()): #生成器函數 for pos in range(num): if not conflict(state, pos): if len(state)==num-1: yield(pos,) else: for result in queens(num, state+(pos,)): yield (pos,)+result def queenprint(solution): #打印函數 def line(pos,length=len(solution)): return ". "*(pos)+"X "+". "*(length-pos-1) for pos in solution: print line(pos) for solution in list(queens(8)): print solution print " total number is "+str(len(list(queens()))) print " one of the range is: " queenprint(random.choice(list(queens())))
結果:
(0, 4, 7, 5, 2, 6, 1, 3) (0, 5, 7, 2, 6, 3, 1, 4) (0, 6, 3, 5, 7, 1, 4, 2) (0, 6, 4, 7, 1, 3, 5, 2) (1, 3, 5, 7, 2, 0, 6, 4) (1, 4, 6, 0, 2, 7, 5, 3) (1, 4, 6, 3, 0, 7, 5, 2) (1, 5, 0, 6, 3, 7, 2, 4) (1, 5, 7, 2, 0, 3, 6, 4) (1, 6, 2, 5, 7, 4, 0, 3) (1, 6, 4, 7, 0, 3, 5, 2) (1, 7, 5, 0, 2, 4, 6, 3) (2, 0, 6, 4, 7, 1, 3, 5) (2, 4, 1, 7, 0, 6, 3, 5) (2, 4, 1, 7, 5, 3, 6, 0) (2, 4, 6, 0, 3, 1, 7, 5) (2, 4, 7, 3, 0, 6, 1, 5) (2, 5, 1, 4, 7, 0, 6, 3) (2, 5, 1, 6, 0, 3, 7, 4) (2, 5, 1, 6, 4, 0, 7, 3) (2, 5, 3, 0, 7, 4, 6, 1) (2, 5, 3, 1, 7, 4, 6, 0) (2, 5, 7, 0, 3, 6, 4, 1) (2, 5, 7, 0, 4, 6, 1, 3) (2, 5, 7, 1, 3, 0, 6, 4) (2, 6, 1, 7, 4, 0, 3, 5) (2, 6, 1, 7, 5, 3, 0, 4) (2, 7, 3, 6, 0, 5, 1, 4) (3, 0, 4, 7, 1, 6, 2, 5) (3, 0, 4, 7, 5, 2, 6, 1) (3, 1, 4, 7, 5, 0, 2, 6) (3, 1, 6, 2, 5, 7, 0, 4) (3, 1, 6, 2, 5, 7, 4, 0) (3, 1, 6, 4, 0, 7, 5, 2) (3, 1, 7, 4, 6, 0, 2, 5) (3, 1, 7, 5, 0, 2, 4, 6) (3, 5, 0, 4, 1, 7, 2, 6) (3, 5, 7, 1, 6, 0, 2, 4) (3, 5, 7, 2, 0, 6, 4, 1) (3, 6, 0, 7, 4, 1, 5, 2) (3, 6, 2, 7, 1, 4, 0, 5) (3, 6, 4, 1, 5, 0, 2, 7) (3, 6, 4, 2, 0, 5, 7, 1) (3, 7, 0, 2, 5, 1, 6, 4) (3, 7, 0, 4, 6, 1, 5, 2) (3, 7, 4, 2, 0, 6, 1, 5) (4, 0, 3, 5, 7, 1, 6, 2) (4, 0, 7, 3, 1, 6, 2, 5) (4, 0, 7, 5, 2, 6, 1, 3) (4, 1, 3, 5, 7, 2, 0, 6) (4, 1, 3, 6, 2, 7, 5, 0) (4, 1, 5, 0, 6, 3, 7, 2) (4, 1, 7, 0, 3, 6, 2, 5) (4, 2, 0, 5, 7, 1, 3, 6) (4, 2, 0, 6, 1, 7, 5, 3) (4, 2, 7, 3, 6, 0, 5, 1) (4, 6, 0, 2, 7, 5, 3, 1) (4, 6, 0, 3, 1, 7, 5, 2) (4, 6, 1, 3, 7, 0, 2, 5) (4, 6, 1, 5, 2, 0, 3, 7) (4, 6, 1, 5, 2, 0, 7, 3) (4, 6, 3, 0, 2, 7, 5, 1) (4, 7, 3, 0, 2, 5, 1, 6) (4, 7, 3, 0, 6, 1, 5, 2) (5, 0, 4, 1, 7, 2, 6, 3) (5, 1, 6, 0, 2, 4, 7, 3) (5, 1, 6, 0, 3, 7, 4, 2) (5, 2, 0, 6, 4, 7, 1, 3) (5, 2, 0, 7, 3, 1, 6, 4) (5, 2, 0, 7, 4, 1, 3, 6) (5, 2, 4, 6, 0, 3, 1, 7) (5, 2, 4, 7, 0, 3, 1, 6) (5, 2, 6, 1, 3, 7, 0, 4) (5, 2, 6, 1, 7, 4, 0, 3) (5, 2, 6, 3, 0, 7, 1, 4) (5, 3, 0, 4, 7, 1, 6, 2) (5, 3, 1, 7, 4, 6, 0, 2) (5, 3, 6, 0, 2, 4, 1, 7) (5, 3, 6, 0, 7, 1, 4, 2) (5, 7, 1, 3, 0, 6, 4, 2) (6, 0, 2, 7, 5, 3, 1, 4) (6, 1, 3, 0, 7, 4, 2, 5) (6, 1, 5, 2, 0, 3, 7, 4) (6, 2, 0, 5, 7, 4, 1, 3) (6, 2, 7, 1, 4, 0, 5, 3) (6, 3, 1, 4, 7, 0, 2, 5) (6, 3, 1, 7, 5, 0, 2, 4) (6, 4, 2, 0, 5, 7, 1, 3) (7, 1, 3, 0, 6, 4, 2, 5) (7, 1, 4, 2, 0, 6, 3, 5) (7, 2, 0, 5, 1, 4, 6, 3) (7, 3, 0, 2, 5, 1, 6, 4) total number is 92 one of the range is: X . . . . . . . . . . . . . X . . . . X . . . . . . . . . X . . . . . . . . . X . X . . . . . . . . . . X . . . . . X . . . . .
源碼解析:
主要利用沖突函數檢測沖突,如果沖突則回溯,遞歸用到python的yield語句,該語句涉及python的生成器。
沖突函數:
def conflict(state,col): #沖突函數,row為行,col為列 row=len(state) for i in range(row): if abs(state[i]-col) in (0,row-i):#重要語句 return True return False
state為皇后的狀態,類型是一個元組,如(7, 3, 0, 2, 5, 1, 6, 4),元組是不可變對象,一經創建不能修改,元組是創建生成器的一種方法。
步驟:
假設第一行到第三行的皇后都沒沖突,這個時候要檢測第四行皇后是否沖突。如第一行皇后在第五列,第二行皇后在第八列,第三行皇后在第四列,檢驗第四行皇后放在哪一列不會沖突。
. . . . X . . . . . . . . . . X . . . X . . . .
這時state=(4,7,3),col=?
1.得出目前沒沖突行數row
row=len(state)
2.從1~row行依次檢測是否與row+1行皇后沖突
for i in range(row):
3.如果row+1行皇后所在的列col與其他行皇后的列相同或處于對角線,則沖突
if abs(state[i]-col) in (0,row-i):#重要語句 return True
以上語句翻譯為(其他行所在的列-要求檢測所在行的列)相差范圍為0~row-i則沖突。
傻瓜式教學:
第一行與第四行沖突,要么在同一列,要么在對角線,當對角線時列數相差3(因為第一行與第二行對角線相差1,第二行與第三行對角線相差1,則第一行與第三行對角線相差2,以此類推,第一行與第四行沖突,則相差3)
當第四行所在列col=4,這時abs ( state[0]-4 ) in (0 , 3-0)為真,因為4-4=0,如:
. . . . X . . . . . . . . . . X . . . X . . . . . . . . X . . . 同列沖突
當第四行所在列col=7,這時abs ( state[0]-7 ) in (0 , 3-0)為真,因為abs (4-7)=3,如:
. . . . X . . . . . . . . . . X . . . X . . . . . . . . . . . X 對角線沖突
你們這么聰明,該重要語句應該懂吧。
生成器函數:
def queens(num=8,state=()): #生成器函數 for pos in range(num): if not conflict(state, pos): if len(state)==num-1: yield(pos,) else: for result in queens(num, state+(pos,)): yield (pos,)+result
生成器:
通過列表生成式,我們可以直接創建一個列表。但是,受到內存限制,列表容量肯定是有限的。而且,創建一個包含100萬個元素的列表,不僅占用很大的存儲空間,如果我們僅僅需要訪問前面幾個元素,那后面絕大多數元素占用的空間都白白浪費了。所以,如果列表元素可以按照某種算法推算出來,那我們是否可以在循環的過程中不斷推算出后續的元素呢?這樣就不必創建完整的list,從而節省大量的空間。在Python中,這種一邊循環一邊計算的機制,稱為生成器(Generator)。
參考:生成器
步驟:
1.下面該語句為構建所有皇后擺放情況打下基礎。可以嘗試所有情況。
for pos in range(num):
2.如果不沖突,則遞歸構造棋盤。
if not conflict(state, pos):
3.如果棋盤狀態state已經等于num-1,即到達倒數第二行,而這時最后一行皇后又沒沖突,直接yield,打出其位置(pos, ),Python在顯示只有1個元素的元組時,也會加一個逗號,,以免你誤解成數學計算意義上的括號。
否則遞歸,打印(pos , )+ result
if len(state)==num-1: yield(pos,) else: for result in queens(num, state+(pos,)): yield (pos,)+result
傻瓜式教學:
例如pos=0,第一行放在第一列,這時不會沖突,但是不會進入if,因為還沒到達倒數第二行,進入else后,再調用queens(num, state+(pos,),這時進入第二行,再次遞歸展開則是queens(num,state+(pos, )+(pos, ) ),到達最后一行時返回(pos, ),再返回倒數第二行,再返回倒數第三行,最后到達最開始那層(pos, )+result, pos為第一行皇后所在列,result包含第二行皇后所在列和另一個result,就是這么復雜,希望好好琢磨。
優美格式的打印函數就不講了。
講講打印所有結果
for solution in queens(8): print solution
queens(8)因為生成器函數的for循環,每一次循環都會yield一個元組出來,所以有很多種情況,可以把它全部打出來。
也可以用list包裝成列表再統計一下多少種數目。
print " total number is "+str(len(list(queens()))
隨機優美打印一個棋盤情況:
print " one of the range is: " queenprint(random.choice(list(queens())))
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/43292.html
摘要:終止條件遞推公式遞歸的分類通過做大量的題,根據遞歸解決不同的問題,引申出來的幾種解決和思考的方式。我們通過層與層之間的計算關系用遞推公式表達出來做計算,經過層層的遞歸,最終得到結果值。 showImg(https://segmentfault.com/img/remote/1460000019222330); 前言 幾個月之前就想寫這樣一篇文章分享給大家,由于自己有心而力不足,沒有把真...
摘要:回溯法解八皇后帶詳細注解若出現小于則說明問題無解第一次檢測到新的一行回溯時運行的程序塊為已經檢測過并為能放置皇后的位置回溯過程中,遇到能放皇后的位置,說明這個位置在后面的驗證沒有通過,需要重新處理回溯時發現上一行也到行末需要繼續回溯回溯 /** * 回溯法解八皇后, 帶詳細注解 */ function NQueens(order) { if (order < 4) { ...
閱讀 2907·2021-11-19 09:40
閱讀 3578·2021-10-09 09:43
閱讀 2675·2021-09-22 15:31
閱讀 1724·2021-07-30 15:31
閱讀 782·2019-08-30 15:55
閱讀 3257·2019-08-30 15:54
閱讀 1161·2019-08-30 11:26
閱讀 1907·2019-08-29 13:00