國際大學(xué)生程序設(shè)計(jì)競(jìng)賽試題與算法分析(二) 回溯算法.pdf

信意章賽 令毋次豢緒常尋嗽分瀟寥 試題與算法分析 二 回溯 耳法 郭篙山 吳漢榮 中山大學(xué)信息科技學(xué)院計(jì)算機(jī)科學(xué)系 廣州 我 們?cè)谌粘Ｉ钪薪?jīng)常會(huì)遇到 一 些 要求最優(yōu) 解 的問題 比如說從一個(gè) 城市到另一個(gè) 城 市怎么走 才最快 怎么走 才最省錢 但 是在處理一些 最優(yōu)解 的問題 方面 沒有任何的理論也無法采用精確 的數(shù) 學(xué)公式來 幫助我們 找到最優(yōu)解 我們只能求 助于窮 舉搜索方法 在 這 里 我們介紹 一種 系 統(tǒng) 化 的窮舉 搜索技術(shù) 稱 為回溯技術(shù) 所謂 的回溯技術(shù)就是像 人走迷 宮一樣 先選擇 一個(gè)前 進(jìn) 方 向嘗試 一步步 往 前 試 探 在遇到死 胡 同不能再往前的時(shí)候 就回退到上 一個(gè)分叉點(diǎn) 選 另 一個(gè) 方向嘗試 而在前進(jìn)和回撤 的路上都設(shè)置 一些 標(biāo)記 以便 能正 確返回 直 到達(dá)到目標(biāo) 或 者 所有 的 可行方案都已經(jīng) 嘗試完 為止 在通 常的情況下 我 們使用遞 歸方 式來 實(shí)現(xiàn)回溯技術(shù) 也就是在每 一個(gè) 分叉 點(diǎn)進(jìn) 行遞 歸 嘗試 在回溯時(shí)通 常采用棧來 記 錄回溯過程 使用棧可使窮舉過 程能回溯到所要位 置 并 繼續(xù) 在指 定層 次上往 下 窮 舉 所 有可能 的解 回溯算法可以用偽碼 描述 如下 當(dāng)前狀態(tài) 當(dāng)前狀 態(tài)等于目標(biāo)狀態(tài) 對(duì)所有可能的新狀態(tài) 新狀態(tài) 回溯算法 是一種十分 常用的算法 象一 些經(jīng)典 問題如八皇后 問題 騎士周游問題 地圖著色問題 都可以采用回溯算 法 來解 本期將 刊登題歷年 的國際決賽 和區(qū)域賽試題 供讀者分析和學(xué)習(xí) 每道題都先給 出題目 然后是算法分析 由于篇幅所 限 我們只 給 出主要 的解 題思路和算 法分析 具體的程序?qū)?現(xiàn) 留給讀者 自行 完成 第一題骨牌矩陣 問題描述 多米諾骨牌是一個(gè)小正方形方塊 每個(gè)骨牌都 標(biāo) 有 一 個(gè) 數(shù) 字 一 現(xiàn) 在 有組 骨 牌 每 組兩 個(gè) 各組編 號(hào) 為 一 每組編 號(hào)對(duì)應(yīng) 的兩個(gè)骨牌數(shù) 值如下 骨骨牌組組骨牌牌 骨牌組組骨牌牌 骨牌組 組 骨牌牌骨牌組組骨牌牌 編編號(hào)號(hào)號(hào)編號(hào)號(hào)號(hào)編號(hào) 號(hào)號(hào) 編號(hào)號(hào)號(hào) 現(xiàn)將這組骨牌排 成一 個(gè)矩 陣 此 時(shí)只 能看到每個(gè)骨牌上的數(shù) 字 一 而 不能知 道每組 的組 號(hào) 如圖所示 請(qǐng)編程將每組 骨牌分辨 出來 見 圖 圖中數(shù)字 為對(duì)應(yīng)圖每組骨牌的編號(hào) 骨牌擺放可旋轉(zhuǎn) 例如第組 骨牌經(jīng)旋 轉(zhuǎn)可得以 種放法 萬 了 第 屆亞洲臺(tái) 匕賽區(qū) 中山大學(xué)隊(duì)教練 第屆 亞洲臺(tái)能賽區(qū)中山大學(xué)隊(duì)隊(duì)長 晦 衛(wèi)衛(wèi) 翻 鈞仆 偽 仲 曾 并翎饑 匕心公未 從杏少 湘用 骨牌矩陣骨牌組編號(hào)矩陣 圖圖 如場(chǎng) 比 代曰 曰 什 州 替異知饑 匕 心 兮 術(shù) 片未少毛如剮 輸入格式 從鍵 盤輸 人一個(gè) 文本文件的文件 名 該 文 件 包含了一個(gè)行列 的骨牌矩 陣 每 行有個(gè) 一 的整數(shù) 每個(gè)整數(shù)之間用空格 分開 每 行 的行 首 行末無多余空格 榆出格式 答案輸 出到一個(gè) 文本 文件 中 文件 名由鍵 盤輸 人 若問題無解 則輸 出憶 若問題有解 則將 所 有 可能的解 輸出 每個(gè) 解之 間用一個(gè)空行分開 最后輸 出解 的總數(shù) 數(shù) 字 間用空格分開 算法分析 這題的算法比較簡單 只需使用標(biāo) 準(zhǔn) 的回溯算 法 而且由于本 題的規(guī) 模比較 小 不需要對(duì)算 法進(jìn) 行優(yōu)化 既可滿足 時(shí)間上 的要求 在骨牌矩陣中 每組 骨牌既可以橫 放也可以豎 放 我們可以按 從左 到右從上到下 的順 序 對(duì) 骨牌 矩 陣中的每個(gè)位置進(jìn) 行回溯 判 斷相應(yīng) 的骨牌組應(yīng) 該是 橫 放 還是豎放 最 終目標(biāo) 就 是 要 求 二 十八組 骨牌 組都能夠 不 重 復(fù) 地 排 成 一個(gè)的矩 陣 而 且每個(gè)骨牌上 的數(shù)字和輸人 的骨牌矩 陣一一對(duì)應(yīng) 還要求 每組骨 牌不互相重疊 例程中的過 程 就 是 用于 回溯的 遞 歸 過 程 它先 查 找下 一個(gè)還 沒放置骨 牌的位 置 較 如已 經(jīng)超 過 矩 陣 的范 圍 而且 所 有的骨牌組已經(jīng)放置 好 則 表示已經(jīng) 找 到一 個(gè)解 將 它輸 出否則 按四 種方式嘗試放 置個(gè)骨牌組 假 如成 功則嘗試 放置 下 一個(gè)骨牌組 假 如不成 功就回溯 核心算法是 遞歸放 置一個(gè)骨牌組 信 滬息穿賽 查 找 下一 個(gè)還 沒放置骨牌的位置 力 若沒有 則表示已經(jīng)找 到一個(gè)解 輸出 返回 把在 處 的骨牌作 為 當(dāng)前骨牌組 的一個(gè)骨牌 把在川處 的骨牌作為當(dāng)前骨牌組的 另一個(gè)骨 牌 判斷 當(dāng)前骨 牌 組是否 未 被使用 如果未被使用則遞歸 放 置下一個(gè)骨牌組 把在 處的骨 牌作為當(dāng)前骨牌組的另一個(gè)骨牌 判 斷 當(dāng)前骨 牌 組是否未被使用 如果未被使用 則遞歸放 置下 一 個(gè)骨 牌組 兩種嘗 試都失 敗 進(jìn) 行回溯 第二題求馬的不同走法總數(shù) 問題描述 在 一個(gè)的棋 盤 上 馬的起 始 位置坐標(biāo) 縱 橫位 置由鍵 盤輸人 求馬能返回初 始位置的 所有不同走法 的總數(shù)馬走 過 的位置不能重復(fù) 馬 走 舊 字 算法分析 由于棋盤 的大小只有 所以只需使用回 溯算法 搜索馬能返回初 始 位 置的所 有不同走法 效率基本上能達(dá)到要求 遞歸的回溯算法 可描述 為 是 當(dāng)前位置 馬從當(dāng)前位 置出發(fā) 走 一 步 到位置的每 一 種走法 在棋盤內(nèi)位置沒有走 過 出發(fā)點(diǎn)不同走 法 總數(shù)加 標(biāo)記 已經(jīng)走 過了 取消位置 的標(biāo)記 下面討論算法的具體實(shí)現(xiàn) 棋盤用坐標(biāo)表示 點(diǎn) 表示棋盤上任一個(gè) 點(diǎn) 的范圍是 從 出發(fā) 下 一 步 最多有個(gè)位 置 記 為 若 用表示這個(gè)方 向 則 即馬從點(diǎn) 出發(fā) 首先沿的方向行進(jìn) 當(dāng) 在此方 向走完所有 的不同走法后 就 進(jìn) 行回溯 改 變 二 方向繼續(xù)行進(jìn) 乃 信 矛窟章賽 各點(diǎn)坐標(biāo)的計(jì)算 設(shè)點(diǎn)坐標(biāo)為 則能到 達(dá)點(diǎn)的坐標(biāo)分 別為 一 一 一 一 一 一 為 簡化坐標(biāo)的計(jì)算 引人增 量數(shù)組 二 一 一 一 一 一一 一一 則按方向能到達(dá)點(diǎn)的坐標(biāo)是 霎霎霎霎霎霎霎霎霎霎霎霎霎霎霎 入入入入入才才才才 么么夕夕 聲 產(chǎn)產(chǎn)產(chǎn) 尹產(chǎn) 產(chǎn) 門門卜卜 夕夕夕夕夕側(cè)側(cè)側(cè)側(cè) 圖馬的八種不同走法 第三題求不 連續(xù)重復(fù)字 符序列 問題描述 由大寫字母 中前個(gè) 字母 組成 字 符序列 所 謂不連續(xù)重復(fù) 字符序列是 指 字符序列中 無連續(xù) 重復(fù)的子 串 例如 以下為有連續(xù)重復(fù) 字 串的字符序列 又如以下為沒有連續(xù)重復(fù) 字 串的字符序列 輸入和輸出 請(qǐng)編寫程 序 讀人 整數(shù)和 其中 輸出第個(gè)由前個(gè) 字母 組 成 的不連 續(xù) 重復(fù)字符序列 以及這個(gè) 序列 的長度 顯然 第 個(gè)不連續(xù) 重復(fù) 字符序列 為 假 定 由給出的和 中至少存在個(gè)不連續(xù)重復(fù) 序列 例如當(dāng)時(shí) 前個(gè)不連續(xù) 重復(fù)序列為 由于所輸出序列 可能很長 因此輸出時(shí)以每 個(gè)字母 為組 每組用個(gè)空格分開 每行個(gè) 字 符 輸人以兩個(gè)時(shí)用 空格分開結(jié)束 輸人樣例 輸出樣例 算法分析 由于只要求最大 為 所以只需使用回溯 算法 搜索生成前個(gè)不連續(xù)重復(fù) 字符序列并輸 出 第個(gè)不 連續(xù)重復(fù)字符序列 即可 測(cè)試 時(shí)保證不會(huì) 超時(shí) 本題的關(guān)鍵 在于判斷字 符 序列有無連續(xù)重復(fù) 字 串 由于 我們是一面搜索一面判斷的 因此 當(dāng)需 要判斷一個(gè)長度 為的字符序列有 無連續(xù)重復(fù) 字 串時(shí) 可以確保 前 一 個(gè) 字符的序列沒 有連續(xù)重 復(fù)字串 只需檢查包含第個(gè)字符的字串即可 因 為如果這個(gè) 字符序列含有連續(xù)重 復(fù)字 串 則必 定是 由第個(gè) 字符造成 的 判斷字符序列有無 連 續(xù)重復(fù) 字 串的函數(shù)可 描述為 檢查 長度為的字 串 一 一 返回有 連續(xù) 重復(fù)字串 返回沒有連續(xù)重復(fù)字串 需要注意的 一點(diǎn)是本 題 最好使用非遞 歸 的搜 索算法 否則容易造成堆棧溢 出 可以考慮的優(yōu)化措施有 為了提高信息 的利 用率 對(duì) 每個(gè)字符序 列 若沒有搜索過 可搜索至 生成前個(gè)不連續(xù)重 乃 翻 場(chǎng)少找 曰 什 州 枯豆 翎饑 匕心琶 未 八上下少七湘用 信息竟賽 復(fù)字符序列并 用一個(gè) 字符 串?dāng)?shù)組記錄搜 索過程 然 后從 中還原出第個(gè)字符 序列輸出若已經(jīng)搜索 過 直接從中還 原出第個(gè)字符序列并輸 出 當(dāng) 時(shí) 所 產(chǎn) 生 的前個(gè)序列是 相 同 的 所以可以直接調(diào) 用的結(jié) 果 求不連續(xù)重復(fù)字符序列 可描述 為 初始化 讀人新 的和 輸人合法 協(xié) 聲 遷 的字 申還未產(chǎn)生產(chǎn)生的字串 還原 出第個(gè)序列并輸出 二二 把新的序列 添加人記錄字串田 已經(jīng)產(chǎn)生了 個(gè)字符序列停止搜索 二 二 的前一個(gè)字符初始化下一層 的搜索 一 回退一 層 把 添加人記錄字 串田 還原的過程可描述為 記 錄搜索過 程和還 原出第個(gè) 字 串 的 實(shí) 現(xiàn) 方 法有很 多 這里對(duì)我使用 的方法做簡單說明 非遞 歸 的搜索過程可描述 為 當(dāng)前搜索的深度 二 的前一個(gè)字符 當(dāng)前生成 的字符序列 連 還未生成個(gè)字符序列 二 前 個(gè)字母 沒有連續(xù)重復(fù)字 串 讓 一 刪 除的最后一個(gè)字符 二 口 中存放 的是還原 出來 的字 串 例如 二 時(shí) 搜 索 結(jié) 束后 記錄以下字 符 串 一 一 一 表示 往回退 一位 此 字 串可表示 二 時(shí) 的個(gè) 序列 然后還原出第個(gè)序列并輸 出 收稿日期 一一 北女女女北流流女女流女女流女女流女流女女北北女女女女北女流流女女交流流北女女北北流女北北 上接第頁 翻 壞 飾 樣 踐 曰 仲 們 曹 開知仇 匕 心分未 從山少七湘用 數(shù)據(jù)庫包含了主數(shù)據(jù)庫以及 帳號(hào)權(quán) 限 統(tǒng)計(jì) 匯 總等輔 助數(shù)據(jù)庫 系統(tǒng)管理模塊 的功能包 含 系統(tǒng)初始化 原始 數(shù) 據(jù) 的 錄人和修 改 數(shù) 據(jù)定 期 備 份 定 期 統(tǒng) 計(jì)收費(fèi)額 并自動(dòng)劃 款 發(fā)送 電子郵件等子 功 能 安 全 維 護(hù)模 塊 有 帳號(hào)管理 權(quán) 限管理 操 作跟 蹤用日志記錄 等功能 實(shí)現(xiàn)用戶安全性 數(shù)據(jù)安全性 操作安全性 的全面管理 這種 系統(tǒng)結(jié)構(gòu)模 塊 化程