第六章 隨機(jī)化算法

《第六章 隨機(jī)化算法》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、第五章搜索法?175均等待時(shí)間是n個(gè)顧客等待服務(wù)時(shí)間的總和除以n。5-10整數(shù)變換問題。關(guān)于整數(shù)i的變換f和g定義如下：f(i)=3i，g(i)=??i/2??。試設(shè)計(jì)一個(gè)算法，對(duì)于給定的兩個(gè)個(gè)整數(shù)n和m，用最少的f和g變換次數(shù)將n變換為m。例如，可以將整數(shù)15用4次變換將它變換為整數(shù)4：4=gfgg(15)。當(dāng)整數(shù)n不可能變換為整數(shù)m時(shí)，算法應(yīng)如何處理?5-11推箱子問題。碼頭倉庫是劃分為n×m個(gè)格子的矩形陣列。有公共邊的格子是相鄰格子。當(dāng)前倉庫中有的格子是空閑的；有的格子則已經(jīng)堆放了沉重的貨物。由于堆放的貨物很重，單憑倉庫管理員的力量是無法移動(dòng)的。倉庫管理員有一項(xiàng)任務(wù)，要將一

2、個(gè)小箱子推到指定的格子上去。管理員可以在倉庫中移動(dòng)，但不能跨過已經(jīng)堆放了貨物的格子。管理員站在與箱子相對(duì)的空閑格子上時(shí)，可以做一次推動(dòng)，把箱子推到另一相鄰的空閑格子。推箱子只能向管理員的對(duì)面方向推。由于要推動(dòng)的箱子很重，倉庫管理員想盡量減少推箱子的次數(shù)。請(qǐng)?jiān)O(shè)計(jì)一算法，使倉庫管理員推箱子的次數(shù)最少。5-12噴漆機(jī)器人。F大學(xué)開發(fā)出一種噴漆機(jī)器人Rob，能用指定顏色給一塊矩形材料噴漆。Rob每次拿起一種顏色的噴槍，為指定顏色的小矩形區(qū)域噴漆。噴漆工藝要求，一個(gè)小矩形區(qū)域只能在所有緊靠它上方的矩形區(qū)域都噴過漆后，才能開始噴漆，且小矩形區(qū)域開始噴漆后必須一次性噴完，不能只噴一部分。為Ro

3、b編寫一個(gè)自動(dòng)噴漆程序，使Rob拿起噴槍的次數(shù)最少。PrinttoPDFwithoutthismessagebypurchasingnovaPDF(http://www.novapdf.com/)第六章隨機(jī)化算法教學(xué)目標(biāo)理解產(chǎn)生偽隨機(jī)數(shù)的線性同余法掌握數(shù)值隨機(jī)化算法的特點(diǎn)及應(yīng)用掌握蒙特卡羅算法的特點(diǎn)及應(yīng)用掌握拉斯維加斯算法的特點(diǎn)及應(yīng)用掌握舍伍德算法的特點(diǎn)及應(yīng)用前面各章討論的算法每一計(jì)算步驟都是確定的，而本章討論的隨機(jī)化算法允許算法在執(zhí)行過程中隨機(jī)地選擇下一個(gè)計(jì)算步驟，這種算法的新穎之處是把隨機(jī)性注入到算法之中，該策略使得算法的設(shè)計(jì)與分析更加靈活，其解決問題的能力也大為改觀。6.1

4、概述隨機(jī)化算法與現(xiàn)實(shí)生活息息相關(guān)，例如：人們經(jīng)常會(huì)通過擲色子來看結(jié)果，投硬幣來決定行動(dòng)，這就牽涉到一個(gè)問題：隨機(jī)。隨機(jī)化算法看上去是憑著運(yùn)氣做事。其實(shí)，這種算法是有一定的理論基礎(chǔ)的，且很少單獨(dú)使用，大多是與其他算法（如貪心法、查找算法等）配合起來運(yùn)用，求解效果往往出人意料。6.1.1隨機(jī)化算法的類型及特點(diǎn)隨機(jī)化算法的一個(gè)基本特征是：對(duì)所求解問題的同一實(shí)例用同一隨機(jī)化算法求解兩次可能得到完全不同的效果，這兩次求解問題所需的時(shí)間甚至所得到的結(jié)果可能會(huì)有相當(dāng)大的差別。一般情況下，可將隨機(jī)化算法大致分為四類：1．?dāng)?shù)值隨機(jī)化算法這類算法常用于數(shù)值問題的求解，所得到的解往往都是近似解，而且近

5、似解的精度隨計(jì)算時(shí)間的增加不斷提高。使用該算法的理由是：在許多情況下，待求解的問題在原理上可能就不存在精確解，或者說精確解存在但無法在可行時(shí)間內(nèi)求得，因此用數(shù)值隨機(jī)化算法可得到相當(dāng)滿意的解。2．蒙特卡羅算法蒙特卡羅算法是計(jì)算數(shù)學(xué)中的一種計(jì)算方法，它的基本特點(diǎn)是以概率與統(tǒng)計(jì)學(xué)中的理論和方法為基礎(chǔ)，以是否適合于在計(jì)算機(jī)上使用為重要標(biāo)志。蒙特卡羅是摩納哥的一個(gè)著名城市，以賭博聞名于世。為了表明該算法的上述基本特點(diǎn)，蒙特卡羅算法象征性地借用這一城市的名稱來命名。蒙特卡羅算法作為一種可行的計(jì)算方法，首先是由Ulam（烏拉姆）和VonNeumann（馮·諾依曼）在20世紀(jì)40年代中葉提出并加

6、以運(yùn)用，目的是為了解決研制核武器中的計(jì)算問題。該算法用于求問題的準(zhǔn)確解。對(duì)于許多問題來說，近似解毫無意義。例如，一個(gè)判定問題其解為“是”或“否”，二者必居其一，不存在任何近似解答。PrinttoPDFwithoutthismessagebypurchasingnovaPDF(http://www.novapdf.com/)第六章隨機(jī)化算法?177蒙特卡羅算法的特點(diǎn)是：它能求得問題的一個(gè)解，但這個(gè)解未必是正確的。求得正確解的概率依賴于算法執(zhí)行時(shí)所用的時(shí)間，所用的時(shí)間越多得到正確解的概率就越高。一般情況下，蒙特卡羅算法不能有效地確定求得的解是否正確。3．拉斯維加斯算法該算法絕不返回錯(cuò)

7、誤的解，也就是說，使用拉斯維加斯算法不會(huì)得到不正確的解，一旦找到一個(gè)解，那么這個(gè)解肯定是正確的。但是有時(shí)候拉斯維加斯算法可能找不到解。與蒙特卡羅算法類似，拉斯維加斯算法得到正確解的概率隨著算法執(zhí)行時(shí)間的增加而提高。對(duì)于所求解問題的任一實(shí)例，只要用同一拉斯維加斯算法對(duì)該實(shí)例反復(fù)求解足夠多的次數(shù)，可使求解失效的概率任意小。4．舍伍德算法當(dāng)一個(gè)確定性算法在最壞情況下的計(jì)算時(shí)間復(fù)雜性與其在平均情況下的計(jì)算復(fù)雜性有較大差異時(shí)，可在這個(gè)確定性算法中引入隨機(jī)性來降低最壞情況出現(xiàn)的概率，進(jìn)而消除