| 不完全信息下路径选择策略设计及分析 |
| |
| 引用本文： | 武小平,方静,谢逢洁.不完全信息下路径选择策略设计及分析[J].西安邮电学院学报,2012,17(3):117-120. |
| |
| 作者姓名： | 武小平 方静 谢逢洁 |
| |
| 作者单位： | 1. 西安邮电学院管理工程学院,陕西西安710121 西安交通大学管理学院,陕西西安710049
2. 西安邮电学院管理工程学院,陕西西安,710121 |
| |
| 基金项目： | 陕西省教育厅人文社会科学基金资助项目，西安邮电学院中青年面上基金资助项目 |
| |
| 摘 要： | 用户出行时不能获知所有路况信息,针对从出发地去目的地,路段权重信息无法准确预知就必须做出决策,选择出行路径的问题。从在线与竞争策略的角度出发考虑,设计了最优策略——贪婪策略选择路径,当路段权重满足三角不等式时,证明了该策略的竞争比是3且是紧界;当路段权重不满足三角不等式时,证明了该问题不存在竞争策略。
|
| 关 键 词： | 不完全信息 路段权重 竞争分析 竞争比 |
Strategies design and analysis of paths choosing without complete information |
| |
| WU Xiaoping,FANG Jing,XIE Fengjie.Strategies design and analysis of paths choosing without complete information[J].Journal of Xi'an Institute of Posts and Telecommunications,2012,17(3):117-120. |
| |
| Authors: | WU Xiaoping FANG Jing XIE Fengjie |
| |
| Affiliation: | 1(1.School of Management Engineering,Xi’an University of Posts and Telecommunications,Xi’an 710061,China; 2.School of Management,Xi’an Jiaotong University,Xi’an 710049,China) |
| |
| Abstract: | For the problem that the user choose its path without complete information of edge weight from departure to destinations in a traffic network,the method of online and competitive analysis is put forward and the optimum strategy,greed strategy,is designed to solve the problem,it proved that competitive ratio of the strategy is 3 and is tight under the assumption of triangle inequality;otherwise,there is no exist competitive strategy for the problem. |
| |
| Keywords: | incomplete information edge weight competitive analysis competitive ratio |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
