天津理工学院学报
天津理工學院學報
천진리공학원학보
JOURNAL OF TIANJIN INSTITUTE OF TECHNOLOGY
2002年
3期
50-54
,共5页
TSP%最小元素%组合%置换%合成%算法
TSP%最小元素%組閤%置換%閤成%算法
TSP%최소원소%조합%치환%합성%산법
n阶完全图(边赋权)的矩阵每行每列最小元素对应着一个次数为n的置换,若从这些最小元素组成的所有圈中每圈至少取出一个元素并令其为∞,那么仅包含这些元素的子矩阵可以经过初等变换将这些元素置于主对角线上形成一个新矩阵,其每行每列最小元素又对应一个新的置换.在满足一定条件时,两个置换合成能够得到一个次数为n的循环置换.运用这种方法,可使求TSP解的算法得到简化.
n階完全圖(邊賦權)的矩陣每行每列最小元素對應著一箇次數為n的置換,若從這些最小元素組成的所有圈中每圈至少取齣一箇元素併令其為∞,那麽僅包含這些元素的子矩陣可以經過初等變換將這些元素置于主對角線上形成一箇新矩陣,其每行每列最小元素又對應一箇新的置換.在滿足一定條件時,兩箇置換閤成能夠得到一箇次數為n的循環置換.運用這種方法,可使求TSP解的算法得到簡化.
n계완전도(변부권)적구진매행매렬최소원소대응착일개차수위n적치환,약종저사최소원소조성적소유권중매권지소취출일개원소병령기위∞,나요부포함저사원소적자구진가이경과초등변환장저사원소치우주대각선상형성일개신구진,기매행매렬최소원소우대응일개신적치환.재만족일정조건시,량개치환합성능구득도일개차수위n적순배치환.운용저충방법,가사구TSP해적산법득도간화.
