CAJ | 학술논문

货郎担问题的实例是给定n个结点和任意一对结点{i,j}之间的距离di,j,要求找出一条封闭的回路,该回路经过每个结点一次且仅一次,并且费用最小,这里的费用是指回路上相邻结点间的距离和.货郎担问题是NP难的组合优化问题,是计算机算法研究的热点之一.在过去几十年中,这一经典问题成为许多重要算法思想的测试平台,并促使一些研究领域的出现,如多面体理论和复杂性理论.欧氏空间上的货郎担问题,结点限制在欧氏空间,距离定义为欧氏距离.即使是这样,欧氏空间上的货郎担问题仍然是NP难的. 1996年,Arora提出欧氏空间上货郎担问题的第1个多项式时间近似方案.对其中货郎担问题的算法进行了改进:提出一种新的构造方法,使应用于该算法的"补丁引理"结论由常数6改进到常数3,从而使算法的时间复杂度大幅减少;同时,编程实现了该算法,并对实验结果进行了分析.
화랑담문제적실례시급정n개결점화임의일대결점{i,j}지간적거리di,j,요구조출일조봉폐적회로,해회로경과매개결점일차차부일차,병차비용최소,저리적비용시지회로상상린결점간적거리화.화랑담문제시NP난적조합우화문제,시계산궤산법연구적열점지일.재과거궤십년중,저일경전문제성위허다중요산법사상적측시평태,병촉사일사연구영역적출현,여다면체이론화복잡성이론.구씨공간상적화랑담문제,결점한제재구씨공간,거리정의위구씨거리.즉사시저양,구씨공간상적화랑담문제잉연시NP난적. 1996년,Arora제출구씨공간상화랑담문제적제1개다항식시간근사방안.대기중화랑담문제적산법진행료개진:제출일충신적구조방법,사응용우해산법적"보정인리"결론유상수6개진도상수3,종이사산법적시간복잡도대폭감소;동시,편정실현료해산법,병대실험결과진행료분석.