| ******************************************************************
我也來(lái)冒充一回高手，談?wù)剬W(xué)習計算機的一點(diǎn)個(gè)人體會(huì )。由于我是做理論的，所以先著(zhù)重談?wù)劺碚摗?/p> 記得當年大一，剛上本科的時(shí)候，每周六課時(shí)數學(xué)分析，六課時(shí)高等代數，天天作業(yè)不斷(那時(shí)是六日工作制)。頗有些同學(xué)驚呼走錯了門(mén):咱們這到底念的是什么系？不錯，你沒(méi)走錯門(mén)，這就是(當時(shí)的)南大計算機系。系里的傳統是培養做學(xué)術(shù)研究，尤其是理論研究的人。而計算機的理論研究，說(shuō)到底了就是數學(xué)，雖然也許是正統數學(xué)家眼里非主流的數學(xué)。 數學(xué)分析這個(gè)東東，咱們學(xué)計算機的人對它有很復雜的感情。愛(ài)它在于它是第一門(mén)，也是學(xué)分最多的一門(mén)數學(xué)課，又長(cháng)期為考研課程--94以前可以選考數學(xué)分析與高等代數，以后則并軌到著(zhù)名的所謂“工科數學(xué)一”。其重要性可見(jiàn)一斑。恨它則在于它好象難得有用到的機會(huì )，而且思維跟咱們平常做的這些離散/有限的工作截然不同。當年出現的怪現象是：計算機系學(xué)生的高中數學(xué)基礎在全校數一數二(希望沒(méi)有冒犯其它系的同學(xué))，教學(xué)課時(shí)數也僅次于數學(xué)系，但學(xué)完之后的效果卻幾乎是倒數第一。其中原因何在，發(fā)人深思。 我個(gè)人的淺見(jiàn)是：計算機類(lèi)的學(xué)生，對數學(xué)的要求固然跟數學(xué)系不同，跟物理類(lèi)差別則更大。通常非數學(xué)專(zhuān)業(yè)的所謂“高等數學(xué)”，無(wú)非是把數學(xué)分析中較困難的理論部分刪去，強調套用公式計算而已。而對計算機系來(lái)說(shuō)，數學(xué)分析里用處最大的恰恰是被刪去的理論部分。說(shuō)得難聽(tīng)一點(diǎn)，對計算機系學(xué)生而言，追求算來(lái)算去的所謂“工科數學(xué)一”已經(jīng)徹底地走進(jìn)了魔道。記上一堆曲面積分的公式，難道就能算懂了數學(xué)分析？ 中文的數學(xué)分析書(shū)，一般都認為以北大張筑生老師的“數學(xué)分析新講”為最好。我個(gè)人認為南大數學(xué)系的“數學(xué)分析教程”也還不錯，至少屬于典型的南大風(fēng)格，咱們看著(zhù)親切。隨便學(xué)通哪一本都行。萬(wàn)一你的數學(xué)實(shí)在太好，這兩本書(shū)都吃不飽，那就去看菲赫金哥爾茨的“微積分學(xué)教程”好了--但我認為沒(méi)什么必要，畢竟你不想轉到數學(xué)系去。 吉米多維奇的“數學(xué)分析習題集”也基本上是計算型的東東。如果你打算去考那個(gè)什么“工科數學(xué)一”，可以做一做。否則，不做也罷。 中國的所謂高等代數，就等于線(xiàn)性代數加上一點(diǎn)多項式理論。我以為這有好的一面，因為可以讓學(xué)生較早感覺(jué)到代數是一種結構，而非一堆矩陣翻來(lái)覆去。當年我們用林成森，盛松柏兩位老師編的“高等代數”，感覺(jué)相當舒服，我直到現在還保留著(zhù)教材。此書(shū)相當全面地包含了關(guān)于多項式和線(xiàn)性代數的基本初等結果，同時(shí)還提供了一些有用的比較深的內容，如Sturm序列，Shermon-Morrison公式，廣義逆矩陣等等?？梢哉f(shuō)，作為本科生如能吃透此書(shū)，就可以算高手。后來(lái)它得以在南大出版社出版，可惜好象并軌以后就沒(méi)有再用了。 國內較好的高等代數教材還有清華計算機系用的那本，清華出版社出版，書(shū)店里多多，一看就知道。特點(diǎn)嘛，跟南大那本差不太多。 但以上兩本書(shū)也不能說(shuō)完美無(wú)缺。從抽象代數的觀(guān)點(diǎn)來(lái)看，高等代數里的結果不過(guò)是代數系統性質(zhì)的一些例子而已。莫宗堅先生的“代數學(xué)”里，對此進(jìn)行了深刻的討論。然而莫先生的書(shū)實(shí)在深得很，作為本科生恐怕難以接受，不妨等到自己以后成熟了一些再讀。 概率論與數理統計這門(mén)課很重要，可惜少了些東西。 少了的東西是隨機過(guò)程。到畢業(yè)還沒(méi)有聽(tīng)說(shuō)過(guò)Markov過(guò)程，此乃計算機系學(xué)生的恥辱。沒(méi)有隨機過(guò)程，你怎么分析網(wǎng)絡(luò )和分布式系統？怎么設計隨機化算法和協(xié)議？據說(shuō)清華計算機系開(kāi)有“隨機數學(xué)”，早就是必修課。人家可是工科學(xué)校，作為自以為“理科計算機系”出身的人，我感到慚愧。 另外，離散概率對計算機系學(xué)生來(lái)說(shuō)有特殊的重要性?，F在，美國已經(jīng)有些學(xué)校開(kāi)設了單純的“離散概率論”課程，干脆把連續概率刪去，把離散概率講深些。我們不一定要這么做，但應該更加強調離散概率是沒(méi)有疑問(wèn)的。 計算方法是最后一門(mén)由數學(xué)系給我們開(kāi)的課。一般學(xué)生對這門(mén)課的重視程度有限，以為沒(méi)什么用。其實(shí)，做圖形圖像可離不開(kāi)它。而且，在很多科學(xué)工程中的應用計算，都以數值的為主。 這門(mén)課有兩個(gè)極端的講法：一個(gè)是古典的“數值分析”，完全講數學(xué)原理和算法；另一個(gè)是現在日趨流行的“科學(xué)與工程計算”，干脆教學(xué)生用軟件包編程。南大數學(xué)系的幾位老師做了件大好事，把前者的一本極為經(jīng)典的教材翻譯出版了：德國Stoer的“數值分析引論”。如果你能學(xué)會(huì )此書(shū)中最淺顯的三分之一，就算沒(méi)有白上過(guò)計算方法這門(mén)課！而后一種講法似乎國內還沒(méi)有跟上潮流？不過(guò)，只要你有機會(huì )在自己的電腦上裝個(gè)matlab之類(lèi)，完全可以無(wú)師自通。 本系里，通常開(kāi)一門(mén)離散數學(xué)，包括集合論，圖論，和抽象代數，另外再單開(kāi)一門(mén)數理邏輯。這樣安排，主要由于南大的邏輯傳統：系里很多老師都算莫先生的門(mén)人，就連孫先生都是邏輯專(zhuān)業(yè)出身(見(jiàn)孫先生自述)。 不過(guò)，這么多內容擠在離散數學(xué)一門(mén)課里，是否時(shí)間太緊了點(diǎn)？另外，計算機系學(xué)生不懂組合和數論，也是巨大的缺陷。要做理論，不懂組合或者數論吃虧可就太大了。 從理想的狀態(tài)來(lái)看，最好分開(kāi)六門(mén)課：集合，邏輯,圖論，組合，代數，數論。這個(gè)當然不現實(shí)，因為沒(méi)那么多課時(shí)。也許將來(lái)可以開(kāi)三門(mén)課：集合與邏輯，圖論與組合，代數與數論。 不管課怎么開(kāi)，學(xué)生總一樣要學(xué)。下面分別談?wù)勆厦娴娜M內容。 古典集合論，北師大出過(guò)一本“基礎集合論”不錯。南大出版朱梧(木賈)老師的“集合論導引”也許觀(guān)點(diǎn)更高些，但他的書(shū)形式化得太厲害，念起來(lái)吃力。 數理邏輯，莫先生的書(shū)自然是經(jīng)典。然而我們也不得不承認，此書(shū)年代久遠，光讀它恐怕不夠。尤其是命題/謂詞演算本身有好多種不同的講法，多看幾家能大大開(kāi)闊自己的視野。例如陸鐘萬(wàn)老師的“面向計算機科學(xué)的數理邏輯”就不錯。朱老師也著(zhù)有“數理邏輯教程”一書(shū)，但也同樣讀起來(lái)費力些。 總的來(lái)說(shuō)，學(xué)集合/邏輯起手不難，但越往后越感覺(jué)深不可測。建議有興趣的同學(xué)讀讀朱老師的“數學(xué)基礎引論”--此書(shū)有點(diǎn)時(shí)間簡(jiǎn)史的風(fēng)格，講到精彩處，所謂“天花亂墜，妙雨繽紛”，令人目不暇接。讀完以后，你對這些數學(xué)/哲學(xué)中最根本的問(wèn)題有了個(gè)大概了解，也知道了山有多高，海有多深。 學(xué)完以上各書(shū)之后，如果你還有精力興趣進(jìn)一步深究，那么可以試一下GTM系列中的"Introduction to Axiomatic Set Theory"和"A Course of Mathematical Logic"。這兩本都有世界圖書(shū)的引進(jìn)版。你如果能搞定這兩本，可以說(shuō)在邏輯方面真正入了門(mén)，也就不用再浪費時(shí)間聽(tīng)我瞎侃了。：) 據說(shuō)全中國最多只有三十個(gè)人懂圖論(當年上課時(shí)陳道蓄老師轉引張克民老師的話(huà))。此言不虛。圖論這東東，技巧性太強，幾乎每題都有一個(gè)獨特的方法，讓人頭痛。不過(guò)這也正是它魅力所在：只要你有創(chuàng )造性，它就能給你成就感。所以學(xué)圖論沒(méi)什么好說(shuō)的，做題吧。 國內的圖論書(shū)中，王樹(shù)禾老師的“圖論及其算法”非常成功。一方面，其內容在國內教材里算非常全面的。另一方面，其對算法的強調非常適合計算機系(本來(lái)就是科大計算機系教材)。有了這本書(shū)為主，再參考幾本翻譯的，如Bondy&Murty的“圖論及其應用”，郵電出版社翻譯的“圖論和電路網(wǎng)絡(luò )”等等，就馬馬虎虎，對本科生足夠了。 再進(jìn)一步，世界圖書(shū)引進(jìn)有GTM系列的"ModernGraph Theory"。此書(shū)確實(shí)經(jīng)典！國內好象還有一家出版了個(gè)翻譯版。不過(guò)，學(xué)到這個(gè)層次，還是讀原版好。搞定這本書(shū)，也標志著(zhù)圖論入了門(mén)，呵呵。組合感覺(jué)沒(méi)有太適合的國產(chǎn)書(shū)。還是讀Graham和Knuth 等人合著(zhù)的經(jīng)典“具體數學(xué)”吧，有翻譯版，西電出的。 抽象代數，國內經(jīng)典為莫宗堅先生的“代數學(xué)”。此書(shū)是北大數學(xué)系教材，深得好評。然而對本科生來(lái)說(shuō)，此書(shū)未免太深?？梢韵葘W(xué)習一些其它的教材，然后再回頭來(lái)看“代數學(xué)”。國際上的經(jīng)典可就多了，GTM系列里就有一大堆。推薦一本談不上經(jīng)典，但卻最簡(jiǎn)單的，最容易學(xué)的： http://www.math.miami.edu/~ec/book/ 這本“Introduction to Linear and Abstract Algebra"非常通俗易懂，而且把抽象代數和線(xiàn)性代數結合起來(lái)，對初學(xué)者來(lái)說(shuō)非常理想。不過(guò)請注意版權問(wèn)題，不要違反法律噢。 數論方面，國內有經(jīng)典而且以困難著(zhù)稱(chēng)的”初等數論“(潘氏兄弟著(zhù)，北大版)。再追溯一點(diǎn)，還有更加經(jīng)典(可以算世界級)并且更加困難的”數論導引“(華羅庚先生的名著(zhù)，科學(xué)版，九章書(shū)店重印)。把基礎的幾章搞定一個(gè)大概，對本科生來(lái)講足夠了。但這只是初等數論。本科畢業(yè)后要學(xué)計算數論，你必須看英文的書(shū)，如Bach的"Introduction to Algorithmic Number Theory"。理論計算機的根本，在于算法?，F在系里給本科生 開(kāi)設算法設計與分析，確實(shí)非常正確。環(huán)顧西方世界，大約沒(méi)有一個(gè)三流以上計算機系不把算法作為必修的。 算法教材目前公認以Corman等著(zhù)的"Introduction to Algorithms"為最優(yōu)。對入門(mén)而言，這一本已經(jīng)足夠，不需要再參考其它書(shū)。南大曾翻譯出版此書(shū)，中文名為”現代計算機常用數據結構與算法“。pie好象提供了網(wǎng)上課程的link，我也就不用廢話(huà)。 最后說(shuō)說(shuō)形式語(yǔ)言與自動(dòng)機。我們用過(guò)北郵的教材，應該說(shuō)寫(xiě)的還清楚。但是，有一點(diǎn)要強調：形式語(yǔ)言和自動(dòng)機的作用主要在作為計算模型，而不是用來(lái)做編譯。事實(shí)上，編譯前端已經(jīng)是死領(lǐng)域，沒(méi)有任何open problem。如果為了這個(gè)，我們完全沒(méi)必要去學(xué)形式語(yǔ)言--用用yacc什么的就完了。北郵的那本，在深度上，在跟可計算性的聯(lián)系上都有較大的局限，現代感也不足。所以建議有興趣的同學(xué)去讀英文書(shū)......不過(guò)英文書(shū)中好的也不多，而且國內似乎沒(méi)引進(jìn)這方面的教材。 入門(mén)以后，把形式語(yǔ)言與自動(dòng)機中定義的模型，和數理邏輯中用遞歸函數定義的模型比較一番，可以說(shuō)非常有趣?，F在才知道，什么叫”宮室之美，百官之富“！
胡侃學(xué)習計算機--理論之外
我上大學(xué)的時(shí)候，第一門(mén)專(zhuān)業(yè)課時(shí)程序設計，現在好象改成了計算機科學(xué)導論？不管叫什么名字，總之，念計算機的人就是靠程序吃飯。 去年在計算機系版有過(guò)一場(chǎng)爭論，關(guān)于第一程序設計語(yǔ)言該用哪一種。我個(gè)人認為，用哪種語(yǔ)言屬于末節，關(guān)鍵在養成良好的編程習慣。當年老師對我們說(shuō)，打好基礎后學(xué)一門(mén)新語(yǔ)言只要一個(gè)星期?，F在我覺(jué)得根本不用一個(gè)星期--前提是先把基礎打好。 數據結構有兩種不同的上法：一種把它當成降低要求的初級算法課，另一種把它當成高級的程序設計課?，F在國內的課程好象介乎兩者之間，而稍偏向前者。我個(gè)人認為，假如已經(jīng)另有必修的算法課，恐怕后一個(gè)目的更重要些。 國內流行的數據結構書(shū)也有兩種：北大的紅皮書(shū)(許卓群等著(zhù)，高教版)和清華的綠皮書(shū)(嚴蔚敏等著(zhù)，清華版)。兩書(shū)差距不大。紅皮書(shū)在理論上稍深一些，當然離嚴格的算法書(shū)還差好遠。綠皮書(shū)更易接受些，而且佩有一本不錯的習題集，但我覺(jué)得它讓學(xué)生用偽代碼寫(xiě)作業(yè)恐怕不見(jiàn)得太好。最好還是把算法都code以后debug一番，才能鍛煉編程能力。 匯編預言和微機原理是兩門(mén)特煩人的課。你的數學(xué)/理論基礎再好，也占不到什么便宜。這兩門(mén)課之間的次序也好比先有雞還是先有蛋，無(wú)論你先學(xué)哪門(mén)，都會(huì )牽扯另一門(mén)課里的東西。所以，只能靜下來(lái)慢慢琢磨。這就是典型的工程課，不需要太多的聰明和頓悟，卻需要水滴石穿的漸悟。 有關(guān)這兩門(mén)課的書(shū)，電腦書(shū)店里不難找到。弄幾本最新的，對照著(zhù)看吧。 模擬電路這東東，如今不僅計算機系學(xué)生搞不定，電子系學(xué)生也多半害怕。如果你真想軟硬件通吃，那么建議你先看看邱關(guān)源的“電路原理”，也許此后再看模擬電路底氣會(huì )足些。 教材：康華光的“電子技術(shù)基礎”還是不錯的。有興趣也可以參考童詩(shī)白的書(shū)。 數字電路比模擬電路要好懂得多。閻石的書(shū)也算一本好教材，遺憾的一點(diǎn)是集成電路講少了些。真有興趣，到東南無(wú)線(xiàn)電系去旁聽(tīng)他們的課。 計算機系統結構該怎么教，國際上還在爭論。國內能找到的較好教材為Stallings的"Computer Organization and Architecture:Designing for Performance"(清華影印本)。國際上最流行的則是“Computer architecture: a quantitative approach", by Patterson & Hennessy。 操作系統可以隨便選用Tanenbaum的"Operating System Design and Implementation"和"Modern Operating System" 兩書(shū)之一。這兩部都可以算經(jīng)典，唯一缺點(diǎn) 就是理論上不夠嚴格。不過(guò)這領(lǐng)域屬于Hardcore System, 所以在理論上馬虎一點(diǎn)也情有可原。 如果先把形式語(yǔ)言學(xué)好了，則編譯原理中的前端我看只要學(xué)四個(gè)算法：最容易實(shí)現的遞歸下降；最好的自頂向下算法LL(k)；最好的自底向上算法LR(k)；LR(1)的簡(jiǎn)化SLR(也許還有另一簡(jiǎn)化LALR?)。后端完全屬于工程性質(zhì)，自然又是another story。
學(xué)數據庫的第一意義是告訴你，會(huì )用VFP編程不等于懂數據庫。(這世界上自以為懂數據庫的人太多了！)數據庫設計既是科學(xué)又是藝術(shù)，數據庫實(shí)現則是典型的工程。 所以從某種意義上講，數據庫是最典型的一門(mén)計算機課--理工結合，互相滲透。 推薦教材：Silberschatz, et al., "Database System Concepts". 必須結束這篇“胡侃”了，再侃下去非我力所能及。其實(shí)計算機還有很多基礎課都值得一侃，如程序設計語(yǔ)言原理，圖形圖像處理，人工智能等等。怎奈我造詣?dòng)邢?，不敢再讓內行恥笑。 最后聲明：前后的兩篇“胡侃”只針對本科階段的學(xué)習。即使把這些全弄通了，前面的路還長(cháng)......
計算機科學(xué)和數學(xué)的關(guān)系有點(diǎn)奇怪。二三十年以前，計算機科學(xué)基本上還是數學(xué)的一個(gè)分支。而現在，計算機科學(xué)擁有廣泛的研究領(lǐng)域和眾多的研究人員，在很多方面反過(guò)來(lái)推動(dòng)數學(xué)發(fā)展，從某種意義上可以說(shuō)是孩子長(cháng)得比媽媽還高了。 但不管怎么樣，這個(gè)孩子身上始終流著(zhù)母親的血液。這血液是the mathematical underpinning of computer science(計算機科學(xué)的數學(xué)基礎)，-- 也就是理論計算機科學(xué)。 現代計算機科學(xué)和數學(xué)的另一個(gè)交叉是計算數學(xué)/數值分析/科學(xué)計算，傳統上不包含在理論計算機科學(xué)以?xún)?。所以本文對計算數學(xué)全部予以忽略。 最常和理論計算機科學(xué)放在一起的一個(gè)詞是什么？ 答：離散數學(xué)。這兩者的關(guān)系是如此密切，以至于它們在不少場(chǎng)合下成為同義詞。 傳統上，數學(xué)是以分析為中心的。數學(xué)系的同學(xué)要學(xué)習三四個(gè)學(xué)期的數學(xué)分析，然后是復變，實(shí)變，泛函等等。實(shí)變和泛函被很多人認為是現代數學(xué)的入門(mén)。在物理，化學(xué)，工程上應用的，也以分析為主。 隨著(zhù)計算機科學(xué)的出現，一些以前不太受到重視的數學(xué)分支突然重要起來(lái)。人們發(fā)現，這些分支處理的數學(xué)對象與傳統的分析有明顯的區別：分析研究的對象是連續的，因而微分，積分成為基本的運算；而這些分支研究的對象是離散的，因而很少有機會(huì )進(jìn)行此類(lèi)的計算。人們從而稱(chēng)這些分支為“離散數學(xué)”。“離散數學(xué)”的名字越來(lái)越響亮，最后導致以分析為中心的傳統數學(xué)分支被相對稱(chēng)為“連續數學(xué)”。 離散數學(xué)經(jīng)過(guò)幾十年發(fā)展，基本上穩定下來(lái)。一般認為，離散數學(xué)包含以下學(xué)科： 但是，理論計算機科學(xué)僅僅就是在數學(xué)的上面加上“離散”的帽子這么簡(jiǎn)單嗎？一直到大約十幾年前，終于有一位大師告訴我們：不是。 D.E.Knuth(他有多偉大，我想不用我廢話(huà)了)在Stanford開(kāi)設了一門(mén)全新的課程Concrete Mathematics。 Concrete這個(gè)詞在這里有兩層含義： 第一，針對abstract而言。Knuth認為，傳統數學(xué)研究的對象過(guò)于抽象，導致對具體的問(wèn)題關(guān)心不夠。他抱怨說(shuō)，在研究中他需要的數學(xué)往往并不存在，所以他只能自己去創(chuàng )造一些數學(xué)。為了直接面向應用的需要，他要提倡“具體”的數學(xué)。 在這里我做一點(diǎn)簡(jiǎn)單的解釋。例如在集合論中，數學(xué)家關(guān)心的都是最根本的問(wèn)題--公理系統的各種性質(zhì)之類(lèi)。而一些具體集合的性質(zhì)，各種常見(jiàn)集合，關(guān)系，映射都是什么樣的，數學(xué)家覺(jué)得并不重要。然而，在計算機科學(xué)中應用的，恰恰就是這些具體的東西。Knuth能夠首先看到這一點(diǎn)，不愧為當世計算機第一人。 第二，Concrete是Continuous(連續)加上discrete (離散)。不管連續數學(xué)還是離散數學(xué)，都是有用的數學(xué)！ 前面主要是從數學(xué)角度來(lái)看的。從計算機角度來(lái)看，理論計算機科學(xué)目前主要的研究領(lǐng)域包括：可計算性理論，算法設計與復雜性分析，密碼學(xué)與信息安全，分布式計算理論，并行計算理論，網(wǎng)絡(luò )理論，生物信息計算，計算幾何學(xué)，程序語(yǔ)言理論等等。這些領(lǐng)域互相交叉，而且新的課題在不斷提出，所以很難理出一個(gè)頭緒來(lái)。下面隨便舉一些例子。 由于應用需求的推動(dòng)，密碼學(xué)現在成為研究的熱點(diǎn)。密碼學(xué)建立在數論(尤其是計算數論)，代數，信息論，概率論和隨機過(guò)程的基礎上，有時(shí)也用到圖論和組合學(xué)等。 很多人以為密碼學(xué)就是加密解密，而加密就是用一個(gè)函數把數據打亂。這就大錯特錯了?，F代密碼學(xué)至少包含以下層次的內容： 第一，密碼學(xué)的基礎。例如，分解一個(gè)大數真的很困難嗎？能否有一般的工具證明協(xié)議正確？ 在分布式系統中，也有很多重要的理論問(wèn)題。例如，進(jìn)程之間的同步，互斥協(xié)議。一個(gè)經(jīng)典的結果是：在通信信道不可靠時(shí)，沒(méi)有確定型算法能實(shí)現進(jìn)程間協(xié)同。所以，改進(jìn)TCP三次握手幾乎沒(méi)有意義。例如時(shí)序問(wèn)題。常用的一種序是因果序，但因果序直到不久前才有一個(gè)理論上的結果.... 例如，死鎖沒(méi)有實(shí)用的方法能完美地對付。 例如,...... |
| 工作中總是牽扯到一些大規模的狀態(tài)搜索，路經(jīng)搜索的問(wèn)題，個(gè)人也對這方面的問(wèn)題比較感興趣。在這一 類(lèi)問(wèn)題上，現代計算機的能力真的太弱了，照這種模式發(fā)展下去，不知道什么時(shí)候才能出現真正的人工智 能。 這種問(wèn)題的。對于這類(lèi)問(wèn)題，存在這種說(shuō)法：世界上任何一臺計算能力不是太差的計算機，計算能力都是 相同的?；蛘哒f(shuō)，存在很多簡(jiǎn)單的計算問(wèn)題，世界上任何計算機都無(wú)法求解?，F代超級計算機的計算能力 大概是10^15左右，個(gè)人計算機大概是10^8，但很多問(wèn)題的狀態(tài)空間輕而易舉地就能達到10的幾十次方的 規模，這對任何計算機都是無(wú)法完成的天文數字。 舉一個(gè)小游戲的例子，對于8數碼（3*3的棋盤(pán)）問(wèn)題，總共的狀態(tài)空間數目為9!=362880,這個(gè)規模計算機 還是很容易求解的，對于4*4棋盤(pán)的15數碼問(wèn)題，狀態(tài)空間數目就激增至15!=1307674368000,已經(jīng)夠考驗 一臺計算機的能力了，而對于5*5的24數碼問(wèn)題，24!=620448401733239439360000,超級計算機計算起來(lái)都 會(huì )很困難,再高的就不用說(shuō)了。 另一個(gè)考驗計算機搜索能力的小游戲是幻方，單純的求解一個(gè)n階幻方的時(shí)間復雜度是O((n^2)!)。稍大一 點(diǎn)的n馬上就會(huì )導致巨大的計算量。由于某些幻方的解空間也比較大，因而采取某些演化搜索算法能夠在 較短的時(shí)間內得到可行的結果。比如對于普通幻方，采用模擬退火，可以在幾秒鐘之內得到幾十階的結果 。然而對于限制條件更加苛刻的幻方，就不容易得到了，對稱(chēng)幻方我目前只能搜索到n=8（下一個(gè)就是 n=12），完美幻方只能搜索到n=7。很多人通過(guò)手工分析，然后最多寫(xiě)一個(gè)小程序，能夠得到更高階的結 果，然而這不屬于人工智能的范圍，并且具有很大的偶然性。（人腦有時(shí)能夠構造出很高階的特殊幻方（ 幾十上百階），但卻難于構造中低階的特殊幻方（十幾階的），這也是人的構造性方法的缺陷。） 上面的兩個(gè)問(wèn)題都是小游戲，解決不了也就罷了，玩玩而已。但實(shí)際工程中確實(shí)存在很多類(lèi)似的大規模搜 索問(wèn)題。 費用最小的路徑）?這個(gè)問(wèn)題不難解決，用廣度優(yōu)先搜索或dijkstra算法就可以完成了，也可以考慮A*算 法，最多遍歷所有的圖節點(diǎn)。 和線(xiàn)不相交兩種方式）。這個(gè)問(wèn)題就異常復雜了，當圖結點(diǎn)有幾十萬(wàn)，(si,ti)有上千對的時(shí)候，搜索規 模遠不止10的幾十幾百次方。 ，連線(xiàn)也是有寬度的，且不能相交。如果采用劃分網(wǎng)格的方法，則生成的圖結點(diǎn)數目很大；如果采用自適 應的網(wǎng)格劃分方法，則很難避免搜索過(guò)程中兩條線(xiàn)不相交，且不好找合適的啟發(fā)搜索方法。 時(shí)候都采用了非常原始的方法。 即使計算機運算能力再增一億億億倍，能解決這些問(wèn)題嗎? |
聯(lián)系客服
