计算机工程与设计
計算機工程與設計
계산궤공정여설계
COMPUTER ENGINEERING AND DESIGN
2015年
8期
2103-2107,2166
,共6页
谢继文%徐涛%姜锡珂%李建伏
謝繼文%徐濤%薑錫珂%李建伏
사계문%서도%강석가%리건복
国际航线%运价搜索%多约束%K条最短路径%A?Level算法
國際航線%運價搜索%多約束%K條最短路徑%A?Level算法
국제항선%운개수색%다약속%K조최단로경%A?Level산법
international airlines%searching for air fares%multiple constrained%K shortest paths%A?Level algorithm
为提升国际航线运价搜索效率，建立一个国际航线运价搜索的 EKMCSP 模型，该模型基于 K 条多约束最短路径(KMCSP)问题并进行扩展。国际航线运价搜索的各种因素被表示为EKMCSP模型中的变量、约束和目标；针对建立的国际航线运价搜索 EKMCSP模型提出 A?Level算法，结合国际航线运价搜索的特点，采用有限层搜索的思想，提高搜索效率并减小搜索规模。大量实验结果表明，该算法可实现国际航线运价搜索的 EKMCSP 问题的快速求解，且解集具有较高的正确率。
為提升國際航線運價搜索效率，建立一箇國際航線運價搜索的 EKMCSP 模型，該模型基于 K 條多約束最短路徑(KMCSP)問題併進行擴展。國際航線運價搜索的各種因素被錶示為EKMCSP模型中的變量、約束和目標；針對建立的國際航線運價搜索 EKMCSP模型提齣 A?Level算法，結閤國際航線運價搜索的特點，採用有限層搜索的思想，提高搜索效率併減小搜索規模。大量實驗結果錶明，該算法可實現國際航線運價搜索的 EKMCSP 問題的快速求解，且解集具有較高的正確率。
위제승국제항선운개수색효솔，건립일개국제항선운개수색적 EKMCSP 모형，해모형기우 K 조다약속최단로경(KMCSP)문제병진행확전。국제항선운개수색적각충인소피표시위EKMCSP모형중적변량、약속화목표；침대건립적국제항선운개수색 EKMCSP모형제출 A?Level산법，결합국제항선운개수색적특점，채용유한층수색적사상，제고수색효솔병감소수색규모。대량실험결과표명，해산법가실현국제항선운개수색적 EKMCSP 문제적쾌속구해，차해집구유교고적정학솔。
To improve the efficiency of searching for best air fares in international airlines,the extended K multiple constrained shortest path (EKMCSP)model of searching for best air fares in international airlines was established,in which the previous K multiple constrained shortest path (KMCSP)model was extended and all kinds of factors in searching model were represented clearly as variables,constraints and objectives.A?Level algorithm based on EKMCSP model of searching for best airfares in in-ternational airlines was presented.Furthermore,a technique of searching with limited levels was combined with the A?Level al-gorithm to improve the speed of searching and reduce the scales of searching.Experimental results show that the solution to EK-MCSP problem about searching for best air fares in international airlines can be obtained fast using the proposed algorithm,and the solution set has higher accuracy.
