基于計算機控制的光碟智能存取裝置研制_畢業(yè)論文.doc

基于計算機控制的光碟智能存取裝置研制 基于計算機控制的光碟智能存取裝置研制基于計算機控制的光碟智能存取裝置研制 目目 錄錄 一、項目簡介一、項目簡介1 二、主要創(chuàng)新點二、主要創(chuàng)新點.1 三、研究背景、目的和意義三、研究背景、目的和意義2 四、探究過程四、探究過程2 1.研究方案探究 .2 2.技術(shù)路線圖 .4 3.結(jié)構(gòu)設(shè)計 .5 4.計算機管理功能的實現(xiàn) .8 5.精確定位的實現(xiàn) .17 6.路徑算法的優(yōu)化與創(chuàng)新應(yīng)用 .25 7.設(shè)備連接與調(diào)試 .33 8.智能應(yīng)用 .37 9.改進 .37 五、展望和應(yīng)用五、展望和應(yīng)用.41 六、感謝六、感謝.43 七、附件七、附件.43 1 全國青少年科技創(chuàng)新大賽全國青少年科技創(chuàng)新大賽 基于計算機控制的光碟智能存取裝置基于計算機控制的光碟智能存取裝置 -隨機存儲、自動搜索與控制、路徑優(yōu)化算法的創(chuàng)新與應(yīng)用 一、項目簡介一、項目簡介 本項目的最終目標最終目標是實現(xiàn)一種基于計算機控制的光碟智能存取裝置，是一 個集計算機管理及軟件開發(fā)、算法設(shè)計與控制為一體的計算機應(yīng)用系統(tǒng)。完善 后可以廣泛應(yīng)用于圖書館、檔案館、電視臺、廣播電臺、博物館、資料室等需 要管理大宗信息和資料的單位。主要研究內(nèi)容包括主要研究內(nèi)容包括：取多盤執(zhí)行機構(gòu)路徑優(yōu)化 算法的研究與探討；執(zhí)行機構(gòu)精度控制算法的研究與軟件設(shè)計；光盤管理信息 系統(tǒng)設(shè)計與程序開發(fā)；單片機控制及驅(qū)動系統(tǒng)設(shè)計；光盤位置檢測的實現(xiàn)；存 儲機構(gòu)設(shè)計與加工；整機系統(tǒng)的試驗研究與改進等。系統(tǒng)裝置實現(xiàn)如下功能如下功能： 光碟隨機存儲功能光碟隨機存儲功能，光碟存放時不需要按分類和編號進行對號入座和固定存放， 即：哪里有空位就哪里存放；光碟自動搜索與控制功能光碟自動搜索與控制功能：按存放位置自動更新、 分層分類，并按照關(guān)鍵字進行自動搜索的數(shù)據(jù)庫設(shè)計，實現(xiàn)對光碟基本信息的 瀏覽、自動搜索和查找功能。同時，光碟取出執(zhí)行機構(gòu)會按照搜索到的光碟位 置信息，自動彈出要查找的光碟；取多盤路徑優(yōu)化功能取多盤路徑優(yōu)化功能，執(zhí)行取多盤功能時， 應(yīng)用與計算機進行通信的單片機控制電路、驅(qū)動電路和執(zhí)行結(jié)構(gòu)，以路徑最短 方式進行路徑優(yōu)化設(shè)計，實現(xiàn)多盤自動彈出功能。 稍做簡化可直接進入家庭。系統(tǒng)裝置具有廣泛的應(yīng)用前景和市場推廣價值。 二、主要創(chuàng)新點二、主要創(chuàng)新點 1) 取多盤路徑尋優(yōu)算法及創(chuàng)新應(yīng)用。本系統(tǒng)具有一次取多盤路徑優(yōu)化功能， 2 采用了改進的回溯尋優(yōu)法尋找最佳路徑，利用截枝分界法來提高搜索效率，并 對分界比較值進一步優(yōu)化，使系統(tǒng)的取盤效率大大提高。 2) 在取盤機構(gòu)位置控制精度方面，本系統(tǒng)在普通分段線性化的基礎(chǔ)上進行 了改進，對取盤機構(gòu)上的控制上采用了斜率分段線性化優(yōu)化算法，使取盤的位 置精度得到保證。 3）本系統(tǒng)裝置功能人性化，充分考慮實用性與應(yīng)用型，是集光、機、電、 控制與信息為一體的綜合智能化計算機實際應(yīng)用系統(tǒng)。 三、研究背景、目的和意義三、研究背景、目的和意義 隨著科學(xué)技術(shù)和文化事業(yè)的發(fā)展，光碟的數(shù)量是越來越多，而從林林總總 的光碟中找到自己需要的光盤是一件費時費力的事情。有一天，我為了找老鷹 樂隊的珍藏碟，我花了一個上午的時間，將所有的碟翻了出來才找到。這不僅 浪費了我的時間，也破壞了我那天的好心情。當時我就在想，是否可以有那么 一個裝置，存儲物品的時候可以隨意放置，取出的時候裝置可以自動找到物品 并把物品自動取出來。這樣一個想法激發(fā)了我對這方面的探究興趣。這樣的裝 置研究出來，將對許多需要物品存儲管理的場合和單位非常有用。 光碟是目前用途最廣、也是最可靠的信息載體，經(jīng)過調(diào)研，我發(fā)現(xiàn)圖書館， 檔案館，電視臺，廣播電臺，博物館，資料室等這樣的一些單位，保存、管理 和使用數(shù)量巨大的光碟，以此作為切入口，我選擇了以光碟自動存取作為研究 對象開始我的探究之路。 四、探究過程四、探究過程 1.1.研究方案探究研究方案探究 首先，這是一個自動裝置，結(jié)構(gòu)方面應(yīng)該緊湊，要爭取在有限的空間內(nèi)存 放盡可能多的光盤。根據(jù)觀察，發(fā)現(xiàn)檔案館里存放檔案的檔案柜的設(shè)計和放置 3 十分合理，一排排緊湊放置，每排僅留一個機動的操作位，由于每個柜底下有 導(dǎo)軌和滑輪，柜子可以依次移動，當取檔案時，把操作位調(diào)整到合適位置就可 以進行操作。同時，市面上有一種柵格一樣的結(jié)構(gòu)，可以裝幾十張去掉封套、 僅保存光碟本身的光碟盒也是一種好的結(jié)構(gòu)。將這兩種結(jié)構(gòu)結(jié)合在一起，就是 我設(shè)想中的智能光碟存取裝置結(jié)構(gòu)（如圖 1.1） 。其中，柵格為多層層疊式，每 層兩組，自動取盤機構(gòu)設(shè)在中間，可以把選擇的光碟從兩邊彈出。 圖 1.1 初步設(shè)想中的智能光碟存取裝置結(jié)構(gòu) 其次，既然要實現(xiàn)智能功能，每個柜子應(yīng)設(shè)計計算機控制系統(tǒng)，本系統(tǒng)考 慮用設(shè)有觸摸屏的計算機控制系統(tǒng)實現(xiàn)其智能功能。光碟隨機存儲功能光碟隨機存儲功能-光碟 存放時不需按分類和編號進行對號入座和固定存放，哪里有空位就哪里存放。 光碟自動搜索與控制功能光碟自動搜索與控制功能方便光碟基本信息方便的瀏覽、搜索和查找。光碟光碟 自動彈出功能自動彈出功能-應(yīng)用控制電路驅(qū)動執(zhí)行結(jié)構(gòu)，將選擇的光碟自動彈出。 考慮到每個柜中可以儲存的光碟容量很大（估計 5000-8000 個） ，單個光碟 設(shè)計一個彈出機構(gòu)是不現(xiàn)實的，可以考慮用計算機控制的 x-y 滑塊方式來實現(xiàn)， 我想這種方式用計算機來控制是應(yīng)該可以做到的。 目前市面上那些光碟管理柜（裝置）多半是先人工分類編號，存放的時候 一一對號入座，而且也少有自動彈出機構(gòu)。我設(shè)計的這個智能光碟存取裝置不 僅設(shè)有自動彈出機構(gòu)，而且光碟實現(xiàn)可以隨意存放在任意的空閑位置上，裝置 自動識別出位置，并記錄起來以便以后自動尋找，這一點，對圖書館，檔案館， 電視臺，廣播電臺，博物館，資料室等這樣需要保存、管理和使用數(shù)量巨大的 4 光碟的一些單位相當有用。圖書館一天從借閱者還書時回收上百張書帶光碟 （現(xiàn)在好多書都配光碟，它們與書分開存放） ，管理員每天要將它們一一對號入 座，將是多大的工作量啊！ 2.2.技術(shù)路線圖技術(shù)路線圖 帶著這個問題，我征詢了老師和爸爸的意見，他們?nèi)χС趾凸膭钗覍@ 個問題進行探討，并聯(lián)系了華南理工大學(xué)自動化學(xué)院老師對我進一步的指導(dǎo)。 經(jīng)過溝通，老師對我的研究方案提出了兩點意見和建議： 一是方案提出“不需按分類和固定位置存放”解決光碟存放問題符合當前 倉庫管理理念，是一種新趨勢，方案可行，具有廣闊的應(yīng)用前景。支持我以此 為目標，為最后形成實際應(yīng)用產(chǎn)品而努力。但就目前而言，建議分段實施。 二是項目涉及計算機、單片機、自動化、機械設(shè)計與加工，電路設(shè)計、數(shù) 學(xué)、物理等多個學(xué)科門類的知識，有些已經(jīng)大大超出高中學(xué)生的要求，提出只 要有興趣和毅力，邊學(xué)邊實現(xiàn)，可以完成預(yù)定的目標。 老師的意見給予我信心。在老師們的幫助下，我重新調(diào)整了方案。簡要講 就是設(shè)計用一組柵格，先做一個可以存放 200 個左右光碟的單元柜，實現(xiàn)主要 功能進行可行性試驗和測試，發(fā)現(xiàn)問題，彌補不足并積累經(jīng)驗，待成功后才向 前推進。控制系統(tǒng)和計算機數(shù)據(jù)庫系統(tǒng)先采用單片機+普通計算機來實現(xiàn)，待成 功后用一體機（老師說是工業(yè)計算機，可配觸摸屏）轉(zhuǎn)變（圖 2.1） 。 圖 2.1 經(jīng)咨詢討論后確定的試驗樣機裝置圖 5 所擬的技術(shù)路線圖如下： 3.3.結(jié)構(gòu)設(shè)計結(jié)構(gòu)設(shè)計 光電管位置檢測方案的選定光電管位置檢測方案的選定 在整個設(shè)計過程中，首先應(yīng)解決的問題是如何實現(xiàn)隨意存儲功能。整個方 案反反復(fù)復(fù)修改了幾次，是本探究學(xué)習(xí)的主要難點和重點之一。探究過程如下： 首先，我想到了普通的滑動變阻器。根據(jù)電阻長度位置的不同而阻值不同 的特性，可以通過測量電路中電阻的阻值，就可以將阻值與光碟位置一一對應(yīng) 起來。但是，經(jīng)過我的實驗，我發(fā)現(xiàn)每次測量同一位置的電阻值并不是一個定 值，而且不同位置的電阻值相差的又不是很大，很難與光碟位置一一對應(yīng)，數(shù) 據(jù)處理起來非常的困難，所以我選擇放棄。 6 圖 3.1 滑動變阻器的原理圖 接著，我又想到了觸動開關(guān)，就是在每個光碟的存放位置安放一個觸動彈 片來感知光碟的位置。對此，我還去專門的電子市場去尋找相應(yīng)的材料?；氐?家中后，我將它們焊接到一塊電路板上做可行性實驗。雖然電路很簡單，元器 件比較少，但是線路卻非常繁雜，檢查電路也成為了一件異常費力的事情。所 以為了接通這十六個觸動開關(guān)組成的電路，整整花了我一天的時間。正當我正 高興于實驗的成功時，我發(fā)現(xiàn)，僅僅十六個觸動開關(guān)就占用了很大的面積。因 為這是我在市面上找到的最小型號觸動開關(guān),而將來要設(shè)計出可以存儲 1000 張 光碟的裝置時，裝置的占地面積將會異常巨大，這違背了我結(jié)構(gòu)設(shè)計方面的宗 旨，況且觸動開關(guān)的反應(yīng)并不像想象中的靈敏，所以我決定找尋更佳的方案。 圖 3.2 觸動開關(guān)示意圖 再者，通過以前對數(shù)字電路學(xué)習(xí)的基礎(chǔ)，我想到了一種可以有效減少數(shù)據(jù) 線數(shù)量的方案薄膜開關(guān)。也就是說，連接八條數(shù)據(jù)線，那么就有 28256 種狀態(tài)。每個光碟槽放置一個薄膜開關(guān)，每個開關(guān)對應(yīng)一種狀態(tài)，這樣就可以 識別出光碟的位置，從而實現(xiàn)隨意存儲的功能。我的這個想法得到了指導(dǎo)老師 的高度贊揚，說這是一個很好的想法。但是由于電子市場根本沒有這樣的開關(guān) 賣，訂做會導(dǎo)致成本很高，而且可靠性不高。無奈之下，只能放棄了這個很好 的方案。 7 圖 3.3薄膜開關(guān)示意圖 最后，通過在網(wǎng)上論壇的討論，我終于發(fā)現(xiàn)了一個目前來說的最佳選擇- -光電檢測管。它有著體積小、反應(yīng)靈敏和可靠性高優(yōu)點。我的設(shè)想是在每個 光碟存放位置的前端安放一對光電檢測管，當有光碟存放時，它可以觸發(fā)信號， 送給上層管理系統(tǒng)，使其識別并記憶光碟所處的位置。通過實驗發(fā)現(xiàn)，開關(guān)反 應(yīng)靈敏，工作可靠，而且在市面上可以買到尺寸非常小的此類開關(guān)（大約 3 毫 米左右） 。因此，最后確定選用光電檢測管來實現(xiàn)自動檢測光碟位置的功能。 光電檢測管的排布設(shè)計光電檢測管的排布設(shè)計 我對于結(jié)構(gòu)方面設(shè)計的初衷是：在有限的空間里可以存放盡可能多的光盤。 所以，我決定采用柵格結(jié)構(gòu)，因為它的空間利用率是最高的。依照原來的設(shè)想， 光電檢測管是按“一”字型排列的。但是通過觀察發(fā)現(xiàn)，以這種排列方式的話， 光電檢測管的兩壁會占用較多的空間，我當時就在想能不能把這部分的空間也 充分利用起來。通過多種擺放方案的嘗試，終于發(fā)現(xiàn)通過“品”字型的排布是 空間利用率最好的排布。 圖 3.4a “一“字型排布示意圖 圖 3.4b “品”字型排布示意圖 8 取盤機構(gòu)的設(shè)計取盤機構(gòu)的設(shè)計 根據(jù)測量，光碟的厚度是大約是 1.25mm，設(shè)想中光碟之間的距離是盡可能 窄的。要在這么小的距離內(nèi)自動取出光碟是比較麻煩的事情。開始我想到的是 利用機械手臂，但是機械手臂體積太大結(jié)構(gòu)太復(fù)雜，同時也涉及到了太復(fù)雜的 技術(shù)，考慮用機械手臂這個方案不現(xiàn)實，放棄。方案的選擇陷入了僵局，通過 電視我發(fā)現(xiàn)實際工程應(yīng)用中有很多精密控制的例子，我決定去工廠參觀來尋找 解決方案。通過與那里師傅的交流，我獲益匪淺，最終采用了絲桿+螺母結(jié)構(gòu)的 雙步進電機作為執(zhí)行機構(gòu)。雙步進電機的一個負責(zé)軸向運動，另一個負責(zé)推出 光碟。 4.4.計算機管理功能的實現(xiàn)計算機管理功能的實現(xiàn) 我的光盤管理軟件設(shè)計主要可以分為兩個階段，分別是前期探索，實際設(shè) 計。 前期探索前期探索 所謂萬事起頭難，現(xiàn)在想起我剛開始的時候，還真有點苦盡甘來的感覺。 當決定要設(shè)計一個光盤管理系統(tǒng)后，通過與指導(dǎo)老師商討和在網(wǎng)上搜索，我決 定利用 vb 和數(shù)據(jù)庫進行開發(fā)，選擇 vb 是因為之前我對它曾經(jīng)有所接觸，有一 定的基礎(chǔ)，而且老師說 vb 語言入門比較容易，對專業(yè)知識要求不高，而且控件 資源比較豐富。但對于數(shù)據(jù)庫我的概念就比較模糊，只感覺是一門高深的學(xué)問 與內(nèi)容。 雖說我有一點 vb 的基礎(chǔ)，可是要開發(fā)一個軟件還是有所欠缺。老師說我應(yīng) 該循序漸進，所以我第一步是以設(shè)計一個簡易計算器為目標的，作為一個前期 的學(xué)習(xí)階段。 9 圖 4.1 我設(shè)計的簡易計算器 不要以為設(shè)計計算器很簡單，記得那時候我花了整整大半個月的時間，特 別是某些細節(jié)的地方，例如在 vb 中的 text 控件，顯示的是從左到右的，但 計算器是從右到左的，開始時我也沒有注意，但和 windows 上附件中自帶的做 比較后，發(fā)現(xiàn)這個問題，通過在網(wǎng)上搜索，知道是需要修改控件的屬性。還有 就是數(shù)據(jù)的類型也要特別注意，因為利用 text 控件來顯示數(shù)據(jù)和結(jié)果，他需 要的是字符型的數(shù)據(jù)，而在運算過程中，利用的是數(shù)字型的數(shù)據(jù)，這樣在不同 的地方就要對數(shù)據(jù)進行恰當?shù)霓D(zhuǎn)換。還有的是中間變量的設(shè)置也需要注意它的 類型匹配，總之，雖然這個例子對其他人可能比較簡單，但通過它我掌握了 vb 程序開發(fā)的過程，基本控件的使用方法還有數(shù)據(jù)利用的原則。 學(xué)會使用 vb 僅僅是個開始，因為我設(shè)計的系統(tǒng)中需要用到數(shù)據(jù)庫，而這 方面我完全沒有學(xué)習(xí)過的。開始時在網(wǎng)上找了些資料看，但看了很久還是沒有 頭緒。指導(dǎo)老師針對我系統(tǒng)的設(shè)計需求，給我有針對性地進行輔導(dǎo)。經(jīng)過他的 講解，我終于對數(shù)據(jù)庫中，例如關(guān)系數(shù)據(jù)庫，表，視圖，關(guān)鍵字，搜索等一些 概念有了基本了解。老師還為我講解了數(shù)據(jù)庫中常用的 sql 語言，通過學(xué)習(xí)， 我知道了基本的數(shù)據(jù)庫操作語言，例如 insert、delete、update、select 等 命令的使用格式。根據(jù)老師給的資料，我開始按著提示，利用 office 中自帶的 access 數(shù)據(jù)庫軟件，建立自己的數(shù)據(jù)庫。 10 圖 4.2練習(xí)建立的圖書信息表 由于系統(tǒng)中需要利用 vb 對數(shù)據(jù)庫進行操作，從資料上我知道，vb 通過 ado 可以方便對數(shù)據(jù)庫進行操作的。其實從現(xiàn)在我的理解來說，ado 應(yīng)該相 當于一個橋梁，利用它可以使 vb 和數(shù)據(jù)庫進行連接，而 vb 送到數(shù)據(jù)庫的是 sql 數(shù)據(jù)庫操作語言，而從數(shù)據(jù)庫回來的是查詢的數(shù)據(jù)。為了練習(xí)如何利用 ado 對數(shù)據(jù)庫進行操作，對著書本上的例子，我做了一個數(shù)據(jù)庫數(shù)據(jù)查詢器， 利用它可以對數(shù)據(jù)庫所建立的表中數(shù)據(jù)進行查詢，并把結(jié)果顯示出來。 圖 4.3 我設(shè)計的數(shù)據(jù)查詢器 這個例子對與我后面的設(shè)計起到了很大的幫助，通過它不但知道了如何在 vb 中利用 ado 控件對數(shù)據(jù)庫中表的數(shù)據(jù)進行查詢，還知道了可以利用 11 datagrid 控件對數(shù)據(jù)進行顯示。 之前的學(xué)習(xí)主要是了解和熟悉各個控件的使用，對數(shù)據(jù)庫和 vb 中的一些 基本原理更加了解。在正式開始系統(tǒng)設(shè)計前，我通過書上例子，設(shè)計出了一個 簡易的圖書管理軟件。這個軟件從包括從數(shù)據(jù)庫的建立，數(shù)據(jù)表的設(shè)計，到 vb 中界面的設(shè)計，各個控件的使用和協(xié)調(diào)，數(shù)據(jù)的查詢搜索，更新，刪除等 都用上了，是我之前所學(xué)知識的一個綜合使用。我對著參考書一個一個語句看， 一個部分一個部分地嘗試，用了整整一個多月的時間，把書上例子中的主要功 能都實現(xiàn)了。通過這個練習(xí)，我對自己需要設(shè)計的系統(tǒng)有了更多的了解，我知 道該如何下手了。我的系統(tǒng)也是在這個例子的基礎(chǔ)上建立起來的。 圖 4.4 我做的圖書管理軟件界面 實際設(shè)計實際設(shè)計 通過前期的準備，我對 vb 程序設(shè)計，數(shù)據(jù)庫使用以及其的二次開發(fā)有了 更深的了解。在前期的基礎(chǔ)上，我開始一部分一部分地設(shè)計自己的光盤管理軟 件。對于整個系統(tǒng)來說，其核心部分應(yīng)該是數(shù)據(jù)庫，而其中表的建立是基礎(chǔ)。 表中的數(shù)據(jù)要設(shè)置得合適，數(shù)據(jù)之間的相互關(guān)聯(lián)性要好，而且要避免冗余。我 開始時先把想到的需要保存的信息制作出幾個表來，其中包括光盤信息表，用 戶信息表，針對著這兩個表在 vb 中分別建立連接?？墒请S著編程中發(fā)現(xiàn)，這 樣的表設(shè)置不是很合理，例如光盤信息表中光盤存放位置等信息，這些信息是 可以隨時更改的，而例如光盤名字，光盤備注等信息不是經(jīng)常要更新，這樣的 信息應(yīng)該有所區(qū)別，還有，就是光盤的分類，應(yīng)該獨立來處理比較合理。這樣 12 一步一步地嘗試，我現(xiàn)在是在整個數(shù)據(jù)庫中建立了幾張數(shù)據(jù)表，分別是光盤基 本信息表，光盤分類表，用戶資料表，光盤動態(tài)信息表等。 我設(shè)想中的管理系統(tǒng)，它應(yīng)該具有信息查詢、信息瀏覽、添加、編輯、刪 除、取盤等功能，并且能夠和單片機進行通信，實現(xiàn)對取盤執(zhí)行機構(gòu)的控制。 根據(jù)以上需求，設(shè)計 vb 框架如下： 圖 4.5 vb 框架圖 主窗體設(shè)計主窗體設(shè)計 主窗體是打開軟件時的第一個窗體，對于數(shù)據(jù)庫的一切操作都是在它上面 完成。利用 vb 工具中的“菜單欄設(shè)計”命令，可以很簡單地設(shè)計出想要的窗體 結(jié)構(gòu)。具體設(shè)計見下圖： 圖 4.6 主窗體結(jié)構(gòu) 效果如下： 13 圖 4.7 效果 在主窗體中插入兩個菜單欄，分別為“基本信息管理”和“系統(tǒng)用戶管理” 。 在“基本信息管理”中各子菜單實現(xiàn)功能如下： cd 分類管理：實現(xiàn)光碟類別的添加、修改、刪除 cd 信息管理：實現(xiàn)光碟信息的添加、修改、刪除、取盤、瀏覽、查詢 “系統(tǒng)用戶管理”中各子菜單實現(xiàn)功能如下： 用戶管理：當用戶是管理者時可以對其他用戶進行刪除 修改密碼：當前登錄用戶可以修改自己的登陸密碼 cdcd 分類管理子窗體設(shè)計分類管理子窗體設(shè)計 當存放的光碟數(shù)目比較多的時候，對于光碟的快速查找和瀏覽就有比較高 的要求，為了提高管理效率，應(yīng)該對光碟分類進行管理，而不同用戶對于光碟 類別的區(qū)分不大一樣，所以本設(shè)計對光碟類別進行動態(tài)管理。對于光碟分類設(shè) 立一個專門的表來儲存信息，用戶可以根據(jù)設(shè)計的需求對光碟類別進行添加、 修改、刪除，這樣就能夠把各種光碟分門別類地保存起來。 為了更好地顯示分類效果，利用 vb 中的 treview 控件，形成樹狀顯示結(jié)構(gòu)， 這樣就能夠清楚地察看分類情況。 具體實現(xiàn)效果如下： 14 圖 4.8 分類 對于選定的分類，可以按需要隨時添加、修改、刪除下一層節(jié)點。分類編 輯子窗體如下： 圖 4.9 分類編輯子窗體 cdcd 信息管理子窗體設(shè)計信息管理子窗體設(shè)計 這是本管理軟件的核心窗口，要完成對于光碟的主要操作。它能夠?qū)崿F(xiàn)光 碟信息的添加、修改、刪除、快速查找、取盤等功能。具體設(shè)計窗體如下： 15 圖 4.10 信息管理子窗體 對于查找功能，用戶可以從兩種方法實現(xiàn)。第一是利用光碟分類管理形成 的結(jié)構(gòu)，把不同的光碟分門別類地顯示出來，用戶只需要打開對應(yīng)的樹狀分類 表就可以瀏覽對應(yīng)光碟的信息。第二種方法是快速查找，用戶利用紅外掃描儀 把貼在光碟上的標簽號輸入到快速查找框，察看對應(yīng)光碟的信息，可用戶還可 以選擇關(guān)鍵字查找方式，在快速查找框中輸入光碟名稱的關(guān)鍵字來實現(xiàn)模糊查 找。 圖 4.11 模糊查找 管理軟件中新光碟信息的輸入只需輸入一次。有兩種途徑，第一是用戶直 接在快速查找框中掃描輸入新的條形碼編號，軟件會自動查詢數(shù)據(jù)庫中的信息， 當發(fā)現(xiàn)為新的信息時會自動調(diào)用添加信息窗體。 16 圖 4.12 新光碟信息輸入窗口 第二種途徑是用戶自己在對應(yīng)分類的圖書列表中直接按添加按鈕添加新的 信息。軟件會自動調(diào)用新光碟信息輸入窗口。用戶按要求填寫好信息，按保存 按鈕就可以把新的光碟信息保存下來。當填入的信息不對或者忘記填寫時，軟 件會彈出提示窗口。 圖 4.13 提示窗口 用戶管理子窗體設(shè)計用戶管理子窗體設(shè)計 本軟件有用戶使用限制，用戶可以根據(jù)需要設(shè)計用戶密碼來防止別人修改 數(shù)據(jù)庫中的內(nèi)容。當?shù)卿涇浖r候，軟件會自動彈出登錄信息窗體： 17 圖 4.14 身份驗證 只有輸入正確的用戶名和對應(yīng)密碼才能進入軟件。而在軟件中用戶可以根 據(jù)實際需要設(shè)立和修改用戶名和對應(yīng)密碼，編輯子窗口如下： 圖 4.15 用戶信息 按確認后軟件會把數(shù)據(jù)儲存到對應(yīng)的用戶管理表中。 所設(shè)計的數(shù)據(jù)庫界面如下圖所示： (a) 18 (b) 圖 4.16 數(shù)據(jù)庫設(shè)計界面 5.5.精確定位的實現(xiàn)精確定位的實現(xiàn) 單片機的學(xué)習(xí)單片機的學(xué)習(xí) 通過前一段時間的軟件設(shè)計，我電腦上的管理軟件已經(jīng)有了個基本框架了， 而光碟存放的機械結(jié)構(gòu)已經(jīng)委托機械廠師傅幫我加工，現(xiàn)在的問題是怎么用我 電腦上的管理軟件來控制光碟存放裝置，讓它完成我設(shè)想中的隨意存放光碟和 自動取光碟的功能。我設(shè)想中是利用電腦直接控制電機和接受信號就可以了。 但事實上并不是這樣的。那次去工廠參觀時，我特意去問了這個問題，工作的 師傅說他們設(shè)計的那些裝置都有自己的控制單元。例如 plc，dsp，單片機等等， 這些東西我都沒有接觸過，我把我的想法同他們交流，他們建議我可以利用單 片機作為裝置的控制單元。利用它與電腦進行通信，并且控制裝置上的其他東 西。因為高中課程中沒有接觸過單片機，所以為了方案的實施，我開始了單片 機的學(xué)習(xí)歷程。我因為打算用 c 語言編寫單片機程序，所以首先我先去購書中 心買了一本有關(guān) c 語言入門和單片機教程的書籍來看。我的鄰居是一個在校研 究生，名叫小何，是自動化控制專業(yè)的，我打算向他請教有關(guān)方面的知識。他 建議我用 avr 的單片機來做，因為這款單片機入門資料比較多，而且價格便宜， 使用方便，而且他對 avr 比較了解。他還說，學(xué)習(xí)單片機最好的方法是自己動 手實踐。他先是很系統(tǒng)地教了我一些 c 語言在單片機開發(fā)中的應(yīng)用，然后他還 19 教我如何利用一個專門的模擬軟件來模擬實驗效果。在他的幫助下，我可以運 用模擬軟件中的 avrmega16 單片機來實現(xiàn)一些比如說走馬燈之類的簡單的控制 功能。 經(jīng)過模擬的訓(xùn)練后，我在小何哥哥的指導(dǎo)下做自己的單片機最小系統(tǒng)板。 開始時總覺得最小系統(tǒng)板是一個很深奧的東西，但實際上它所需要的器件不是 很多。我做的最小系統(tǒng)板包括幾個部分，第一是供電電路，是利用 7805 芯片實 現(xiàn)的；第二是串口通信電路，小何哥哥說我的設(shè)計需要用到單片機跟 pc 機的通 信，比較簡單而且可行的方法是利用串口，只需要一條串口線和 max232 芯片就 可以了；第三部分是單片機的復(fù)位電路；第四部分是調(diào)試口，因為小何哥哥那 里有 jtagice 調(diào)試工具，只需要把單片機對應(yīng)端口按順序引出就可以了。我按 照小何哥哥給我提供的原理圖，在萬用板上一部分一部分地把芯片連接起來。 焊接電路真是一個細致活，小何哥哥說假如某個地方短路就很容易把芯片給燒 了。雖然需要連接的線不是很多，但我還用了整整一天的時間，而且用萬用表 反復(fù)檢查，生怕哪里出了問題。到了最后，小何哥哥給我檢查了一遍，確定沒 有問題后，就開始最重要的時刻，上電。當時我的心真懸著啊，上電的一刻還 在默默祈禱著。幸虧一切正常，小何哥哥說利用仿真器能夠正常連接到芯片， 這表明芯片已經(jīng)能正常工作了。第二天，我繼續(xù)完成我的最小系統(tǒng)板。我很快 就把電路焊接好了，可是上電后，我把小何哥哥給我的串口調(diào)試程序下載到芯 片后芯片不能正常和 pc 機通信，我一下子懵了。小何哥哥讓我再仔細檢查電路 是否連接正確，串口的參數(shù)設(shè)定是否符合要求等。最后發(fā)現(xiàn)原來是有一條線沒 有連接好。硬件調(diào)試遠比軟件困難，一個錯誤可能需要很長時間才能發(fā)現(xiàn)。最 后，小何哥哥讓我在板上焊接了 8 個調(diào)試燈，并給了我一些基礎(chǔ)的程序，讓我 參照著它們來控制這些燈。在這個最小系統(tǒng)板上，我完成了很多的實驗，比如 走馬燈、蜂鳴器等。通過這一系列的實驗，我對單片機的了解也越來越深，對 單片機中斷，io 口操作，定時器使用，pwm 發(fā)生器使用等也有形成了基本認識。 電路設(shè)計電路設(shè)計 在我學(xué)習(xí)單片機的時間里，我委托機械廠的陳師傅加工機械部分。因為這 裝置要求的精度非常高，且運用到了高級的工業(yè)加工技術(shù)，以我現(xiàn)在的知識面 20 和條件，顯然是無法單獨開展這樣的工作。我把我的思路與設(shè)計方案向機械廠 的師傅進行了描述，并在他們熱心的指導(dǎo)下進行了調(diào)整，算是最終定下來了， 最后在加工廠師傅的協(xié)助下，他們幫助我設(shè)計了加工的圖紙，并按照我們討論 的方案，幫助我進行了機械加工。按照設(shè)計和加工的樣式，模型由三部分組成， 第一部分是光盤存放架子，光盤可以豎著放到架子上；第二部分是絲桿和螺母 組成的運動部分，一個步進電機帶動著絲桿轉(zhuǎn)動而讓另外一個步進電機橫向移 動，當?shù)竭_設(shè)定位置時，另外一個步進電機運作，帶動一個撥盤把光盤從架子 上推出來。接著利用單片機按照預(yù)定程序控制這兩個步進電機就可以了。 為了簡化裝置，陳師傅向我推薦了幾款步進電機驅(qū)動器，單片機產(chǎn)生的 pwm 脈沖信號輸入到驅(qū)動器后就可以控制步進電機。將驅(qū)動器分別與單片機和步進 電機連起來后，驅(qū)動電路就這樣完成了。 接下來是光電管的檢測電路。據(jù)我所知，光電管的特性是當有遮擋物的時 候可等效為斷路，無遮擋物的時候等效為通路。在之前檢測方式選擇時，我在 網(wǎng)上找到，利用光電管的特性，很容易設(shè)計出一個檢測電路，當光電管間有遮 擋物時輸出 0v，沒有遮擋物時輸出 5v，電路圖如下圖所示： 圖 5.1 光電管的檢測電路 但問題是怎么樣令單片機檢測到這些信號呢？我向小何哥哥請教，他給我 說了幾個方案，一是可以利用并進串出芯片串聯(lián)起來，可是這樣檢測速度就有 所限制，二是利用模擬開關(guān)對信號一個一個檢測，但是這樣需要很多 io 口，而 單片機上只有 32 個 io 口，三是利用鎖存器加譯碼芯片。這樣既方便讀取信號， 而且用的 io 口也相對較小。所以我采用了第三種方案。 21 我首先在萬用板上焊接 16 個光電管作為測試，接著利用單片機控制譯碼器， 輪流地開關(guān)鎖存器的使能端口，八個一組地讀取光電管的信號。經(jīng)過測試和實 際調(diào)整，基本能夠?qū)崿F(xiàn)我的要求。 然后是指示燈的電路設(shè)計。在我的設(shè)想之中，裝置進行取盤操作的隨后對 應(yīng)光碟的位置的 led 指示燈會亮起來，因為裝置對 led 指示燈的即時性要求不 是很高，小何哥哥提議利用單片機的 spi 口串行移位芯片實現(xiàn)來實現(xiàn)指示燈 的功能。我上網(wǎng)查了一下，發(fā)現(xiàn)了有一個利用八位移位輸出芯片在 led 大屏幕 顯示中的應(yīng)用實例，于是，我就參照了一下他的電路樣式，在小何哥哥的指導(dǎo) 之下完成了指示燈的萬用板電路（如圖 5.2 所示） 。經(jīng)過測試，效果基本滿意。 圖 5.2 指示燈的萬用板電路 為了讓整個裝置運行更加穩(wěn)定，更加美觀，按照之前設(shè)計方案，我委托工 廠把光電檢測電路和指示燈電路制作成 pcb 板。 整個控制系統(tǒng)結(jié)構(gòu)圖如下： 圖 5.3 控制系統(tǒng)結(jié)構(gòu) 22 設(shè)置控制命令格式設(shè)置控制命令格式 pc 作為整個系統(tǒng)的控制中心，在設(shè)計中要解決的一個重點是如何利用軟件 控制整套系統(tǒng)。由于控制部分是以單片機為核心的，那么問題就轉(zhuǎn)變?yōu)槿绾问?管理軟件與單片機有效通信交流。這部分一開始時我還真沒有頭緒，因為單片 機主要是利用串口與電腦通信的，而該如何處理發(fā)送數(shù)據(jù)才能實現(xiàn)與單片機的 溝通呢？經(jīng)過在網(wǎng)上一些論壇發(fā)帖咨詢，還有與指導(dǎo)老師的討論，我才形成了 現(xiàn)在的那種以控制標識符，數(shù)據(jù)內(nèi)容，命令結(jié)束標志為組合的控制信息。例如 上文所述，當在軟件上按取盤按鈕，那么電腦會自動形成控制信息如下 “g+address+e”其中，g 表示 get，就是說要取盤，address 是需要取盤的位 置信息，e 是命令結(jié)束標志符。 控制命令地址結(jié)束標志 設(shè)計命令格式 開始的時候，我設(shè)計的系統(tǒng)只能取一個光盤，那么它的命令只有 “g+address” ，可是到了后面，系統(tǒng)具有取多盤的功能，就是說所要去的的光 盤個數(shù)的不確定的，那么單片機在讀取位置信息時就要有一個結(jié)束標志才能判 斷出來。所以要加上一個“e”來坐標標識符。而在實際中，g 是用十六進制的 0xfa 表示，e 用十六進制的 0xff 表示。下面是利用串口助手接受軟件發(fā)送數(shù) 據(jù)。利用它可以很方便地對串口發(fā)送數(shù)據(jù)進行監(jiān)控，這樣就可以在沒有與單片 機控制系統(tǒng)連接下也可以對軟件進行調(diào)節(jié)。 23 圖 5.4 取盤時軟件發(fā)送的數(shù)據(jù) 精度控制精度控制 利用我自己的單片機最小系統(tǒng)板和陳師傅介紹的驅(qū)動模塊，我已經(jīng)成功地 控制步進電機根據(jù)我的設(shè)想前進和后退，但是步進電機是按照脈沖數(shù)目來控制 的，而我電腦上保存的是光盤位置，還有因為光盤的間距很小，如何準確的把 光碟推出來，這些問題還值得我去思考。精度的調(diào)試主要經(jīng)過了三個階段。 階段一：階段一： 光碟槽在加工的時候是按照均勻位置距離來加工的，所以一開始，我按照 全程線性化的方法編寫單片機控制程序。因為光盤與光盤之間的距離為 3mm， 每個光盤的厚度為 2.1mm，從理論上說，絲桿上步進電機的步角為 1.8，每圈 需要的脈沖數(shù)為 200。當知道絲桿每一圈前進的距離，加上光盤厚度與間距， 就可以計算出對應(yīng)光盤位置所需要的脈沖。其表達式為，其中， 12 0 dd /200 pn （） l 為光盤厚度，為光盤間距，就是每個光盤間的實際距離。為絲 1 d 2 d 12 dd 0 l 桿每一圈的前進距離，因為我們每一圈需要 200 個脈沖，那么，就是每 0/ 200 l 24 個脈沖前進的距離。是當前要取的光盤位置，代入上式就能計算出理論需要n 的脈沖個數(shù) p。 當我滿懷信心去驗證我的實驗成果的時候，我發(fā)現(xiàn)步進電機并沒有到達相 應(yīng)的位置。在咨詢了家長后，我明白，在實際的加工過程中，是不可能實現(xiàn)光 碟槽位置的均勻分布的。 階段二：階段二： 通過網(wǎng)絡(luò)的問詢，我采用了一種新方法分段線性化。我首先測量一組 光盤位置與對應(yīng)脈沖個數(shù)的數(shù)據(jù)?？梢钥隙ǎ竭_這些位置，需要走的脈沖 個數(shù)是知道的。對于點與點之間的區(qū)域，近似認為是按線性變化的。這種方法 計算脈沖的表達式為，其中，是當前需要取的光盤所在 1 () iii ppkxx i p 分段區(qū)域中起點位置所對應(yīng)的脈沖數(shù)，是其坐標位置。是光盤所在分段 i x 1i k 區(qū)域中的近似斜率，計算公式為，為當前需要取的光盤位置。每個分段 i i y ix k x 區(qū)域中的近似斜率計算表達式為，為分段區(qū)域起點與終點坐標， 1 1 1 ii ii yy ixx k 1 , ii x x 為其對應(yīng)的脈沖個數(shù)。 1 , ii y y 經(jīng)過實際調(diào)試，利用以上方法能夠準確的定位到大部分的位置，但在某些 地方，還是不能準確定位。 階段三：階段三： 通過向指導(dǎo)老師的咨詢與自己慎重的考慮，我認為出現(xiàn)的問題主要有兩點。 第一可能是我測量時估計量不準確造成的，第二是這段范圍內(nèi)的光盤存放位置 的不均勻比較明顯而造成的。我又對我的控制方法進行了改進。我先在這些精 度比較差的范圍我重新測量了位置與脈沖對應(yīng)關(guān)系，然后對于一個關(guān)鍵的參數(shù) k，我修改了計算方法。原來的 k 在同一段范圍內(nèi)是不變的，現(xiàn)在我把它改為 一個動態(tài)值，定義脈沖計算公式為，其中為需要取的光 * () ii pkkxxxx 盤位置，為目標光盤所在分段區(qū)域的起點坐標，為它的斜率，定義為 i x i k ，為當前分段中斜率的變化率，其定義為，為對應(yīng)分段 i i y ix k * k 1 1 * ii ii kk xx k 1 , ii x x 起始和結(jié)束端點坐標，為他們對應(yīng)的斜率。 1 , ii k k 在實際中，驅(qū)動器選擇 64 分頻下，測到的位置與對應(yīng)脈沖關(guān)系如下： 25 x1x2x3x4x5x6 坐標837.85186.5109130.6 脈沖數(shù)20366106588145046246845311927373835 利用斜率分段線性化的流程框圖如下： 圖 5.5 利用斜率分段線性化的流程框圖 根據(jù)斜率分段線性化思路，先把整個區(qū)域分成六段，每段的端點位置分別 為 address_f 和 address_b，address_f 是首端點，所對應(yīng)測得的脈沖數(shù)為 pluse_f, address_b 為末端點,所對應(yīng)測得的脈沖數(shù)為 pluse_b。其實這里對于每個分段來 說，它的末端點就是下一分段的首端點。為了簡化說明，這里設(shè)為每段首端 i x 26 點對應(yīng)的位置，為其對應(yīng)的脈沖個數(shù)。這樣，利用以上定義式 i y ，就可以計算出每個光盤位置對應(yīng)的脈沖數(shù)了。 * () ii pkkxxx 利用分段線性化和斜率分段線性化畫出曲線如下： 圖 5.6 利用以上兩種方法畫出來的曲線 圖 5.7 曲線局部放大（虛線為分段線性化擬合，實線為斜率分段線性化擬合） 可以看出，利用斜率分段線性化擬合后，脈沖數(shù)量的增加是按端點斜率的 變化趨勢改變的。 經(jīng)過實際檢測，利用以上辦法，能夠很好解決誤差問題，取盤精度基本滿 意。 27 6.6.路徑算法的優(yōu)化與創(chuàng)新應(yīng)用路徑算法的優(yōu)化與創(chuàng)新應(yīng)用 我在原來設(shè)計中，裝置每次只能取一個光盤，當完成取盤操作后就自動回 復(fù)到初始零位。若使用者一次要取的盤很多時，這樣的操作就很浪費時間。我 當時就在想，是否既可以令裝置一次性取多盤，而且可以令裝置記錄當前位置， 節(jié)省復(fù)位時間？ 這個部分從想法的提出，到實現(xiàn)經(jīng)過了很漫長的過程。我先利用單片機里 的 eeprom 存儲了每次取盤完成后的當前位置，解決了每次取盤操作后復(fù)位的問 題，接著我再著力解決取多盤的問題。開始的時候，我是按照用戶選擇取盤的 順序來實現(xiàn)取盤的，就是說用戶先點擊 1 號盤，再點擊 2 號盤，再點擊 3 號盤， 那么系統(tǒng)就會按照 1，2，3 的順序來取出光盤，但在實際調(diào)試過程中發(fā)現(xiàn)，很 多時候取盤機構(gòu)都走了重復(fù)的路線。我就想能不能設(shè)計出一種有效的方法，讓 取盤機構(gòu)在最短的時間內(nèi)把光盤都取出來呢？順著這個思路，我在網(wǎng)上找了很 多資料，包括動態(tài)規(guī)劃，最優(yōu)設(shè)計，貪心算法等等，但是看到這些高深的東西， 我真的不知道如何下手。通過和指導(dǎo)老師交流后，老師推薦了我兩本書看，包 括如何進行思考 ， 算法設(shè)計與分析這兩本書對于一些基本的算法做了詳 細的介紹，還有具體的例子。我利用課余時間一點一點地看，老師也把書上的 部分內(nèi)容給我進行講解，我發(fā)現(xiàn)利用書上的算法，可以解決實際中很多難題。 例如旅行售貨員問題，最大團問題，這對于我思考其他問題帶來很大的啟發(fā)。 書本讓我理解了什么叫做樹，什么是圖，如何對樹進行遍歷，如何尋找最小生 成樹等。說實話，書上有些內(nèi)容我還不是很理解，但通過它們，我漸漸發(fā)現(xiàn)我 需要解決的關(guān)于在對短時間內(nèi)實現(xiàn)取多盤的問題應(yīng)該屬于最優(yōu)路徑問題，與旅 行售貨員問題有點相似，但又有所區(qū)別，它要尋找的是一條回路，而我的問題 是一條停止在最優(yōu)端點的最短路徑。這點的不同也使得我對算法的改進提供了 思路。 我設(shè)計的取盤最優(yōu)路徑算法我設(shè)計的取盤最優(yōu)路徑算法 1）取多盤問題的進一步闡述：）取多盤問題的進一步闡述： 在電機速度不變的情況下，最短時間內(nèi)把選定的光盤全部取出的問題實際 28 等效于一個最短路徑問題，就是要找出一個最短路徑，讓取盤機構(gòu)經(jīng)過各個目 標光盤存放點，并把光盤推出到指定位置。就像下面的示意圖(圖 6.1)： 圖 6.1 圓圈表示需要取的光盤，三角形代表當前取盤機構(gòu)的位置 上圖表示一個 3 層的光盤存放機構(gòu)，每層可以存放 10 張光盤。其中圓形表 示需要取的光盤，三角形表示取盤機構(gòu)當前的位置，事實上，取盤機構(gòu)的位置 是上一次取盤過程中取最后一張光盤的位置。由排列組合的知識可以算出，當 所需要取光盤個數(shù)為 n 時，那么可用的取盤的路徑條數(shù)為 n!，例如，以上所需 要取光盤個數(shù)為 7，那個可選的路徑數(shù)目為 5040 條！為了討論方便，我們減小 取盤數(shù)目，假設(shè)取盤數(shù)目為 3 個，見如下圖： 圖 6.2 需要取個光盤時表示圖 （圓圈表示需要取的光盤，三角形代表當前取盤機構(gòu)的位置） 可以算出上圖可選的路徑數(shù)目為 3！=6。問題需要求取總距離最短的路徑， 29 那么就必須有一個權(quán)衡路徑的量。在本算法中，定義光盤之間的距離為 ,其中是以裝置一個端點為原點時，第 i 個光盤的 1212 l |xxyy( ,) ii x y 坐標，由于實際中不可能測量每個光盤到原點的位置，我們利用光盤存放的位 置信息作為坐標。例如，上圖中光盤 c 的坐標為（9，3） ，光盤 b 的坐標為 （3，2） 。那么光盤 b 和光盤 c 的距離 l=|9-3|+|3-2|=7?？墒窃趯嶋H中光盤橫 向與縱向的比例不可能是 1：1，在計算縱向坐標時應(yīng)該把位置信息乘上一個大 于零的比例系數(shù) k，所以最終的計算公式應(yīng)該為，因為 1212 l |xxk yy k 是一個任意致，可以假設(shè) k=1。利用上圖雖然可以表示各個光盤的位置信息， 但還不夠直觀，利用圖的概念和以上定義的距離信息，可以得到以上坐標圖的 等效加權(quán)圖如下： 圖 6.3 加權(quán)圖表示光盤位置 其中線條之間數(shù)據(jù)表示兩個點之間的距離。1，2，3，4 表示需要走過的各 個節(jié)點，起點規(guī)定為 1 號節(jié)點。 2 2）基于回溯法的最短路徑探究）基于回溯法的最短路徑探究 前面提到，當需要取的光盤個數(shù)為 n 時，可選路徑數(shù)目為 n!，當需要取的 光盤數(shù)目為 10 個時，可選路徑達到 10！=3628800。所以必須采用一個系統(tǒng)的 方法來選取最優(yōu)路徑。這里采用回溯法來實現(xiàn)?；厮莘ㄓ小巴ㄓ媒忸}法”之稱。 用它可以系統(tǒng)地搜索問題的所有解?；厮莘ㄊ且粋€既帶有系統(tǒng)性又帶有跳躍性 的搜索算法。它在問題的解空間樹中，按深度優(yōu)先策略，從根結(jié)點出發(fā)搜索解 空間樹。算法搜索至解空間樹的任一結(jié)點時，先判斷該結(jié)點是否包含問題的解。 如果肯定不包含，則跳過對以該結(jié)點為根的子樹的搜索，逐層向其祖先結(jié)點回 30 溯；否則，進入該子樹，繼續(xù)按深度優(yōu)先策略搜索?；厮莘ㄇ蠼鈺r，只要搜索 到問題的一個解就可結(jié)束。 3 3）問題的解空間）問題的解空間 用回溯法解問題時，應(yīng)該明確定義問題的解空間。問題的解空間至少應(yīng)該 包含問題的一個（最優(yōu)）解。例如，對圖 6.4 所示，當需要取 3 個光盤時，按 光盤序號，可選的路徑為（1，2，3，4）,（1，2，4，3）,（1，3，4，2） ， （1，3，2，4） ， （1，4，2，3） ， （1，4，3，2） ，他們共同構(gòu)成一個解空間。 定義了問題的解空間后，還應(yīng)該將解空間很好地組織起來，使得能用回溯 法方便地搜索整個解空間。通常將解空間組織成樹的形式。對于圖 6.3 所示， 利用解空間樹表示如圖 6.4 所示： 圖 6.4 解空間樹表示 其中，aq 為樹的各個結(jié)點，結(jié)點間數(shù)字表示實際經(jīng)過的光盤編號和到達 這個光盤需要的路徑長度。例如從分支（a，b，c，f，l）表示遍歷順序為 （1，2，3，4） ，對應(yīng)路徑長度為 5，3，7，總共路程為 15。 4）回溯法的求解思路）回溯法的求解思路 確定了解空間的組織結(jié)構(gòu)后，回溯法從開始結(jié)點（根結(jié)點）出發(fā)，以深度 優(yōu)先方式搜索整個解空間。這個開始結(jié)點成為活結(jié)點，同時成為當前的擴展結(jié) 點。在當前擴展結(jié)點出，搜索向縱深方向移動至一個新的結(jié)點。這個結(jié)點成為 31 新的活結(jié)點，并成為當前擴展結(jié)點。如果在當前擴展結(jié)點處不能再向縱深方向 移動，則當前擴展結(jié)點就成為死結(jié)點。此時，應(yīng)該往回移動（回溯）至最近的 活結(jié)點處，并使這個活結(jié)點成為當前擴展結(jié)點?；厮莘ㄒ赃@種工作方式遞歸地 在解空間中搜索，直至找到所需求的解或者解空間中已無活動結(jié)點為止。 對圖 6.4 所示的解空間樹，回溯法找最短路勁時，從解空間樹的根節(jié)點 a 出發(fā)，搜索至 b，c，f，l。在葉結(jié)點 l 處記錄找到的路線為（1，2，3，4） ， 該路線長度為 15。從葉結(jié)點 l 返回至最近活動結(jié)點 f 處。由于 f 處已經(jīng)沒有可 擴展結(jié)點，算法又回到結(jié)點 c 處。結(jié)點 c 成為新擴展結(jié)點，由新擴展結(jié)點，算 法再移動至結(jié)點 g 后又移動至結(jié)點 m，得到路線為（1，2，4，3） ，其長度為 22，這個長度比之前的更長，所以舍棄。算法又依次返回至結(jié)點 g，c，b。從 結(jié)點 b，算法繼續(xù)搜索至結(jié)點 d，h，n。在葉結(jié)點 n 處，響應(yīng)的路線為 （1，3，2，4） ，其長度為 17，比當前最短路徑長，舍棄。從結(jié)點 n 算法返回 至結(jié)點 h，然后從開始繼續(xù)向縱深搜索至結(jié)點。依此方式算法繼續(xù)搜 索遍整個解空間，最終得到最小費用路徑為（，） ，其長度為 15。 5）算法的改進）算法的改進 從以上可以看到，回溯法搜索過程中，需要對整個解空間進行搜索，而在 實際中，往往有些結(jié)點顯然不能生成最優(yōu)解，所以可以采用有效的策略避免無 效搜索，提高回溯法的搜索效率。本算法采用剪枝法來提高搜索效率。其思路 是利用目標消耗最少的特點，把當前支路中的消耗與當前所求的最優(yōu)值比較， 當前支路中的消耗比當前所求的最優(yōu)解還大時，就沒有必要繼續(xù)往下搜索其他 結(jié)點了。其中剪枝標準的選取相當重要，合理的標準值可以提高算法的效率。 以上所述的回溯法在搜索過程中，其下層結(jié)點的選取是隨意的，而利用局 部最優(yōu)思想，在搜索過程中，對于每一個活動結(jié)點，先從其代價最小的一個分 支開始。其核心思想是利用局部最優(yōu)來達到整體最優(yōu)。例如，從跟結(jié)點出發(fā)， 其子結(jié)點只有，接著尋找的子結(jié)點為，從到他們的距離分別 為，選取距離最短的結(jié)點為新活動結(jié)點，這里選取，如此類推， 得到路徑為（，） ，其代價為?？梢钥闯?，第一次搜索到的路 徑不是最優(yōu)的，但肯定是目前分支中的次最優(yōu)。把它作為目前的剪枝標準值， 32 在接下來的回溯搜索過程中，只要發(fā)現(xiàn)當前分支的總路程大于 18，就可以停止 對其子結(jié)點的搜索了。 現(xiàn)在我們再來看圖 6.4 所示的解空間樹，由于本問題只需要把各個結(jié)點遍歷 就可以了，不需要回到開始位置。就是說，結(jié)點 l，m，n，o，p，q 都分別 是對應(yīng)路徑的末節(jié)點。而且，在所需要取的光盤個數(shù)為 n 時，只要前 n-1 個結(jié) 點確定了，那么最后一個結(jié)點就是唯一的。例如，當確定了路線為（1，2，3） 后，接著最后一個結(jié)點肯定就是 4。上面提到，利用剪枝法來提高搜索效率時， 剪枝標準的選取起到關(guān)鍵作用。設(shè) best_l 為當前問題的最短路徑長度，為其( )l i 對應(yīng)結(jié)點間的距離。有，那么對于任意的其路徑，設(shè)其路徑總長 1 _( ) n i bestll i 度為，有，令為各個結(jié)點中最短距離,為當前已經(jīng)搜索 o l_ o lbestl min l * _bestl 過的路徑中最短的路長度，則有,， * _bestl _bestl * minmin _bestllbestll 就是說，在接下來的搜索中，最優(yōu)路徑出現(xiàn)的條件為 。為當前正在搜索的路徑總長度。換句 * minmin 1 ( )_() j i l ilbestlljn 1 ( ) j i l i 話說，在當前正在生成的路徑中，只有滿足以上式子的時候，才能在其分支上 出現(xiàn)最優(yōu)路徑。也就是指當前的路徑總長度必須要小于。利用這個 * min _bestll 性質(zhì)，可以對剪枝標準進一步縮減，定義為，就是當前搜索到的最 * min _bestll 短路徑減去各個結(jié)點之間最短路徑的值。 利用這個標準再來看看圖 6.4 所示的問題。首先可以看出，各個結(jié)點中最 短距離=3，利用局部最優(yōu)的思路，選擇路徑最短的分支優(yōu)先生成，于是得到 min l 第一條路徑為（a，b，d，h，n）其路徑長度為 17，由于這是第一條生成的路 徑長度，令，于是當前的剪枝比較值為=14。接著回溯 * _17bestl * min _bestll 到 d 點，生成新的路徑為（a，b，d，i，o）其路徑長度為 21，比之前的大， 非最優(yōu)解。接著回溯到 b 點，由于到 c，e 兩個子結(jié)點消耗都相同，可以隨意選 取，按從左到右原則，先選取 c 結(jié)點。得到路徑為（a,b,c,f,l）其路徑總長度 33 為 15，比當前要少，于是令=15，當前的比較值變 * _bestl * _bestl * min _bestll 為 12。接著回溯到 c 點，此時可以算出，到達 g 點是路程長度為 15，大于 =12，所以不用再往下搜索了?；厮莸?b 點，進入 e 結(jié)點搜索。當 * min _bestll 到達 j 結(jié)點時，路