漢諾塔圖性質(zhì)研究.pdf

1、漢諾塔問題是一個(gè)古老的問題。根據(jù)漢諾塔問題，我們可以構(gòu)造一類分形網(wǎng)絡(luò):漢諾塔圖。自從漢諾塔圖提出以來，許多學(xué)者從不同角度對(duì)漢諾塔圖進(jìn)行了研究，例如最短距離，平均距離，平面性，擴(kuò)散問題，哈密爾頓回路等。然而，一些重要的問題，例如漢諾塔圖生成樹的數(shù)目，隨機(jī)游走問題，一致性問題等，依舊是相關(guān)研究領(lǐng)域的空白，而這些問題無論在理論上和實(shí)際應(yīng)用中，都有重要意義。本論文主要在三個(gè)方面研究漢諾塔圖，即生成樹數(shù)目，隨機(jī)游走問題和一致性問題。
　　生

2、成樹數(shù)目與網(wǎng)絡(luò)的諸多拓?fù)浜蛣?dòng)力學(xué)性質(zhì)密切相關(guān)，例如網(wǎng)絡(luò)穩(wěn)定性，同步性能，通信效率等等。然而，求解大規(guī)模網(wǎng)絡(luò)的生成樹數(shù)目依然缺乏高效的算法。本論文中，我們用枚舉的方法，求解了二維和三維漢諾塔圖生成樹的數(shù)目，并給出了解析結(jié)果。
　　分形上的隨機(jī)游走問題在眾多領(lǐng)域都有重要應(yīng)用。本論文中我們研究d維漢諾塔圖上的隨機(jī)游走問題。借助于漢諾塔圖的自相似結(jié)構(gòu)，我們可以精確地求解隨機(jī)游走相關(guān)的幾個(gè)重要的量。我們首先求解了漢諾塔圖中最外面兩個(gè)結(jié)點(diǎn)之間

3、的隨機(jī)游走平均首達(dá)時(shí)間，接著，我們求解了所有結(jié)點(diǎn)間的全局平均首達(dá)時(shí)間。我們給出了上述兩個(gè)量的解析結(jié)果以及其如何隨著網(wǎng)絡(luò)規(guī)模增長。隨后我們求解了漢諾塔圖概率轉(zhuǎn)移矩陣的譜，接著我們運(yùn)用所求得的譜，求得了漢諾塔圖生成樹的數(shù)量和隨機(jī)游走特征時(shí)間常數(shù)。
　　分布式一致性算法是多智能系統(tǒng)和交通運(yùn)輸中使用的重要工具。除了算法本身的正確性以外，其魯棒性、收斂速度等性質(zhì)，也是相關(guān)研究領(lǐng)域重點(diǎn)考慮的。在本論文中，我們研究了漢諾塔上的一致性問題，包括收