【正文】 從分支（ A， B， C， F， L）表示遍歷順序?yàn)椋?1， 2，3， 4），對(duì)應(yīng)路徑長(zhǎng)度為 5， 3， 7，總共路程為 15。通常將解空間組織成樹(shù)的形式。例如，對(duì)圖 所示，當(dāng)需要取 3個(gè)光盤(pán)時(shí)，按光盤(pán)序號(hào)，可選的路徑為（ 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)成一個(gè)解空間。 29 3） 問(wèn)題的解空間 用回溯法解問(wèn)題時(shí)，應(yīng)該明確定義問(wèn)題的解空間。如果肯定不包含，則跳過(guò)對(duì)以該結(jié)點(diǎn)為根的子樹(shù)的搜索，逐層向其祖先結(jié)點(diǎn)回溯；否則，進(jìn)入該子樹(shù)，繼續(xù)按深度優(yōu)先策略搜索。 它 在問(wèn)題的解空間樹(shù)中，按深度優(yōu)先策略，從根結(jié)點(diǎn)出發(fā)搜索解空間樹(shù)。用它可以系統(tǒng)地搜索問(wèn)題的所有解。這里 采用回溯法來(lái)實(shí)現(xiàn)。 2） 基于回溯法的最短路徑探究 前面提到， 當(dāng)需要取的光盤(pán) 個(gè)數(shù) 為 n時(shí)，可選路徑數(shù)目為 n!，當(dāng)需要取的光盤(pán)數(shù)目為 10個(gè)時(shí)，可選路徑達(dá)到 10！ =3628800。利用上圖雖然可以表示各個(gè)光盤(pán)的位置信息，但還不夠直觀，利用圖的概念 和 以上定義的距離信息，可以得到以上坐標(biāo)圖的等效加權(quán)圖如下： 圖 加權(quán)圖表示光盤(pán)位置 其中線條之間數(shù)據(jù)表示兩個(gè)點(diǎn)之間的距離 。那么光盤(pán) B和光盤(pán) C的距離 L=|93|+|32|=7。在本 算法中， 定義光盤(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)。由排列組合的知識(shí)可以算出，當(dāng)所需要取光盤(pán)個(gè)數(shù)為 n 時(shí)，那么可用的取盤(pán)的路徑條數(shù)為 n!，例如，以上所需要取光盤(pán)個(gè)數(shù)為 7，那個(gè)可選的路徑數(shù)目為 5040 條！為了討論方便，我們減小取盤(pán)數(shù)目，假設(shè)取盤(pán)數(shù)目為 3 個(gè)，見(jiàn)如下圖： 圖 需要?。硞€(gè)光盤(pán)時(shí)表示圖 （ 圓圈表示需要取的光盤(pán)，三角形代表當(dāng)前取盤(pán)機(jī)構(gòu)的位置 ） 可以算出上圖可選的路徑數(shù)目為 3！ =6。就像下面的示意圖 (圖 )： 圖 圓圈表示需要取的光盤(pán)，三角形代表當(dāng)前取盤(pán)機(jī)構(gòu)的位置 上圖表示一個(gè) 3 層的光盤(pán)存放機(jī)構(gòu)，每層可以存放 10 張光盤(pán)。這點(diǎn)的不同也使得我對(duì)算法的改進(jìn)提供了思路。書(shū)本讓我理解了什么叫做樹(shù)，什么是圖，如何對(duì)樹(shù)進(jìn)行遍歷，如何尋找最小生成樹(shù)等。我利用課余時(shí)間一點(diǎn)一點(diǎn)地看，老師也把書(shū)上的部分內(nèi)容給我進(jìn)行講解，我發(fā)現(xiàn)利用書(shū)上的算法，可以解決實(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ì)，貪心算法等等，但是看到這些高深的東西，我真的不知道如何下手。 我 先 利用 單片機(jī)里的EEPROM 存儲(chǔ)了每次取盤(pán)完成后的當(dāng)前位置，解決了每次取盤(pán)操作后復(fù)位的問(wèn)題，接著我再著力解決取多盤(pán) 的問(wèn)題 。若使用者 一次 要取的盤(pán)很多 時(shí) ，這樣的操作 就 很浪費(fèi)時(shí)間。 經(jīng)過(guò)實(shí)際檢測(cè)，利用以上辦法，能夠很好解決誤差問(wèn)題，取盤(pán)精度基本滿意 。這樣， 利用以上定義式*( ( ) )iiP k k x x x? ? ? ?，就可以計(jì)算出每個(gè)光盤(pán)位置對(duì)應(yīng)的脈沖數(shù)了 。其實(shí)這里對(duì)于每個(gè)分段來(lái)說(shuō)，它的末端點(diǎn)就是下一分段的首端點(diǎn)。 原來(lái)的 K 在同一段范圍內(nèi)是不變的，現(xiàn)在我把它改為一個(gè)動(dòng)態(tài)值， 定義脈沖計(jì)算公式為 *( ( ))iiP k k x x x? ? ? ?，其中 x 為需要取的光盤(pán)位置， 24 ix 為目標(biāo)光盤(pán)所在分段區(qū)域的起點(diǎn)坐標(biāo)， ik 為它的斜率，定義為 iiyi xk? ， *k 為當(dāng)前分段中斜率的變化率，其定義 為 11* iikkxxk ?????， 1,iixx? 為對(duì)應(yīng)分段起始和結(jié)束端點(diǎn)坐標(biāo)， 1,iikk? 為他們對(duì)應(yīng)的斜率。 我又對(duì)我的控制方法進(jìn)行了改進(jìn)。 階段 三： 通過(guò)向指導(dǎo)老師的咨詢與自己慎重的考慮，我認(rèn)為出現(xiàn)的問(wèn)題主要有兩點(diǎn)。每個(gè)分段區(qū)域中的近似斜率計(jì)算表達(dá)式為 111 iiyyi xxK ?? ?? ??， 1,iixx? 為分段區(qū)域起點(diǎn)與終點(diǎn)坐標(biāo)， 1,iiyy? 為其對(duì)應(yīng)的脈沖個(gè)數(shù)。這種方法計(jì)算脈沖的表達(dá)式為 1 ()i i iP P K x x?? ? ? ?，其中， iP 是當(dāng)前需要取的光盤(pán)所在分段區(qū)域中起點(diǎn)位置所對(duì)應(yīng)的脈沖數(shù)， ix 是其坐標(biāo)位置。可以肯定，要到達(dá)這些位置，需要走的脈沖個(gè)數(shù)是知道的。 階段 二： 通過(guò)網(wǎng)絡(luò)的問(wèn)詢，我采用了一種新方法 —— 分段線性化 。 當(dāng)我滿懷信心去驗(yàn)證我的實(shí)驗(yàn)成果的時(shí)候，我發(fā)現(xiàn)步進(jìn)電機(jī)并沒(méi)有到達(dá)相應(yīng)的位置。 0l 為絲桿每一圈的前進(jìn)距離，因?yàn)槲覀兠恳蝗π枰?200 個(gè)脈沖，那么， 0/200l 就是每個(gè)脈沖前進(jìn)的距離。當(dāng)知道絲桿每一圈前進(jìn)的距離，加上光盤(pán)厚度與間距，就可以計(jì)算出對(duì)應(yīng)光盤(pán)位置所需要的脈沖。因?yàn)楣獗P(pán)與光盤(pán)之間的距離為 3mm，每個(gè)光盤(pán)的厚度為 ，從理論上說(shuō)，絲桿上步進(jìn)電機(jī)的步角為 176。 精度的調(diào)試主要經(jīng)過(guò)了三個(gè)階段。利用它可以很方便地對(duì)串口發(fā)送數(shù)據(jù)進(jìn)行監(jiān)控，這樣就可以在沒(méi)有與單片機(jī)控制系統(tǒng)連接下也可以對(duì)軟件進(jìn)行調(diào)節(jié)。而在實(shí)際中， G 是用十六進(jìn)制的 0XFA表示， E 用十六進(jìn)制的 0XFF 表示。 控制命令 地址 結(jié)束標(biāo)志 設(shè)計(jì)命令格式 開(kāi)始的時(shí)候，我設(shè)計(jì)的系統(tǒng)只能取一個(gè)光盤(pán)，那么它的命令只有 22 “ G+Address”，可是到了后面，系統(tǒng)具有取多盤(pán)的功能 ，就是說(shuō)所要去的的光盤(pán)個(gè)數(shù)的不確定的，那么單片機(jī)在讀取位置信息時(shí)就要有一個(gè)結(jié)束標(biāo)志才能判斷出來(lái)。這部分一開(kāi)始時(shí)我還真沒(méi)有頭緒，因?yàn)閱纹瑱C(jī)主要是利用串口與電腦通信的，而該 如何處理發(fā)送數(shù)據(jù)才能實(shí)現(xiàn)與單片機(jī)的溝通呢？經(jīng)過(guò)在網(wǎng)上一些論壇發(fā)帖咨詢，還有與指導(dǎo)老師的討論，我才形成了現(xiàn)在的那種以控制標(biāo)識(shí)符，數(shù)據(jù)內(nèi)容，命令結(jié)束標(biāo)志為組合的控制信息。 整個(gè) 控制系統(tǒng)結(jié)構(gòu)圖如下： 圖 控制系統(tǒng)結(jié)構(gòu) 設(shè)置 控制 命令格式 PC 作為整個(gè)系統(tǒng)的控制中心，在設(shè)計(jì)中要解決的一個(gè)重點(diǎn)是如何利用軟件控制整套系統(tǒng) 。經(jīng)過(guò)測(cè)試，效果基本滿意。 在我的設(shè)想之中，裝置進(jìn)行取盤(pán)操作的隨后對(duì)應(yīng)光碟的位置的 LED指示燈會(huì)亮起來(lái)， 因?yàn)?裝置對(duì) LED指示燈 的 即時(shí)性 要求不是 很高，小何哥哥提議利用單片機(jī)的 SPI 口＋串行移位芯片實(shí)現(xiàn) 來(lái)實(shí)現(xiàn) 指示燈的功能 。經(jīng)過(guò)測(cè)試和實(shí)際調(diào)整，基本能夠?qū)崿F(xiàn)我的要求。所以我采用了第三種方案。在之前檢測(cè)方式選擇時(shí) ，我在網(wǎng)上找到，利用光電管的特性，很容易設(shè)計(jì)出一個(gè)檢測(cè)電路，當(dāng)光電管間有遮擋物時(shí)輸出 0V，沒(méi)有遮擋物時(shí)輸出 5V，電路圖如下圖所示： 20 圖 光電管的檢測(cè)電路 但問(wèn)題是怎么樣令單片機(jī)檢測(cè)到這些信號(hào)呢？我向小何哥哥請(qǐng)教，他給我說(shuō)了幾個(gè)方案，一是可以利用并進(jìn)串出芯片串聯(lián)起來(lái)，可是這樣檢測(cè)速度就有所限制，二是利用模擬開(kāi)關(guān)對(duì)信號(hào)一個(gè)一個(gè)檢測(cè)，但是這樣需要很多 IO 口，而單片機(jī)上只有 32個(gè) IO口，三是利用鎖存器加譯碼芯片。 接下來(lái)是光電管的檢測(cè)電路。 為了簡(jiǎn)化裝置，陳師傅向我推薦了幾款步進(jìn)電機(jī)驅(qū)動(dòng)器，單片機(jī)產(chǎn)生的 PWM脈沖信號(hào)輸入到驅(qū)動(dòng)器后就可以控制步進(jìn)電機(jī)。 按照設(shè)計(jì) 和加工 的樣式， 模型由三部分組成，第一部分是光盤(pán)存放架子，光盤(pán)可以豎著放到架子上；第二部分是 絲桿和螺母組成的運(yùn)動(dòng)部分，一個(gè)步進(jìn)電機(jī)帶動(dòng)著絲桿轉(zhuǎn)動(dòng)而讓另外一個(gè)步進(jìn)電機(jī)橫向移動(dòng)，當(dāng)?shù)竭_(dá)設(shè)定位置時(shí)，另外一個(gè)步進(jìn)電機(jī)運(yùn)作，帶動(dòng)一個(gè)撥盤(pán)把光盤(pán)從架子上推出來(lái)。 因?yàn)檫@裝置要求的精度非常高，且運(yùn)用到了高級(jí) 的工業(yè)加工技術(shù)，以我現(xiàn)在的知識(shí)面 和條件 ，顯然是無(wú)法 單獨(dú)開(kāi)展這樣的工作 。 通過(guò)這一系列的實(shí)驗(yàn)，我對(duì)單片機(jī)的了解也越來(lái)越深，對(duì)單片機(jī)中斷， IO 口操作，定時(shí)器使用， PWM 發(fā)生器使用等也有形成了基本 認(rèn)識(shí) 。最后，小何哥哥讓我在板上焊接了 8 個(gè)調(diào)試燈，并給了我一些基礎(chǔ)的程序，讓我參照著 它們 來(lái)控制這些燈。最后發(fā)現(xiàn)原來(lái)是有一條線沒(méi)有連接好。 我很快就把 電路焊接好了，可是上電后，我把小何哥哥給我的串口調(diào)試程序下載到芯片后芯片不能正常和 PC機(jī)通信，我一下子懵了。幸虧一切正常，小何哥哥說(shuō)利用仿真器能夠正常連接到芯片，這表明芯片已經(jīng)能正常工作了。到了最后，小何哥哥給我檢查了一遍，確定沒(méi)有問(wèn)題后，就開(kāi)始最重要的時(shí)刻，上電。焊接電路真是一個(gè)細(xì)致活，小何哥哥說(shuō)假如某個(gè)地方短路就很容易把芯片給燒了。我做的最小系統(tǒng)板包括幾個(gè)部分，第一是供電電路，是利用 7805 芯片實(shí)現(xiàn)的；第二是串口通信電路，小何哥哥說(shuō)我的設(shè)計(jì)需要用到單片機(jī)跟 PC 機(jī)的通信，比較簡(jiǎn)單而且可行的方法是利用串口，只需要一條串口線和 Max232 芯片就可以了；第三部分是單片機(jī)的復(fù)位電路；第四部分是調(diào)試口，因?yàn)樾『胃绺缒抢镉蠮TAGICE 調(diào)試工具，只需要把單片機(jī) 對(duì)應(yīng)端口按順序引出就可以了。 經(jīng)過(guò)模擬的訓(xùn)練后，我在小何哥哥的指導(dǎo)下 做自己的單片機(jī)最小系統(tǒng)板。他先是很系統(tǒng)地 教了我一些 C語(yǔ)言在 單片機(jī)開(kāi)發(fā)中的應(yīng)用，然后他還教我如何利用 一個(gè)專(zhuān)門(mén)的模擬軟件來(lái)模擬實(shí)驗(yàn)效果 。他 建議我用 AVR 的單片機(jī)來(lái)做，因?yàn)檫@款單片機(jī)入門(mén)資料比較多，而且價(jià)格便宜，使用方便 ，而且他對(duì)AVR比較了解。我因?yàn)榇蛩阌?C語(yǔ)言編寫(xiě)單片機(jī)程序，所以首先我先去購(gòu)書(shū)中心買(mǎi)了一本有關(guān) C語(yǔ)言入門(mén)和單片機(jī)教程的書(shū)籍來(lái)看。利用它與電腦進(jìn)行通信，并且控制裝置上的其他東西。那次去 工廠 參觀時(shí)，我特意去問(wèn)了這個(gè)問(wèn)題，工作的師傅說(shuō)他 18 們?cè)O(shè)計(jì)的那些裝置都有自己的控制單元。我設(shè)想中是利用電腦直接控制電機(jī)和接受信號(hào)就可以了。而在軟件中用戶可以根據(jù)實(shí)際需要設(shè)立和修改用戶名和對(duì)應(yīng)密碼，編輯子窗口如下： 圖 用戶信息 按確認(rèn)后軟件會(huì)把數(shù)據(jù)儲(chǔ)存到對(duì)應(yīng)的用戶管理表中。 16 圖 提示窗口 用戶管理子窗體設(shè)計(jì) 本軟件有用戶使用限制，用戶可以根據(jù)需要設(shè)計(jì)用戶密碼來(lái)防止別人修改數(shù)據(jù)庫(kù)中的內(nèi)容。用戶按要求填寫(xiě)好信息，按保存按鈕就可以把新的光碟信息保存下來(lái)。 圖 新光碟信息輸入窗口 第二種途徑是用戶自己在對(duì)應(yīng)分類(lèi)的圖書(shū)列表中直接按添加按鈕添加新的信息。 15 圖 模糊查找 管理軟件中新光碟信息的輸入 只需輸入一次。第一是利用光碟分類(lèi)管理形 成的結(jié)構(gòu)，把不同的光碟分門(mén)別類(lèi)地顯示出來(lái)，用戶只需要打開(kāi)對(duì)應(yīng)的樹(shù)狀分類(lèi)表就可以瀏覽對(duì)應(yīng)光碟的信息。它能夠?qū)崿F(xiàn)光碟信息的添加、修改、刪除、快速查找、取盤(pán)等功能。 具體實(shí)現(xiàn)效果如下： 圖 分類(lèi) 對(duì)于選定的分類(lèi)，可以按需要隨時(shí)添加、修改、刪除下一層節(jié)點(diǎn)。對(duì)于光碟分類(lèi)設(shè)立一個(gè)專(zhuān)門(mén)的表來(lái)儲(chǔ)存信息，用戶可以根據(jù)設(shè)計(jì)的需求對(duì)光碟類(lèi)別進(jìn)行添加、修改、刪除，這樣就能夠把各種光碟分門(mén)別類(lèi)地保存起來(lái)。具體設(shè)計(jì)見(jiàn)下圖： 圖 主 窗體結(jié)構(gòu) 效果如下： 圖 效果 13 在主窗體中插入兩個(gè)菜單欄，分別為 “ 基本信息管理 ” 和 “ 系統(tǒng)用戶管理 ” 。 根據(jù)以上需求，設(shè)計(jì) VB 框架如下： 12 圖 VB框架圖 主窗體設(shè)計(jì) 主窗體是打開(kāi)軟件時(shí)的第一個(gè)窗體，對(duì)于數(shù)據(jù)庫(kù)的一切操作都是在它上面完成。這樣一步一步地嘗試，我現(xiàn)在是在整個(gè)數(shù)據(jù)庫(kù)中建立了幾張數(shù)據(jù)表，分別是光盤(pán)基本信息表，光盤(pán)分類(lèi)表，用戶資料表，光盤(pán)動(dòng)態(tài)信息表等。我開(kāi)始時(shí)先把想到的需要保存的信息制作出幾個(gè)表來(lái)，其中包括光盤(pán)信息表，用戶信息表，針 對(duì)著這兩個(gè)表在 VB 中分別建立連接。對(duì)于整個(gè)系統(tǒng)來(lái)說(shuō)，其核心部分應(yīng)該是數(shù)據(jù)庫(kù)，而其中表的建立是基礎(chǔ)。 11 圖 我做的圖書(shū)管理軟件界面 實(shí)際設(shè)計(jì) 通過(guò)前期的準(zhǔn)備，我對(duì) VB 程序設(shè)計(jì)，數(shù)據(jù)庫(kù)使用 以及其的二次開(kāi)發(fā) 有了更深的了解。通過(guò)這個(gè)練習(xí)，我對(duì)自己需要設(shè)計(jì)的系統(tǒng)有了更多的了解，我知道 該 如何下手了。這個(gè)軟件從包括從數(shù)據(jù)庫(kù)的建立，數(shù)據(jù)表的設(shè)計(jì)，到 VB 中界面的設(shè)計(jì)，各個(gè)控件的使用和協(xié)調(diào)，數(shù)據(jù)的查詢搜索，更新，刪除等都用上了，是 我之前所學(xué)知識(shí)的一個(gè)綜合使用。 之前的學(xué)習(xí)主要是 了解和熟悉 各個(gè)控件的使用，對(duì)數(shù)據(jù)庫(kù)和 VB 中的一些基本原理更加了解。為了練習(xí)如何利用 ADO 對(duì)數(shù)據(jù)庫(kù)進(jìn)行操作，對(duì)著書(shū)本上的例子，我做了一個(gè)數(shù)據(jù)庫(kù)數(shù)據(jù)查詢器，利用它可以對(duì)數(shù)據(jù)庫(kù)所建立的表中數(shù)據(jù)進(jìn)行查詢，并把結(jié)果顯示出來(lái)。 圖 練習(xí) 建立的圖書(shū)信息表 10 由于系統(tǒng)中需要利用 VB對(duì)數(shù)據(jù)庫(kù)進(jìn)行操作，從資料上我知道， VB通過(guò) ADO可以方便對(duì)數(shù)據(jù)庫(kù)進(jìn)行操作的。老師還為我講解了數(shù)據(jù)庫(kù)中常用的 SQL 語(yǔ)言，通過(guò)學(xué)習(xí)，我知道了基本的數(shù)據(jù)庫(kù)操作語(yǔ)言， 例如 insert、 delete、 update、 select 等命令的使用格式 。指導(dǎo)老師針對(duì)我系統(tǒng)的設(shè)計(jì)需求，給我有針對(duì) 性 地進(jìn)行輔導(dǎo)。 學(xué)會(huì)使用 VB 僅僅是個(gè)開(kāi)始，因?yàn)槲以O(shè)計(jì)的系統(tǒng)中需要用到數(shù)據(jù)庫(kù)，而這方面 我完全沒(méi)有學(xué)習(xí)過(guò)的。還有就是數(shù)據(jù)的類(lèi)型也要特別注意，因?yàn)槔?TEXT 控件來(lái)顯示數(shù)據(jù)和結(jié)果，他需要的是字符型的數(shù)據(jù)，而在運(yùn)算過(guò)程中，利用的是數(shù)字型的數(shù)據(jù)，這樣在不同的地方就要對(duì)數(shù)據(jù)進(jìn)行恰當(dāng)?shù)霓D(zhuǎn)換。老師說(shuō)我應(yīng)該循序漸進(jìn)，所以我第一步是以設(shè)計(jì)一個(gè)簡(jiǎn)易計(jì)算器為目標(biāo)的 ，作為一個(gè)前期的學(xué)習(xí)階段 。 但 對(duì)于數(shù)據(jù)庫(kù)我的概念就比較模糊，只感覺(jué)是一門(mén)高深的 學(xué)