對(duì)樹的Wiener Index逆問(wèn)題的研究.pdf

1、組合化學(xué)是近十幾年逐漸發(fā)展并成熟起來(lái)的一門學(xué)科，它將化學(xué)合成、組合理論、計(jì)算機(jī)輔助設(shè)計(jì)融于一體，在短時(shí)間內(nèi)將不同構(gòu)建模塊經(jīng)過(guò)連接形成化合物庫(kù)，再對(duì)庫(kù)成分進(jìn)行篩選優(yōu)化，得到可能的有目標(biāo)功能的化合物結(jié)構(gòu)。通過(guò)計(jì)算機(jī)輔助設(shè)計(jì)可以極大提高庫(kù)的組成并同時(shí)控制庫(kù)的大小，因而計(jì)算機(jī)技術(shù)正在組合化學(xué)中發(fā)揮著越來(lái)越大的作用。 經(jīng)過(guò)長(zhǎng)期的研究，科學(xué)家們發(fā)現(xiàn)很多化合物的物理性質(zhì)和化學(xué)性質(zhì)與它們的拓?fù)湫再|(zhì)密切相關(guān)。WienerIndex就是一個(gè)與化合物

2、的物理化學(xué)性質(zhì)密切相關(guān)的拓?fù)湎禂?shù)，它的性質(zhì)已經(jīng)被廣泛應(yīng)用于組合化學(xué)領(lǐng)域中。樹的WienerIndex逆問(wèn)題是組合化學(xué)中的一個(gè)重要問(wèn)題，Goldman于2000年提出的動(dòng)態(tài)規(guī)劃算法雖然理論上可以解決此問(wèn)題，但是算法的計(jì)算量很大，程序復(fù)雜性和運(yùn)行速度方面也不太理想。 本文首先對(duì)樹的WienerIndex和其它一些拓?fù)湎禂?shù)的關(guān)系進(jìn)行了分析，并進(jìn)一步利用這種關(guān)系對(duì)原算法進(jìn)行了改進(jìn)，極大地減小了原算法的搜索空間和遞歸次數(shù)；在此算法基礎(chǔ)上本