對(duì)組合化學(xué)中Wiener索引逆問題的研究.pdf

1、組合化學(xué)是一門應(yīng)用在藥物分子設(shè)計(jì)和分子識(shí)別中的新興的重要的技術(shù)。它是一種實(shí)驗(yàn)室的方法，目的是通過“大規(guī)模并行”篩選化合物庫以發(fā)現(xiàn)具有某種生物活性的化合物。這種方法的應(yīng)用主要是基于實(shí)驗(yàn)設(shè)計(jì)和計(jì)算數(shù)學(xué)模型的交互。 藥物和其它化合物可以用多邊形模型表示，其中各頂點(diǎn)表示分子的一個(gè)原子，而原子間的共價(jià)聯(lián)系則用邊表示。這種由化合物的分子得到的多邊形我們稱為分子圖，這個(gè)多邊形可以是一條路、一棵樹或者一個(gè)普通的圖。定義在這個(gè)圖上的指標(biāo)-Wien

2、er索引，是一個(gè)與化合物的物理化學(xué)性質(zhì)密切相關(guān)的拓?fù)湎禂?shù)。前面對(duì)Wiener索引已經(jīng)作了大量的工作，以前對(duì)Wiener索引的研究主要分為兩種類型：圖的Wiener索引問題以及Wiener索引逆問題。 Wiener索引逆問題指：給定一個(gè)整數(shù)n，是否存在一棵樹T，使得W(T)=n，以及如何計(jì)算更有效率。Wiener索引猜想指：除了有限的集合外，所有的正整數(shù)都是某一棵樹的Wiener索引值。這個(gè)猜想至今沒有得到證明，但是研究該問題的理

3、論不斷得到簡(jiǎn)化。2000年，Goldman et al借助于索引值之間的遞歸聯(lián)系，提出了一個(gè)從較小的子樹構(gòu)造樹的動(dòng)態(tài)規(guī)劃算法。該算法雖然可以在理論上解決此問題，但是算法的計(jì)算量很大，程序復(fù)雜性和運(yùn)行速度也不太理想。 本文首先對(duì)樹的Wiener索引和其它一些拓?fù)渌饕年P(guān)系進(jìn)行了分析，并進(jìn)一步利用這種關(guān)系對(duì)原算法進(jìn)行了改進(jìn)，極大地減小了原算法的搜索空間和遞歸次數(shù)。然后，又對(duì)上述猜想作了進(jìn)一步的研究：通過設(shè)計(jì)更有效的算法來證明上述猜想

4、。以前的研究都側(cè)重于通過枚舉所有可能的樹來證明該猜想，本文通過設(shè)計(jì)一種新的數(shù)據(jù)類型一樹族，在這種數(shù)據(jù)類型中來證明上述猜想就已足夠。 本文圍繞樹的Wiener索引逆問題展開深入的研究，主要成果如下： 1)對(duì)Goldman提出的算法進(jìn)行了改進(jìn)，通過比較得出，改進(jìn)后的算法在搜索空間和遞歸次數(shù)方面都明顯優(yōu)于原算法，并且給出了新算法和原算法在遞歸調(diào)用次數(shù)上的實(shí)驗(yàn)對(duì)比結(jié)果； 2)提出了一種新的數(shù)據(jù)結(jié)構(gòu)-樹族，比較系統(tǒng)的分析了