亚洲免费av电影一区二区三区,日韩爱爱视频,51精品视频一区二区三区,91视频爱爱,日韩欧美在线播放视频,中文字幕少妇AV,亚洲电影中文字幕,久久久久亚洲av成人网址,久久综合视频网站,国产在线不卡免费播放

        ?

        回溯算法

        2011-10-18 09:42:30王鳳紅
        中國現(xiàn)代教育裝備 2011年14期
        關(guān)鍵詞:最優(yōu)性九宮格約束條件

        王鳳紅

        回溯算法

        王鳳紅

        回溯算法是程序設計中最重要的基礎算法之一,也是搜索算法中的一種控制策略,回溯算法的基本思想是:從一條路往前走,能進則進,不能進則退回來,選擇另外一條路再走。它是從初始狀態(tài)出發(fā),運用題目給出的條件、規(guī)則,按照深度優(yōu)先搜索的順序擴展所有可能情況,從中找出滿足題意要求的解答?;厮莘ㄊ乔蠼馓厥庑陀嫈?shù)題或較復雜的枚舉題中使用頻率最高的一種算法。

        一、回溯算法說明

        1.算法定義

        回溯算法是搜索算法中的一種控制策略。它在包含問題的所有解的解空間樹中,按照深度優(yōu)先的策略,從根結(jié)點出發(fā)搜索解空間樹。算法搜索至解空間樹的任一結(jié)點時,總是先判斷該結(jié)點是否肯定不包含問題的解,如果肯定不包含,則跳過對以該結(jié)點為根的子樹的系統(tǒng)搜索,逐層向其祖先結(jié)點回溯。否則進入該子樹,繼續(xù)按深度優(yōu)先的策略進行搜索。回溯算法在用來求問題的所有解時,要回溯到根,且根結(jié)點的所有子樹都已被搜索遍才結(jié)束?;厮菟惴ㄔ谟脕砬髥栴}的任一解時,只要搜索到問題的一個解就可以結(jié)束。這種以深度優(yōu)先的方式系統(tǒng)地搜索問題的解的算法稱為回溯算法。

        2.算法描述

        回溯算法描述如下:

        二、經(jīng)典例題分析

        [問題描述]

        八皇后問題是一個古老而著名的問題,是回溯算法的典型例題。該問題由19世紀著名的數(shù)學家高斯于1850年提出:在8×8格的國際象棋上擺放8個皇后,使其不能互相攻擊,即任意兩個皇后都不能處于同一行、同一列或同一斜線上,問有多少種擺法。高斯認為有76種方案。1854年在柏林的象棋雜志上不同的作者發(fā)表了40種不同的解,后來有人用圖論的方法解出92種結(jié)果??梢杂没厮莸乃惴ㄇ蟪鲞@92種結(jié)果。圖1是其中的一種結(jié)果。(Q表示皇后的位置)

        圖1

        1.算法分析

        (1)具體設計思路:任意2個皇后都不能處于同一行、同一列或同一斜線上,所以我們從第一列開始放,看看每一列的皇后都放在哪一行上就可以了。所有可能的情況全部試驗一遍,找出滿足條件的92種結(jié)果。

        (2)定義狀態(tài):即如何描述問題求解過程中每一步的狀況。在八皇后問題中,將行位置作為狀態(tài)。

        (3)邊界條件:即在什么情況下程序不再遞歸下去。在八皇后問題中,將等于n+1(產(chǎn)生一種成功放法)作為邊界條件。如果是求滿足某個特定條件的一條最佳路徑,則當前狀態(tài)到達邊界時并非一定意味著此時就是最佳目標狀態(tài)。因此還須增加判別最優(yōu)目標狀態(tài)的條件。

        (4)搜索范圍:在當前狀態(tài)不滿足邊界條件的情況下,應如何設計算符值的范圍。換句話說,如何設定for語句中循環(huán)變量的初值和終值。在八皇后問題中,每列的行位置i作為搜索范圍,即1≤i≤n。

        (5)約束條件和最優(yōu)性要求:所謂約束條件是指,當前擴展出一個子結(jié)點后應滿足什么條件方可繼續(xù)遞歸下去;如果是求滿足某個特定條件的一條最佳路徑,那么在擴展出某個子狀態(tài)后是否繼續(xù)遞歸搜索下去,不僅取決于子狀態(tài)是否滿足約束條件,而且還取決于子狀態(tài)是否滿足最優(yōu)性要求。在八皇后問題中,將k列的皇后放在第i行上,不產(chǎn)生攻擊(place=true)作為約束條件。

        (6)參與遞歸運算的參數(shù):將參與遞歸運算的參數(shù)設為遞歸子程序的值參或局部變量。若這些參數(shù)的存儲量大(例如數(shù)組)且初始值需由主程序傳入,為避免內(nèi)存溢出,則必須將其設為全局變量,且回溯前需恢復其遞歸前的值。在八皇后問題中,將皇后的列作為參與遞歸運算的參數(shù)。

        2.程序清單

        [問題描述]

        九宮格問題:九宮格游戲規(guī)則,1~9這九個數(shù)字,思考怎么填入三行三列的方格中,要求使每行、每列、兩條對角線上的數(shù)字之和都相等。

        九宮格這個游戲不僅僅考驗人的數(shù)字推理能力,也同時考驗了人的思維邏輯能力,對人們的思維鍛煉有著極大的作用,從古時起人們便意識到九宮的教育意義。千百年來影響巨大,在文學、影視中都曾出現(xiàn)過。九宮格最早叫“洛書”,現(xiàn)在也叫“幻方”。

        在《射雕英雄傳》中黃蓉曾破解九宮格,口訣:戴九履一,左三右七,二四有肩,八六為足,五居中央,如圖2所示。

        圖2

        1.算法分析

        列出所有可能的情況從中找出符合條件的解。從第一行第一列開始,找一個還沒有填過的數(shù)填上,然后就填下一個。當所有可能的填法都試驗完了以后就回溯到上一個數(shù),試驗還沒有填過的數(shù)。直到九個格全部填完之后,驗證是不是符合條件。第一種填法是圖3中的a,然后變換到b,再變換到c……最后一種填法是e。

        一共有9×8×7×6×5×4×3×2×1=362880種填法,對于每一種填法都驗證每行、每列、對角線上的和是不是等于15,其中有8種填法符合每行、每列、對角線之和都等于15。

        (1)定義狀態(tài):填的第h行,第l列作為狀態(tài)。

        (2)邊界條件:當h=3,l=4說明已經(jīng)填完一種方案;

        (3)搜索范圍:這9個數(shù):l≤i≤9;

        (4)約束條件和最優(yōu)性要求:約束條件是這個數(shù)沒有被填過,找到一個就填上,然后填下一個位置(h,l+1);

        (5)參與遞歸運算的參數(shù):填寫的第h行,第l列(h,l)。

        2.程序清單

        三、結(jié)束語

        利用這兩個經(jīng)典例題,能很好地訓練與掌握回溯算法,回溯算法可以解決很多的問題,是必須要掌握的算法之一。

        [1] 吳文虎,王建德.全國信息學奧林匹克聯(lián)賽培訓教程[M].北京:清華大學出版社,2005

        [2] 曹文仙.奧賽題型精解 高中信息學[M].北京:中國時代經(jīng)濟出版社,2010

        稿件編號:P1103127

        王鳳紅,本科,中教一級。

        山東省北鎮(zhèn)中學電教中心。

        猜你喜歡
        最優(yōu)性九宮格約束條件
        有趣的九宮格
        基于一種改進AZSVPWM的滿調(diào)制度死區(qū)約束條件分析
        二維Mindlin-Timoshenko板系統(tǒng)的穩(wěn)定性與最優(yōu)性
        DC復合優(yōu)化問題的最優(yōu)性條件
        成語九宮格
        不確定凸優(yōu)化問題魯棒近似解的最優(yōu)性
        解密九宮格
        A literature review of research exploring the experiences of overseas nurses in the United Kingdom (2002–2017)
        線性規(guī)劃的八大妙用
        大跨屋蓋結(jié)構(gòu)MTMD風振控制最優(yōu)性能研究
        精品国产一区二区三区男人吃奶 | 美腿丝袜日韩在线观看| 亚洲av无码专区国产乱码4se| 消息称老熟妇乱视频一区二区| 日日摸夜夜添夜夜添无码免费视频| 亚洲精品少妇30p| аⅴ资源天堂资源库在线| 亚洲综合国产精品一区二区99| 国产精品女同一区二区久| 亚洲成人av在线蜜桃| 人妻夜夜爽天天爽三区| 国产v视频| 亚洲二区三区四区太九| 狠狠久久av一区二区三区| 亚洲色图在线免费观看视频| 亚洲国产成人精品无码区二本| 97无码人妻Va一区二区三区| 国产精品亚洲av国产| 日本免费一区二区三区在线播放| 女女女女女裸体处开bbb| 无码中文字幕在线DVD| 亚洲乱色视频在线观看| 亚洲av老熟女一区二区三区| 人与动牲交av免费| 亚洲精品不卡电影| 国产精品农村妇女一区二区三区| 国产亚洲成性色av人片在线观| 国产综合无码一区二区色蜜蜜| 久久青草国产精品一区| 丰满少妇av一区二区三区| 免费无码又爽又刺激网站直播| 亚洲av日韩av无码av| 丰满少妇人妻无码超清 | 男女肉粗暴进来动态图| 亚州少妇无套内射激情视频| 九九99久久精品在免费线97| 亚洲福利二区三区四区| 极品嫩模高潮叫床| 久久se精品一区精品二区国产| 女人天堂av免费在线| 久久亚洲日韩精品一区二区三区|