【正文】 非最優(yōu)解。回溯到 B點(diǎn)，進(jìn)入 E結(jié)點(diǎn)搜索。最終，遍歷整個(gè)解空間得到最短路徑為（ A,B,C,F,L）搜索光盤(pán)順序?yàn)椋?1， 2， 3， 4）路徑總長(zhǎng)度為 15。 其操作流程可以分為兩個(gè)方面，一個(gè)是隨機(jī)存放，另一個(gè)是自動(dòng)取拿 。 2）自動(dòng)取拿：當(dāng)想從光碟存放槽中取拿需要的光碟時(shí)，在計(jì)算機(jī)中輸入關(guān)鍵字（如光碟的名字等），用直接或模糊的方法即可在數(shù)據(jù)庫(kù)中方便地找到相關(guān)光碟的信息；相應(yīng)點(diǎn)擊選定取出按鈕后，系統(tǒng)自動(dòng)尋找所要光碟的位置，并將信息發(fā)送到控制板，控制板通過(guò)地址選擇，確定光碟的位置，點(diǎn)亮指示光碟位置的指示燈；同時(shí)單片 機(jī)發(fā)送相應(yīng)的脈沖數(shù)，驅(qū)動(dòng)電機(jī)旋轉(zhuǎn)， 選擇最優(yōu)路徑， 拖動(dòng)撥盤(pán)裝置依次運(yùn)行到所選擇光碟的位置處，啟動(dòng)撥盤(pán)，將光碟自動(dòng)撥出存放位置。取多盤(pán)的最優(yōu)路徑規(guī)劃算法大大的提高了裝置取盤(pán)的 效率。在門(mén)上貼上畫(huà)圖，這樣不但更加美觀，而且起到防灰塵，防光照等效果。這樣既方便了光盤(pán)存放的識(shí)別操作，也提高了空間的使用效率。這樣我想能不能僅僅把光盤(pán)的目錄結(jié)構(gòu)通過(guò)CDROM 自動(dòng)保存起來(lái)，這樣既方面用戶對(duì)內(nèi)容進(jìn)行搜索，而且可以減輕工作人員的工作量。那么反過(guò)來(lái)，在輸入光碟信息時(shí)，我是不是可以利用這個(gè)信息來(lái)讓電腦自動(dòng)判斷某個(gè)光碟的信息是否已 經(jīng)保存到管理軟件中，沒(méi)有的話就自動(dòng)保存目錄結(jié)構(gòu)信息并且把這個(gè)光碟標(biāo)識(shí)信息保存起來(lái)。他能夠?qū)崿F(xiàn)對(duì)與已經(jīng)注冊(cè)的光盤(pán)就進(jìn)行讀取，沒(méi)有注冊(cè)的光盤(pán)就進(jìn)行提示。其實(shí)在掃描光盤(pán)信息時(shí)，得到的主要是光盤(pán)目錄的信息，如下圖： 圖 這里就利用了之前我學(xué)習(xí)的樹(shù)的遍歷知識(shí)，這里是使用了寬度優(yōu)先的算法，把每個(gè)文件夾中的文件和文件夾的名字信息分別保存起來(lái)。這樣，軟件的實(shí)用性就大大增強(qiáng)了。 該項(xiàng)技術(shù)以光碟儲(chǔ)存管理作為研究對(duì)象，實(shí)現(xiàn) “不需按分類(lèi)和固定位置存放”當(dāng)前倉(cāng)庫(kù)管理 一種 新理念 ，只要空間結(jié)構(gòu)合理，就可以運(yùn)用到其他物品 倉(cāng)庫(kù) 管理上 ， 具有十分廣泛的應(yīng)用前景和市場(chǎng)推廣價(jià)值。如果采用層疊式綜合設(shè)計(jì)模式（這是下一步實(shí)用化和產(chǎn)品化的設(shè)計(jì)思路），則可以在書(shū)柜大小的空間內(nèi)放置 5千到 8千張光碟。 以直接應(yīng)用于家庭為 一期目標(biāo)： 在產(chǎn)品化方面做一些提升，功能方面做一些精簡(jiǎn)，如取消成本較高和復(fù)雜的自動(dòng)取盤(pán)結(jié)構(gòu)和 PC 查詢功能，僅用單片機(jī)組成“實(shí)現(xiàn)隨意存、編碼查找和燈光位置指示”的 靈巧 系統(tǒng)等等。 3）用工業(yè)計(jì)算機(jī) PC104 作為控制核心， 組成基于網(wǎng)絡(luò)的光盤(pán)管理裝置， 提高產(chǎn)品品質(zhì) 。增長(zhǎng)了我關(guān)于機(jī)械設(shè)計(jì)和加工方面的諸多知識(shí)。 if(address=8)//分段計(jì)算 pluse1=2546*address。 else if(address=86) pluse1=(2849+(3*(address63)/10))*address。 pluse2=1000。//10hz 剛開(kāi)始時(shí)不進(jìn)電機(jī)的啟動(dòng)速度要比較慢 ///////////////////////////// // j=address/8。 else{ k。//400hz 這兩種狀態(tài)不用變 PWM 的頻率 else if(pluse1_count800)//針對(duì)走過(guò)不同的脈沖數(shù)目來(lái)調(diào)整 PWM 輸出頻率 ICR1=0x047f。//1000 else if(pluse1_count1600) ICR1=0x00A6。//3000 else if(pluse1_count3000) ICR1=0x0083。 Step=2。 //PORTCamp。=0xfe。=~0x02。 } else{ Step=4。// pluse2_count++。// } }//end else if(step_flag==2) else if(Step==6){ if(pluse1_countpluse1){ //PORTC|=0x01。 OCR1B=0。// PORTC|=0x01。 Get_flag=0。//10hz //test_flag=0。39。39。39。39。39。HFF 48 = StrSen //在用戶每次選中一個(gè)或者取消選擇光盤(pán)時(shí)進(jìn)行的處理 If (0).value 0 Then Sent_Com = Sent_Com + 1 ReDim Preserve StrSen(Sent_Com) StrSen(Sent_Com) = (4).value Else Dim i As Integer For i = 1 To Sent_Com If StrSen(i) = (4).value Then Dim j As Integer If i Sent_Com Then For j = i To Sent_Com StrSen(j) = StrSen(j + 1) Next End If Sent_Com = Sent_Com 1 End If Next End If 光盤(pán)掃描功能實(shí)現(xiàn)的關(guān)鍵程序 Public Function TreeSearch(ByVal sPath As String, ByVal sFileSpec As String, sFiles() As String) As Long Static FileS As Long 39。 sFileSpec) 39。 Str(Int(FileLen(sPath amp。 sDir Print 1, sDir amp。存放子目錄名稱 Dim Index As Long Dim num1 As Integer Dim num2 As Integer If Right(sPath, 1) \ Then sPath = sPath amp。 StrSen(0) = amp。39。39。39。39。39。 // Step=0。 pluse1_count=0。 } else{ //PORTCamp。=~0x01。 pluse2_count=0。 } }// end else if(step_flag==1) else if (Step==4){ //wait Step=5。 OCR1A=0。 pluse1_count=0。// PORTC|=0x01。 46 OCR1B=0。//4000 } ///////////////////////////////////// //把整個(gè)取盤(pán)過(guò)程分解為 7 中狀態(tài)，在不同狀態(tài)中進(jìn)行不同處理 void timer1_ovf_isr(void) { //TIMER1 has overflowed if (Step==1){ pluse1_count=0。//20xx else if(pluse1_count2200) ICR1=0x00B8。//600 else if(pluse1_count1000) ICR1=0x023f。 } } //////////////////////////// TCCR1B = 0x12。 if (k==0)// LEDOUT(j,0x80)。//初始化脈沖計(jì)數(shù)為 0 Step=1。 else if(address=140) pluse1=(2862+64*(address122)/100)*address。 else if(address=51) pluse1=(2820+18*(address25)/10)*address。 七 、 附件 主要 程序清單 44 程序附件 精度問(wèn)題關(guān)鍵程序 ： //////計(jì)算對(duì)應(yīng)位置上需要的脈沖數(shù)目 void Get_Deal(unsigned long address){ unsigned char i,j,k。 43 其次，感謝華南理工大學(xué)的陳欽昌老師，田聯(lián)房老師，王孝洪老師，何建雄學(xué)長(zhǎng)，楊躍學(xué)長(zhǎng)，鐘春波學(xué)長(zhǎng)、王磊學(xué)長(zhǎng)，陳派林學(xué)長(zhǎng)，他們都給予了我無(wú)私的幫助和指導(dǎo)，使我增長(zhǎng)了許多工程專業(yè)技術(shù)知識(shí)。以后會(huì)對(duì)結(jié)構(gòu)進(jìn)行改進(jìn)，既保證速度，也保證精度，縮小用戶等待時(shí)間。裝置經(jīng)進(jìn)一步改進(jìn)后，將申報(bào)相關(guān)的專利。 2）該裝置的操作界面友好，操作流程簡(jiǎn)便易懂，對(duì)使用者無(wú)任何基礎(chǔ)知識(shí)要求。該設(shè)計(jì)思路的提出是為了幫助人們對(duì)光碟進(jìn)行隨意存放和自動(dòng)查找，減輕人們管理光碟的負(fù)擔(dān)，本項(xiàng)目目前雖然提交的 僅是單元柜系統(tǒng) ,但 完善 后，可以應(yīng)用于圖書(shū)館、檔案館、電視臺(tái)、廣播電臺(tái)、博物館、資料室等需要管理大宗信 息和資料的單位 。使用這些信息，我在 VB中利用 TreeView 和 ListView 控件把文件夾和文件名字分別再次生成樹(shù)。 圖 在實(shí)現(xiàn)了光盤(pán)信息的保存后，另外一個(gè)難題就是如何利用所保存的信息復(fù)現(xiàn)光盤(pán)的目錄結(jié)構(gòu)。ＶＢ中有相應(yīng)的函數(shù)可以把這些信息提取出來(lái)。這樣可以防止用戶使用沒(méi)經(jīng)過(guò)批準(zhǔn)的光盤(pán)。雖然每個(gè)光碟的信息只需要一次輸入，但這樣當(dāng)需要輸入的光碟數(shù)量比較多的時(shí)候，就會(huì)大大增加工作人員的工作量，而且效率很低。 2） 電路設(shè)計(jì) 方面 的改進(jìn) 在單層樣機(jī)中，光電檢測(cè)電路和指示燈是做在同一個(gè)電路板上的，加 上必要的芯片，這個(gè)電路板占的面積比較大，降低了空間使用效率。 （ a） 結(jié)構(gòu) 示意 圖 （ b） 實(shí)物照片 圖 第二代光碟機(jī) 39 為了更加貼近實(shí)際使用的需要，每層光碟存放槽帶有自動(dòng)打開(kāi)的門(mén)。 1） 機(jī)械結(jié)構(gòu) 方面 的改進(jìn) 在單層光碟存取裝置成功設(shè)計(jì)出來(lái)的基礎(chǔ)上，我設(shè)計(jì)出了 兩 層的光碟存取裝置。平常將使用完的光碟存放在光碟槽中時(shí)，首先通過(guò)光碟掃描裝置，對(duì)光碟上的標(biāo)識(shí)碼進(jìn)行掃描，此時(shí)計(jì)算機(jī)將自動(dòng)識(shí)別光碟的名 稱等相關(guān)信息；在光碟槽中任意選取一個(gè)空閑位置，將光碟放入，放置在光碟槽前面的一對(duì)光電檢測(cè)管，自動(dòng)讀取光碟所處的位置，并將這個(gè)位置信號(hào)送入計(jì)算機(jī)系統(tǒng)。 實(shí)驗(yàn)證明，通過(guò)以上算法優(yōu)化，可以準(zhǔn)確尋找最短路徑，并顯著提高路徑的搜索效率。回溯到 K，到達(dá) K 結(jié)點(diǎn)時(shí)，當(dāng)前路徑長(zhǎng)度為 12，大于等于 * min_best l l? =12。得到路徑為（ A,B,C,F,L）其路徑總長(zhǎng)度為 15，比當(dāng)前 *_best l 要少，于是令 *_best l =15，當(dāng)前的比較值 * min_best l l? 變?yōu)?12。 利用這個(gè)標(biāo)準(zhǔn)再來(lái)看看 圖 所示的問(wèn)題。1 ()ji li??為當(dāng)前正在搜索的路徑總長(zhǎng)度。例如，當(dāng)確定了路線為（ 1， 2， 3）后，接著最后一個(gè)結(jié)點(diǎn)肯定就是 4。把它作為目前的剪枝標(biāo)準(zhǔn)值，在接下來(lái)的回溯搜索過(guò)程中，只要發(fā)現(xiàn)當(dāng)前分支的總路程大于 18，就可以停止對(duì)其子結(jié)點(diǎn)的搜索了。 以上所述的回溯法在搜索過(guò)程中，其下層結(jié)點(diǎn)的選取是隨意的，而利用局部最優(yōu)思想，在搜索過(guò)程中，對(duì)于每一個(gè)活動(dòng)結(jié)點(diǎn)，先從其代價(jià)最小的一個(gè)分支開(kāi)始。 5） 算法的改進(jìn) 從以上可以看到，回溯法搜索過(guò)程中，需要對(duì)整個(gè)解空間進(jìn)行搜索，而在實(shí)際中，往往有些結(jié)點(diǎn)顯然不能生成最優(yōu)解，所以可以采用有效的策略避免無(wú)效搜索，提高回溯法的搜索效率。從結(jié)點(diǎn) B，算法 繼續(xù)搜索至結(jié)點(diǎn) D， H， N。從葉結(jié)點(diǎn) L 返回至最近活動(dòng)結(jié)點(diǎn) F 處。此時(shí)，應(yīng)該往回移動(dòng)（回溯）至最近的活結(jié)點(diǎn)處， 30 并使這個(gè)活結(jié)點(diǎn)成為當(dāng)前擴(kuò)展結(jié)點(diǎn)。這個(gè)開(kāi)始結(jié)點(diǎn)成為活結(jié)點(diǎn)，同時(shí)成為當(dāng)前的擴(kuò)展結(jié)點(diǎn)。通常將解空間組織成樹(shù)的形式。 29 3） 問(wèn)題的解空間 用回溯法解問(wèn)題時(shí)，應(yīng)該明確定義問(wèn)題的解空間。 它 在問(wèn)題的解空間樹(shù)中，按深度優(yōu)先策略，從根結(jié)點(diǎn)出發(fā)搜索解空間樹(shù)。這里 采用回溯法來(lái)實(shí)現(xiàn)。利用上圖雖然可以表示各個(gè)光盤(pán)的位置信息，但還不夠直觀，利用圖的概念 和 以上定義的距離信息，可以得到以上坐標(biāo)圖的等效加權(quán)圖如下： 圖 加權(quán)圖表示光盤(pán)位置 其中線條之間數(shù)據(jù)表示兩個(gè)點(diǎn)之間的距離 。在本 算法中， 定義光盤(pán)之間的距離為 28 1 2 1 2L | | | |x x y y? ? ? ?,其中 ( , )iixy 是以裝置一個(gè)端點(diǎn)為原點(diǎn)時(shí)，第 i個(gè)光盤(pán)的坐標(biāo)，由于實(shí)際中不可能測(cè)量每 個(gè)光盤(pán)到原點(diǎn)的位置，我們利用光盤(pán)存放的位置信息作為坐標(biāo)。就像下面的示意圖 (圖 )： 圖 圓圈表示需要取的光盤(pán)，三角形代表當(dāng)前取盤(pán)機(jī)構(gòu)的位置 上圖表示一個(gè) 3 層的光盤(pán)存放機(jī)構(gòu)，每層可以存放 10 張光盤(pán)。書(shū)本讓我理解了什么叫做樹(shù)，什么是圖，如何對(duì)樹(shù)進(jìn)行遍歷，如何尋找最小生成樹(shù)等。我就想能不能設(shè)計(jì)出一種有效的方法，讓取盤(pán)機(jī)構(gòu)在最短的時(shí)間內(nèi)把光盤(pán)都取出來(lái)呢？順著這個(gè)思路，我在網(wǎng)上找了很多資料，包括動(dòng)態(tài)規(guī)劃，最優(yōu)設(shè)計(jì)，貪心算法等等，但是看到這些高深的東西，我真的不知道如何下手。若使用者 一次 要取的盤(pán)很多 時(shí) ，這樣的操作 就 很浪費(fèi)時(shí)間。 這 樣 ， 利 用 以 上 定 義 式*( ( ))iiP k k x x x? ? ? ?，就可以計(jì)算