河海大学学报(自然科学版)
河海大學學報(自然科學版)
하해대학학보(자연과학판)
JOURNAL OF HOHAI UNIVERSITY (NATURAL SCIENCES)
2006年
6期
717-720
,共4页
TSP%顶点%方阵%路径%最短路径
TSP%頂點%方陣%路徑%最短路徑
TSP%정점%방진%로경%최단로경
对于被访问城市数为n的不对称旅行商问题,构造了一个n行和n列的方阵,每一行上的n个元素为同一个被访问城市;每一列上的n个元素为n个互不相同的被访问城市.依次从该方阵的第一列到第k列上各取出一个城市,同一行上不存在两个被取出的城市,这样取出的城市序列就构成了一条长度为k的路径.主要讨论最短路径的性质:如果一条长度为(n-1)的最短路径能被产生,则该路径上的任一长度为k的路径都为最短路径,k=1,2,…,n-2.该性质为旅行商问题算法研究的基础.
對于被訪問城市數為n的不對稱旅行商問題,構造瞭一箇n行和n列的方陣,每一行上的n箇元素為同一箇被訪問城市;每一列上的n箇元素為n箇互不相同的被訪問城市.依次從該方陣的第一列到第k列上各取齣一箇城市,同一行上不存在兩箇被取齣的城市,這樣取齣的城市序列就構成瞭一條長度為k的路徑.主要討論最短路徑的性質:如果一條長度為(n-1)的最短路徑能被產生,則該路徑上的任一長度為k的路徑都為最短路徑,k=1,2,…,n-2.該性質為旅行商問題算法研究的基礎.
대우피방문성시수위n적불대칭여행상문제,구조료일개n행화n렬적방진,매일행상적n개원소위동일개피방문성시;매일렬상적n개원소위n개호불상동적피방문성시.의차종해방진적제일렬도제k렬상각취출일개성시,동일행상불존재량개피취출적성시,저양취출적성시서렬취구성료일조장도위k적로경.주요토론최단로경적성질:여과일조장도위(n-1)적최단로경능피산생,칙해로경상적임일장도위k적로경도위최단로경,k=1,2,…,n-2.해성질위여행상문제산법연구적기출.
