國際大學生程序設計競賽試題與算法分析(二) 回溯算法.pdf

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