組合學(xué)問題在生活中隨處可見

1、什么是組合數(shù)學(xué)組合學(xué)問題在生活中隨處可見。例如，計算世界 杯比賽場次。在玩撲克牌游戲中，計算滿堂紅 (full house牌的手?jǐn)?shù)，以確定出現(xiàn)一手滿堂紅牌的幾率。 所有這些都是組合學(xué)問題。正如人們想到的，組合數(shù) 學(xué)的歷史淵源扎根于數(shù)學(xué)娛樂和游戲之中。過去研究 過的許多問題，不論出于消遣還是出于對其美學(xué)的考 慮，如今在純科學(xué)和應(yīng)用科學(xué)中都具有高度的重要性。 今天，組合數(shù)學(xué)是數(shù)學(xué)的一門重要分支，而且它的影 響還在繼續(xù)擴(kuò)大。 組合數(shù)學(xué)自 60 年代以來急速發(fā)展的 部分原因就在于計算機(jī)在我們的社會中所發(fā)揮的重要 影響，而且這種影響還在繼續(xù)發(fā)揮。由于運算速度的 持續(xù)增加，計算機(jī)已經(jīng)能夠解決大型問題，這在

2、以前 是不可能做到的。然而計算機(jī)不能獨立遠(yuǎn)行，它需要 編程來控制。這些程序的基礎(chǔ)往往是求解問題的組合 學(xué)算法。對于這些算法，運行時間效率和存儲需求分 析需要更多的組合學(xué)思想。組合數(shù)學(xué)近期發(fā)展的另一個原因是它對于那些過 去很少與數(shù)學(xué)正式接觸的學(xué)科的適用性。由此我們發(fā) 現(xiàn)，組合數(shù)學(xué)的思想和技巧不僅正在用于數(shù)學(xué)應(yīng)用的 傳統(tǒng)自然科學(xué)領(lǐng)域， 而且也用于社會科學(xué)、 生物科學(xué)、 信息論等領(lǐng)域。此外，組合數(shù)學(xué)和組合學(xué)思想在許多 數(shù)學(xué)分支中已經(jīng)變得越來越重要。組合數(shù)學(xué)一般講可以分存在性問題、計數(shù)問題、 構(gòu)造性算法、最優(yōu)化問題四個方面。一、存在性問題 工程實際或科學(xué)研究提出各種問題，有些可以判 定其有解或無解，但

3、也有不少難以判定。如一個國際 象棋盤，8 行 8行共 64個黑白相間的正方形棋盤，如 任意挖去一個黑格一個白格，問可否用1X2格的骨牌 蓋滿這 62 格的殘盤？這不是不假思索就可判定的問 題。二、計數(shù)問題 如一個組合問題的解已知是存在的，自然會問有多少不同的解。三、構(gòu)造性算法 這一部分發(fā)展很迅速。一個組合問題，已判知解存在，甚至也可以計算推知有幾組解，但關(guān)鍵還在于 把解構(gòu)造出來，有的哪怕給出一種解也好。如求圖的 最大邊匹配算法，旅行售貨員問題近似求解算法等。 這一部分主要研究如何從組合論角度設(shè)計算法，使之 較好地構(gòu)造出解。四、優(yōu)化問題一個問題的構(gòu)造性算法可能不止一種，自然面臨 如何擇優(yōu)，如何改進(jìn)。結(jié)合電子計算機(jī)看，主要是獨 立于計算機(jī)硬設(shè)備而改進(jìn)算法本身的時間復(fù)雜性和空 間復(fù)雜性，使問題的