CAJ | 학술논문

旅行商问题是组合优化的一个经典问题,也是评价算法好坏的一个标准,它要求在给定的一张图中寻找一条哈密尔顿回路,使得该回路在所有的回路中长度最短。然而,该问题是一个NP完全问题,其求解时间会随着问题规模的扩大急剧上升。因此,只能希望在允许的时间内寻求问题的一个较优的解来替代。本文借助生物学的相关理论与思想采用遗传算法对该问题进行求解,最后通过对遗传算法的进一步分析,提出了一种可行的改进算法,达到了获得较优解的目的。
여행상문제시조합우화적일개경전문제,야시평개산법호배적일개표준,타요구재급정적일장도중심조일조합밀이돈회로,사득해회로재소유적회로중장도최단。연이,해문제시일개NP완전문제,기구해시간회수착문제규모적확대급극상승。인차,지능희망재윤허적시간내심구문제적일개교우적해래체대。본문차조생물학적상관이론여사상채용유전산법대해문제진행구해,최후통과대유전산법적진일보분석,제출료일충가행적개진산법,체도료획득교우해적목적。
Traveling salesman problem is a classic combinatorial optimization problem,but also a standard quality assessment algorithm,it calls for a given picture in search for a Hamilton loop to make it in all the loop of the circuit shortest length.However,this problem is a NP complete problem;the solution time will rise sharply with the expansion of the scale.Therefore,we can only hope in allowing time for problem a relatively optimal solution to replace.This essay based on the related theories and thoughts of biology,using genetic algorithm to solve the TSP problem,and eventually puts forward a feasible and improved algorithm to get the optimal solution through further analysis of the genetic algorithm.