【正文】 e_operation(){int i。while(()!=0){i=()。switch(i) {東北石油大學(xué)華瑞學(xué)院本科生畢業(yè)設(shè)計(jì)（論文）17　 case 1:{front_1()。break。}case 2:{front_2()。break。}case 3:{back_1()。break。}case 4:{back_2()。break。}case 5:{left_1()。break。}case 6:{left_2()。break。}case 7:{right_1()。break。}case 8:{right_2()。break。}case 9:{up_1()。break。}case 10:{up_2()。break。}case 11:{down_1()。break。}case 12:{down_2()。break。} }()。}} 以上就是這部分搜索實(shí)現(xiàn)的關(guān)鍵，搜索過程采用的是廣度優(yōu)先搜索，只要對以上的問題有了了解，搜索起來就不是很困難，但在搜索過程中涉及到搜索優(yōu)化的問題。由于結(jié)點(diǎn)的擴(kuò)展采用的是樹型結(jié)構(gòu)，所以，優(yōu)化就是對搜索樹的剪枝。在魔方的操作中有這么兩種情況值得注意：一種是，如果上次的操作是某個(gè)面的順時(shí)針操作，這次操作如果是這個(gè)面的逆時(shí)針操作的話，就會(huì)回到魔方的初始狀態(tài)，以根結(jié)點(diǎn)為例，當(dāng)對根結(jié)點(diǎn)的某個(gè)面進(jìn)行一次順時(shí)針操作，再進(jìn)行一次逆時(shí)針操作，這個(gè)時(shí)候的魔方的狀態(tài)就是根結(jié)點(diǎn)的狀態(tài)，也就是說，在對這個(gè)結(jié)點(diǎn)進(jìn)行擴(kuò)展是毫無意義的。這是在不斷的重復(fù)根結(jié)點(diǎn)的擴(kuò)展。也就是說，對同一個(gè)面的兩次相鄰的操作不能是互逆的，也就是，不能對它進(jìn)行順時(shí)針（逆時(shí)針）操作后，在進(jìn)行逆時(shí)針（順時(shí)針）操作。所以，在搜索樹的擴(kuò)展中，對這種操作應(yīng)該采取剪枝。另一種情況是，每當(dāng)對同一個(gè)面進(jìn)行四次相同的操作后（四次順時(shí)針或四次逆時(shí)針）也會(huì)回到最初的狀態(tài)，如果對上面的剪枝有了了解，這個(gè)就不是很難理解。所以，對這部分操作也要采取剪枝操作。下面給出剪枝和和搜索的一部分代碼，是對前面順時(shí)針旋轉(zhuǎn)操作擴(kuò)展的代碼，其它面的進(jìn)行搜索時(shí)擴(kuò)展的代碼和這些基本相同。其中，re_check來判斷是否需要剪枝。//不擴(kuò)展上次旋轉(zhuǎn)的逆操作if(re_check!=2) {front_1()。(*p)()。if(solve_1==true)東北石油大學(xué)華瑞學(xué)院本科生畢業(yè)設(shè)計(jì)（論文）18{newnode=new nodec。 //申請新結(jié)點(diǎn)newnodenext=NULL。newnodev=1。 //旋轉(zhuǎn)方式newnodeparent=here。 //指向父結(jié)點(diǎn) heref_1=newnode。 //父結(jié)點(diǎn)前面順時(shí)針指針指向新結(jié)點(diǎn) nextnodenext=newnode。 //新結(jié)點(diǎn)插入隊(duì)尾，構(gòu)造擴(kuò)展鏈表 nextnode=newnode。 break。}else{newnode=new nodec。 //申請新結(jié)點(diǎn)newnodenext=NULL。newnodev=1。 //旋轉(zhuǎn)方式newnodeparent=here。 //指向父結(jié)點(diǎn)heref_1=newnode。 //父結(jié)點(diǎn)前面順時(shí)針指針指向新結(jié)點(diǎn)nextnodenext=newnode。 //新結(jié)點(diǎn)插入隊(duì)尾，構(gòu)造擴(kuò)展鏈表nextnode=newnode。front_2()。 //恢復(fù)到擴(kuò)展前的狀態(tài)(1)。 //剪枝序列 }}在這里還有一點(diǎn)要說明，雖說第二種剪枝按理說是應(yīng)該執(zhí)行的，但由于搜索只是應(yīng)用在了解決魔方問題的第一部分，并且，在這里搜索樹的層數(shù)不會(huì)達(dá)到四層，所以，在程序里我就沒有對這種情況進(jìn)行剪枝的操作。到這里搜索部分就算是結(jié)束了，剩下的就是如何將它應(yīng)用到解決到魔方復(fù)原的第一段，關(guān)于這個(gè)會(huì)在談?wù)搶＜蚁到y(tǒng)的時(shí)候給出?！＜蚁到y(tǒng)模塊專家系統(tǒng)模塊()。這是程序中最為關(guān)鍵的一個(gè)模塊，在這里將魔方中復(fù)雜的旋轉(zhuǎn)序列與程序結(jié)合到了一起，從而完成了對魔方的求解。這部分的程東北石油大學(xué)華瑞學(xué)院本科生畢業(yè)設(shè)計(jì)（論文）19序并不是很難寫，關(guān)鍵是知道如何解決魔方問題，也就是知道按照什么樣的規(guī)律來解決魔方問題。每當(dāng)找到符合要求的狀態(tài)時(shí)就調(diào)用專家序列給出正確的求解步驟。這種方法很多，由于方法的不同，會(huì)影響到魔方求解時(shí)的步驟多少問題。我在這里選擇的是“八角法”，這種方法解決魔方問題在求解的步驟上并不是很好，也就是步驟會(huì)比較多，選擇它只是因?yàn)樗鼘W(xué)起來比較容易，因?yàn)槲乙彩遣沤佑|魔方，所以選擇了一個(gè)比較容易學(xué)習(xí)的方法來處理這個(gè)問題。在這里有一點(diǎn)需要說明，雖然求解的步驟比較多，但是在求解的速度上并沒有什么太大的不同，一般來說用不上一秒就可以求解。下面就我所采用的專家方法—“八角法”給以說明。由于，并不是魔方玩法的教學(xué)，所以，我只是簡單的介紹，重點(diǎn)是這個(gè)方法在程序中是如何表示出來的?！鞍私欠ā?，就是在解決魔方問題的時(shí)候，首先復(fù)原魔方的八個(gè)角塊。然后在復(fù)原其它的小塊?！鞍私欠ā苯鉀Q魔方問題一共分為八個(gè)階段。在進(jìn)行“八角法”之前要恢復(fù)魔方的八個(gè)角塊的位置，但顏色不對，這個(gè)過程是用另一種方法完成的，因?yàn)樵凇鞍私欠ā敝胁]有給出這部分的是如何解決的。接下來介紹一下“八角法”解決魔方問題的八個(gè)階段。第一階段是在魔方的頂面構(gòu)建出一個(gè)“X”，可以任意指定魔方的頂面，在我的程序中我指定的這個(gè)階段的頂面為白色。所謂“X ”就是頂面的角塊向上的顏色與中塊的顏色相同。第二階段是在魔方的底面構(gòu)建出一個(gè)“X”，在第一階段后， 所有含底面顏色的角塊，應(yīng)該都在底面，只可能色向不對。這個(gè)過程與上面的過程相似，只要把底面轉(zhuǎn)到頂面，然后把底面當(dāng)做頂面來處理。第三階段是復(fù)原所有的角塊，通過前兩個(gè)階段后魔方的頂面和底面的角塊都已經(jīng)在自己的位置，而且向上面的顏色都已經(jīng)符合要求，只剩下角塊的邊色沒有對上。而這個(gè)階段就是要解決這個(gè)問題。在這里需要為成對的上角快和下角塊分別記數(shù)，如果每個(gè)側(cè)面上兩個(gè)上角塊或兩個(gè)下角塊的顏色相同就為一對。然后根據(jù)成對的情況來選擇合適的魔方旋轉(zhuǎn)序列。第四階段是在頂面恢復(fù)三個(gè)正確的邊塊。在這里邊塊的位置和色向都要考慮，每次只考慮一塊，直到這個(gè)階段的完成。在這個(gè)階段只恢復(fù)三個(gè)邊塊，當(dāng)然，有的時(shí)候很碰巧第四個(gè)邊塊也在正確的位置，這個(gè)先不用過多的考慮，在下面的階段會(huì)給這種情況的處理方法。第五階段是恢復(fù)底面的所有邊塊。在第四階段有一個(gè)邊塊沒有恢復(fù)，在這里就要用到這個(gè)邊塊，把他當(dāng)作“洞”，如果在上個(gè)階段碰巧四個(gè)邊塊都恢復(fù)了，那么在這里就以任意一個(gè)上邊塊當(dāng)作“洞”。把這個(gè)“洞”轉(zhuǎn)到前面，然后尋找要到要恢復(fù)的下邊塊的位置套用具體的旋轉(zhuǎn)序列。重復(fù)這階段的操作，直到底面的邊塊都復(fù)原。第六階段是恢復(fù)頂面的最后一個(gè)邊塊。當(dāng)然，如果在第四階段已經(jīng)恢復(fù)的話東北石油大學(xué)華瑞學(xué)院本科生畢業(yè)設(shè)計(jì)（論文）20在這里就不需要這個(gè)過程，直接進(jìn)入第七階段。在這里旋轉(zhuǎn)魔方，把有“洞”的頂面轉(zhuǎn)到左面或者右面，然后選擇合適的旋轉(zhuǎn)序列，恢復(fù)這最后一個(gè)邊塊。第七階段是恢復(fù)魔方中間邊塊的過程。在上面幾個(gè)階段過后，魔方基本上已經(jīng)被復(fù)原了，只剩下魔方的中間塊沒有被復(fù)原。這沒有什么難度，只需要找出沒有被復(fù)原的中間塊的具體狀態(tài)后，就可以套用固定的旋轉(zhuǎn)序列來求解。當(dāng)然，有的時(shí)候由于情況比較特殊，沒有符合的專家操作序列。不過只要通過旋轉(zhuǎn)魔方就可以找到符合要求的狀態(tài)。第八階段是恢復(fù)魔方中間邊塊的色向。在這里和上面一樣，魔方原來的頂面和底面依然擺放到魔方的左右兩面，然后找到符合要求的狀態(tài)，套用專家操作序列。通過上面的八個(gè)階段，魔方在大部分情況下就已經(jīng)被復(fù)原了。因?yàn)橛行O其特殊的情況用這種方法沒有辦法求解，這個(gè)問題在前面已經(jīng)談過。通過上面對“八角法”的敘述可以看出，這個(gè)部分沒有什么多大的難度，只要把魔方狀態(tài)考慮完全就可以了。只是在魔方第一階段前的八個(gè)角塊的復(fù)原有些需要說明的。在復(fù)原魔方八個(gè)角塊的時(shí)候，用到了在上節(jié)提到的搜索技術(shù)。因?yàn)?，?fù)原八個(gè)角塊的專家序列也是在要恢復(fù)的角塊在某些固定的位置的時(shí)候才能夠起到作用。但是在魔方的初始狀態(tài)中，要恢復(fù)的角塊不一定是符合要求的，這就需要旋轉(zhuǎn)魔方將要恢復(fù)的角塊轉(zhuǎn)到符合要求的位置。這個(gè)過程如果考慮各個(gè)可能的情況是很難的，所以用到了搜索，這樣可以很快的將要恢復(fù)的角塊轉(zhuǎn)到符合要求的位置，從而很快的對魔方求解。恢復(fù)八個(gè)角塊的過程是由這個(gè)模塊中的firststage()函數(shù)實(shí)現(xiàn)的，因?yàn)樵谶@里在搜索的過程中要時(shí)刻對比搜索到的魔方狀態(tài)是否符合那幾種固定的要求，所以，為了方便操作，用到了一個(gè)指向函數(shù)的指針(p)，關(guān)于它的定義在前面已給出說明，這樣是可以很方便的來調(diào)用對比函數(shù)（para1()、para2()、para3() 和para4()）。關(guān)于其它幾個(gè)階段的實(shí)現(xiàn)分別是由secondstage()、thirdstage()、forthstage()、fifthstage()、sixthstage()、sevenstage() 和eightstage()來完成的 [16]。由于在這個(gè)模塊的各個(gè)函數(shù)中都是一些專家序列，程序無外就是將魔方的狀態(tài)與它們比較，如果符合要求就調(diào)用專家序列，不符合要求就通過旋轉(zhuǎn)魔方，使魔方的狀態(tài)符合要求再調(diào)用專家序列。所以在這里不給出任何代碼?！”菊滦〗Y(jié)通過以上可以看出主模塊是建立在各個(gè)分模塊相互調(diào)用的基礎(chǔ)上，對文件接收模塊、程序執(zhí)行模塊、旋轉(zhuǎn)操作模塊、搜索模塊以及專揀模塊分別進(jìn)行說明，并給出基本求解過程和圖解。東北石油大學(xué)華瑞學(xué)院本科生畢業(yè)設(shè)計(jì)（論文）21第 4 章　程序演示(1)程序開始運(yùn)行后的顯示。圖 41　程序啟動(dòng)后的界面(2)輸入魔方文件后的顯示。圖 42　魔方的初始狀態(tài)(3)選擇人工解決后的顯示。東北石油大學(xué)華瑞學(xué)院本科生畢業(yè)設(shè)計(jì)（論文）22圖 43　人工操作界面(4)在選擇人工解決后輸入f+ 后的顯示。圖44　人工選擇一個(gè)操作后的狀態(tài)(5)在輸入“h ”后的顯示。圖 45　人工操作中間選擇 h 后由電腦自動(dòng)求解(6)在程序一開始就輸入電腦。東北石油大學(xué)華瑞學(xué)院本科生畢業(yè)設(shè)計(jì)（論文）23圖 46　在程序開始選擇電腦自動(dòng)求解到這里已經(jīng)把程序的執(zhí)行過程簡單地做了演示。東北石油大學(xué)華瑞學(xué)院本科生畢業(yè)設(shè)計(jì)（論文）24結(jié)　論這次畢業(yè)設(shè)計(jì)所選的題目對我來說是一個(gè)很大的挑戰(zhàn)，因?yàn)樵谝郧皬膩頉]有寫過任何與專家系統(tǒng)有關(guān)的程序。剛開使拿到這個(gè)題目的時(shí)候，沒有考慮很多，也沒有想到這個(gè)問題會(huì)那么不容易解決。在慢慢開始著手做這個(gè)程序的時(shí)候才發(fā)現(xiàn)有很多東西是我沒有接觸過的，這些都需要通過自己來學(xué)習(xí)。在程序的編寫過成中遇到了很多的困難，有些困難曾讓我有放棄的念頭，因?yàn)樵诋?dāng)時(shí)真的不知道如何來解決這些問題。所以本打算在假期就將這個(gè)題目徹底解決的念頭也隨著這些困難消失了，而且無論怎么想也找不到很好的解決辦法。這些困難主要是在如何構(gòu)建魔方的狀態(tài)圖，如何完成對魔方各個(gè)面的旋轉(zhuǎn)操作，如何在搜索中如何解決數(shù)據(jù)結(jié)構(gòu)的問題等等。在假期快要結(jié)束的時(shí)候，找到了構(gòu)建魔方狀態(tài)圖的方法，也完成了對魔方各個(gè)面旋轉(zhuǎn)操作的函數(shù)的編寫。在這個(gè)時(shí)候，我以為只要將搜索部分完成，這個(gè)題目就可以順利的解決，根本沒有考慮到專家系統(tǒng)的問題。在開學(xué)后，開始著手搜索部分程序的編寫，當(dāng)這部分程序編寫完以后，新的問題又出現(xiàn)了。這就是由于魔方狀態(tài)圖很大，而我采用的是盲目搜索，這樣的話在搜索樹每增加一層的時(shí)候魔方的狀態(tài)圖會(huì)以幾何數(shù)級增長，這需要大量的存儲(chǔ)空間，占用大量的內(nèi)存。所以我改變的了對魔方狀態(tài)圖的存儲(chǔ)方法，采用了不存儲(chǔ)狀態(tài)數(shù)組，而是存儲(chǔ)魔方的旋轉(zhuǎn)方式的，再通過回朔來找到要擴(kuò)展的狀態(tài)圖的當(dāng)前狀態(tài)。但是這樣也沒有解決這個(gè)問題，并且我發(fā)現(xiàn)在我的機(jī)器上搜索樹最多也就能擴(kuò)展到七層，當(dāng)?shù)狡邔拥臅r(shí)候我的內(nèi)存就被耗盡了。這也就說明我的程序只能解決在七步之內(nèi)找到復(fù)原路徑的魔方，而且速度相當(dāng)?shù)穆?。在那個(gè)時(shí)候這是另我最頭痛的問題。在沒有辦法用盲目搜索解決這個(gè)問題的時(shí)候我考慮到了專家系統(tǒng)。于是找了很多關(guān)于魔方的玩法的資料，在這些資料中只有“八角法”是最適合初學(xué)者的。但是，新的問題又出現(xiàn)了，這個(gè)方法是在復(fù)原了八個(gè)角塊以后才可以用的，但它并沒有給出如何恢復(fù)八個(gè)角塊的序列。不過還好，在同學(xué)的幫助下找到了如何復(fù)原八個(gè)角塊的操作方法。在這個(gè)時(shí)候我認(rèn)識到，如果想解決這個(gè)題目自己必須要學(xué)習(xí)玩魔方，于是就照著我找到的資料開始學(xué)習(xí)如何玩魔方，還好在幾天后終于將魔方復(fù)原了。于是開始著手專家系統(tǒng)的編寫，在一個(gè)禮拜左右后我將這個(gè)題目基本上解決了，只是有些特殊的情況是無法解決的，在幾次改進(jìn)后有些特殊的情況也的到了解決?，F(xiàn)在的程序基本上可以解決大部分魔方狀態(tài)。東北石油大學(xué)華瑞學(xué)院本科生畢業(yè)設(shè)計(jì)（論文）25參 考 文 獻(xiàn)[1]　[M].北京:機(jī)械工業(yè)出版社,[2]?。幊趟枷耄ǖ诙妫?,第1卷:標(biāo)準(zhǔn)C＋＋引導(dǎo)[M]. 北京: 機(jī)械工業(yè)出版社,[3]　 C++編程技巧精選500例[M].北京: 中國水利水電出版社,[4]?。幊趟枷?,第2卷:實(shí)用編程技術(shù)[M]. 北京: 機(jī)械工業(yè)出版社,[5]　 C++實(shí)效編程百例[M].北京:人民郵電出版社,[6]　Scott Meyers. Effective C++（第三版） （中文版）——改善程序技術(shù)與設(shè)計(jì)思維的55個(gè)有效做法[M].電子工業(yè)出版社,[7]　朱戰(zhàn)立, ++面向?qū)ο蟪绦蛟O(shè)計(jì)[M]. 人民郵電出版社,[8]　許家珆, —理論與實(shí)踐[J].北京:高等教育出版社,[9]　++程序設(shè)計(jì)簡明教程[M] .中國水利水電出版社,[10]　S M. Effective