路由對策的算法研究.pdf

1、將交通網(wǎng)絡在圖論中進行抽象，同時又根據(jù)圖論中最大流、最短路、最小費用流等的性質(zhì)，對局中人在網(wǎng)絡中選擇自己路由的策略作了進一步的研究，具體分為以下幾部分:
　　第一部分從網(wǎng)絡流模型出發(fā)，研究網(wǎng)絡中的最優(yōu)流以及納什均衡流，并給出了它們的有效算法。在限定容量的網(wǎng)絡中，通過引入邊-路徑模型得出了最大流，并得出網(wǎng)路最大流量唯一但最大流量的分流并不唯一的結(jié)論。根據(jù)網(wǎng)絡的最大流的模型可以判定所給出的網(wǎng)絡流是否為可行流。在給出網(wǎng)絡流為可行流時，得

2、到了網(wǎng)絡的最優(yōu)流及納什均衡流的有效算法，并證明了一般網(wǎng)絡的納什均衡流問題為NP-完全問題。
　　第二部分在信息對稱且路由環(huán)境為自私的情況下，研究無政府代價的大小。當網(wǎng)絡中各邊的成本為線性函數(shù)時，若網(wǎng)絡流為可分流時得出網(wǎng)絡的無政府代價不超過4/3的結(jié)論;若網(wǎng)絡流為不可分流時，得出網(wǎng)絡的無政府代價至多為(√5+1)/2。無政府代價對網(wǎng)絡路由的影響非常大，它在一定程度上反應了局中人由于自己的利益而導致網(wǎng)絡社會成本的增加，同時也說明了納什

3、均衡流時局中人的選擇并不一定是網(wǎng)絡的最優(yōu)路由選擇。
　　第三部分由于最優(yōu)流為網(wǎng)絡的最優(yōu)選擇，但是，它卻在一定程度上損害了部分局中人的利益。該部分研究了頂點對間和每個頂點對的最優(yōu)流的不公平性，并得出在路由成本為線性函數(shù)時至多為1的結(jié)論。
　　第四部分通過引入某個城市中定點對的路由選擇和多個城市間的路由選擇研究網(wǎng)絡路由對策在實際中的應用。針對不同的路由選擇，局中人在掌握交通狀況的條件下根據(jù)自身的路由選擇模型選擇最佳路由。在不考慮