CAJ | 학술논문

用户出行时不能获知所有路况信息,针对从出发地去目的地,路段权重信息无法准确预知就必须做出决策,选择出行路径的问题。从在线与竞争策略的角度出发考虑,设计了最优策略——贪婪策略选择路径,当路段权重满足三角不等式时,证明了该策略的竞争比是3且是紧界;当路段权重不满足三角不等式时,证明了该问题不存在竞争策略。
용호출행시불능획지소유로황신식,침대종출발지거목적지,로단권중신식무법준학예지취필수주출결책,선택출행로경적문제。종재선여경쟁책략적각도출발고필,설계료최우책략——탐람책략선택로경,당로단권중만족삼각불등식시,증명료해책략적경쟁비시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.