不完全信息下路径选择策略设计及分析  

Strategies design and analysis of paths choosing without complete information

作　　者：武小平[1,2] 方静[1] 谢逢洁[1] 

机构地区：[1]西安邮电学院管理工程学院,陕西西安710121 [2]西安交通大学管理学院,陕西西安710049

出　　处：《西安邮电学院学报》2012年第3期117-120,共4页Journal of Xi'an Institute of Posts and Telecommunications

基　　金：陕西省教育厅人文社会科学基金资助项目(11JK0179;10JK213;12JK0055);西安邮电学院中青年面上基金资助项目(1040401;1040403)

摘　　要：用户出行时不能获知所有路况信息,针对从出发地去目的地,路段权重信息无法准确预知就必须做出决策,选择出行路径的问题。从在线与竞争策略的角度出发考虑,设计了最优策略——贪婪策略选择路径,当路段权重满足三角不等式时,证明了该策略的竞争比是3且是紧界;当路段权重不满足三角不等式时,证明了该问题不存在竞争策略。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 tri- angle inequality otherwise, there is no exist competitive strategy for the problem.

关 键 词：不完全信息 路段权重 竞争分析 竞争比 

分 类 号：U491[交通运输工程—交通运输规划与管理]