河海大学学报（自然科学版）
河海大學學報（自然科學版）
하해대학학보（자연과학판）
JOURNAL OF HOHAI UNIVERSITY (NATURAL SCIENCES)
2007年
2期
229-232
,共4页
旅行商问题%最短路径%有向图%启发式算法
旅行商問題%最短路徑%有嚮圖%啟髮式算法
여행상문제%최단로경%유향도%계발식산법
用一个有向图表示旅行商避开某一城市到1个顶点的所有最短路径,并在每条弧上定义一个线性表,用以记录所有包含该弧的图,从而将判断某条弧和某个顶点是否应该存在于某个子图中的最短路径上的问题转化为线性表的相关操作,进而讨论了图上的弧都在某一最短路径上的充要条件,以及如何顺序产生第1列到第n列的顶点上的图,如何从这些图上搜索出近似最优解的方法.
用一箇有嚮圖錶示旅行商避開某一城市到1箇頂點的所有最短路徑,併在每條弧上定義一箇線性錶,用以記錄所有包含該弧的圖,從而將判斷某條弧和某箇頂點是否應該存在于某箇子圖中的最短路徑上的問題轉化為線性錶的相關操作,進而討論瞭圖上的弧都在某一最短路徑上的充要條件,以及如何順序產生第1列到第n列的頂點上的圖,如何從這些圖上搜索齣近似最優解的方法.
용일개유향도표시여행상피개모일성시도1개정점적소유최단로경,병재매조호상정의일개선성표,용이기록소유포함해호적도,종이장판단모조호화모개정점시부응해존재우모개자도중적최단로경상적문제전화위선성표적상관조작,진이토론료도상적호도재모일최단로경상적충요조건,이급여하순서산생제1렬도제n렬적정점상적도,여하종저사도상수색출근사최우해적방법.
