详情

原文传递路由对策的算法研究

论文题名：	路由对策的算法研究
关键词：	路由策略;纳什均衡流;网络最优流;可行流;图论;NP-完全问题
摘要：	将交通网络在图论中进行抽象，同时又根据图论中最大流、最短路、最小费用流等的性质，对局中人在网络中选择自己路由的策略作了进一步的研究，具体分为以下几部分: 　　第一部分从网络流模型出发，研究网络中的最优流以及纳什均衡流，并给出了它们的有效算法。在限定容量的网络中，通过引入边-路径模型得出了最大流，并得出网路最大流量唯一但最大流量的分流并不唯一的结论。根据网络的最大流的模型可以判定所给出的网络流是否为可行流。在给出网络流为可行流时，得到了网络的最优流及纳什均衡流的有效算法，并证明了一般网络的纳什均衡流问题为NP-完全问题。　　第二部分在信息对称且路由环境为自私的情况下，研究无政府代价的大小。当网络中各边的成本为线性函数时，若网络流为可分流时得出网络的无政府代价不超过4/3的结论;若网络流为不可分流时，得出网络的无政府代价至多为(√5+1)/2。无政府代价对网络路由的影响非常大，它在一定程度上反应了局中人由于自己的利益而导致网络社会成本的增加，同时也说明了纳什均衡流时局中人的选择并不一定是网络的最优路由选择。　　第三部分由于最优流为网络的最优选择，但是，它却在一定程度上损害了部分局中人的利益。该部分研究了顶点对间和每个顶点对的最优流的不公平性，并得出在路由成本为线性函数时至多为1的结论。　　第四部分通过引入某个城市中定点对的路由选择和多个城市间的路由选择研究网络路由对策在实际中的应用。针对不同的路由选择，局中人在掌握交通状况的条件下根据自身的路由选择模型选择最佳路由。在不考虑整个网络的最优成本的情况下，局中人通过自身利益的衡量，最终获得的路由策略集合即为纳什均衡策略集合，即没有任何局中人改变自己的选择策略。
作者：	张俊丽
专业：	计算数学
导师：	许成
授予学位：	硕士
授予学位单位：	青岛大学
学位年度：	2014
正文语种：	中文