中國數(shù)學(xué)建模-編程交流-組合算法概論

ID:43146833

大小:55.06 KB

頁數(shù):7頁

時間:2019-09-27

中國數(shù)學(xué)建模-編程交流-組合算法概論_第1頁
中國數(shù)學(xué)建模-編程交流-組合算法概論_第2頁
中國數(shù)學(xué)建模-編程交流-組合算法概論_第3頁
中國數(shù)學(xué)建模-編程交流-組合算法概論_第4頁
中國數(shù)學(xué)建模-編程交流-組合算法概論_第5頁
資源描述:

《中國數(shù)學(xué)建模-編程交流-組合算法概論》由會員上傳分享,免費在線閱讀,更多相關(guān)內(nèi)容在工程資料-天天文庫。

1、中國數(shù)學(xué)建模-編程交流-組合算法概論中國數(shù)學(xué)建模-編程交流-組合算法概論卜數(shù)學(xué)思想卜編程交流卜學(xué)術(shù)朵談

2、-EnglishFanswh-ee重登錄隱身用戶控制面板搜索風(fēng)格論壇狀態(tài)論壇展區(qū)社區(qū)服務(wù)社區(qū)休閑網(wǎng)站首頁退出?VC++,C,Perl,Asp...編程學(xué)習(xí),算法介紹.我的收件箱(0)屮國數(shù)學(xué)建模一學(xué)術(shù)區(qū)一編程交流一組合算法概論您是本帖的第623個閱讀者*貼子主題:組合算法概論b等級:職業(yè)俠客文章:470積分:956門派:黑客帝國注冊:2003-8-28鮮花⑴雞蛋(0)樓主組合算法概論組合算法概論(ABriefIntroductiontoComb

3、inatorialAlgorithm)組合算法是算法分析學(xué)當中非常重要的一個分支,關(guān)于它在計算機科學(xué)的地位我就不敖述了,下面為大家整理了整個材料,算法是我收集的,只是分門別類簡單介紹一下,然后把我的材料做了個整理,大家收藏吧,感覺挺有用的,費了我好長吋間和精力呀,我現(xiàn)在準備考研了,沒有太多吋間發(fā)很多經(jīng)典文章了,這片算是大部頭了。關(guān)于組合學(xué)問題的算法,計算對象是離散的、有限的數(shù)學(xué)結(jié)構(gòu)。從方法學(xué)的角度,組合算法包括算法設(shè)計和算法分析兩個方面。關(guān)于算法設(shè)計,歷史上已經(jīng)總結(jié)出了若干帶有普遍意義的方法和技術(shù),包括動態(tài)規(guī)劃、回溯法、分支限界法、分治法、貪心法

4、等。下面我們著重談?wù)剝簜€有代表性的組合算法:單純形法:這是一種線性規(guī)劃算法,由G.B.Dantzig在1947年提出,后來由他和其他的學(xué)者乂提出了單純形法的變形和改進。這些被實踐證明都是行之有效的,線性規(guī)劃研究線性目標函數(shù)在一組線性等式與線性不等式約束下的極值問題。這本來是連續(xù)問題,Dantzig發(fā)現(xiàn)線性規(guī)劃問題的可行解集(即滿足約束條件的點的全體)是一個超多面體。如果它的最優(yōu)解存在,那么這個最優(yōu)解一定可以在超多面體的一個頂點取到。由于超多面體的頂點只有有限個,從而使線性規(guī)劃成為?個組和優(yōu)化問題。單純形法是按照一定的規(guī)則,從可行解集的一個頂點轉(zhuǎn)移

5、到另一個頂點,使得目標函數(shù)的值不斷地得到改進,最后達到最優(yōu)。盡管單純形法一直使用得很好,但是在最壞情況下它需要指數(shù)運行吋間,從而使線性規(guī)劃問題是否屬于P類一度成為人們關(guān)心的問題。后來的橢球算法和投影算法都很好的解決了這個問題。排序和檢索:這兩部分應(yīng)當是大家比較熟悉的,所謂排序,就是將給定的元素序列按照某種順序關(guān)系重新排列成有序序列。例如將n個數(shù)組成的序列按照從小到大的順序重新排列;將n個英語單詞組成的的序列按照字典順序重新排列。所謂檢索,就是在給定的集合中查找某個特定的元素或是元素組。排序和檢索已經(jīng)成為計算機科學(xué)技術(shù)中最基本、使用最頻繁的算法。下

6、面我們專門談?wù)勁判蛩惴?sortingalgorithm)o在討論此種算法時,數(shù)據(jù)通常是指由若干記錄組成的文件,每個記錄包含一個或多個數(shù)據(jù)項,其中能夠標志該記錄的數(shù)據(jù)項稱為鍵碼。給定一文件的n個記錄{Rl,R2,…,Rn}及其相應(yīng)的鍵碼的集合{K1,K2,…,Kn}。所謂排序算法就是在數(shù)據(jù)處理中將文件中的記錄按鍵碼的一定次序要求排列起來的算法。若待排序的文件能夠同吋裝入計算機的主存中,整個排序過程不需要訪問外存便能完成,則稱此類排序問題為內(nèi)部排序;若參加排序的記錄數(shù)量很大,整個序列的排序過程不可能在內(nèi)存中完成,有一部分必須放在外存上,則稱此類排序

7、問題為外部排序。當待排序的文件中包含有一些相同鍵碼的記錄時,如果經(jīng)過排序后這些和同的鍵碼的記錄的相對次序仍然保持不變,則相應(yīng)的排序算法是穩(wěn)定的,否則為不穩(wěn)定的。如果排序算法設(shè)計成單處理機完成的,則此排序算法稱為串行(或順序)排序算法;如果排序算法時設(shè)計成多處理機實現(xiàn)的,則稱為并行排序算法。首先談?wù)剝?nèi)部排序:內(nèi)部排序的過程是一個逐步擴大記錄的有序序列長度的過程。在排序的過程中,參與排序的記錄序列中存在兩個區(qū)域:有序區(qū)和無序區(qū)。使有序區(qū)中記錄的數(shù)目增加一個或兒個的操作稱為一趟排序。逐步擴大記錄有序序列長度的方法大致有下列兒類:一.插入排序假設(shè)在排序過

8、程中,記錄序列R[l..n]的狀態(tài)為:則一趟直接插入排序的基本思想為:將記錄R插入到有序了序列R[l??i-l]中,使記錄的有序序列從R[l..i-1]變?yōu)镽[l?.i]。顯然,完成這個“插入”需分三步進行:1.查找R的插入位置j+1;2.將R[j+l??i-1]中的記錄后移一個位置;3.將R復(fù)制到R[j+1]的位置上。[叮直接插入排序利用順序查找實現(xiàn)“在R[l??iT]中查找R的插入位置”的插入排序。注意直接插入排序算法的三個要點:1.從R[i-U起向前進行順序查找,監(jiān)視哨設(shè)置在R[0];R[0]二R;//設(shè)置“哨兵”for(j=i-l;R[0

9、].key

當前文檔最多預(yù)覽五頁,下載文檔查看全文

此文檔下載收益歸作者所有

當前文檔最多預(yù)覽五頁,下載文檔查看全文
溫馨提示:
1. 部分包含數(shù)學(xué)公式或PPT動畫的文件,查看預(yù)覽時可能會顯示錯亂或異常,文件下載后無此問題,請放心下載。
2. 本文檔由用戶上傳,版權(quán)歸屬用戶,天天文庫負責(zé)整理代發(fā)布。如果您對本文檔版權(quán)有爭議請及時聯(lián)系客服。
3. 下載前請仔細閱讀文檔內(nèi)容,確認文檔內(nèi)容符合您的需求后進行下載,若出現(xiàn)內(nèi)容與標題不符可向本站投訴處理。
4. 下載文檔時可能由于網(wǎng)絡(luò)波動等原因無法下載或下載錯誤,付費完成后未能成功下載的用戶請聯(lián)系客服處理。
关闭