计算机研究与发展
計算機研究與髮展
계산궤연구여발전
JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT
2007年
10期
1796-1800
,共5页
江贺%张宪超%车皓阳%陈国良
江賀%張憲超%車皓暘%陳國良
강하%장헌초%차호양%진국량
黑白旅行商问题%NP-难解%线性规划%完全算法%商品流
黑白旅行商問題%NP-難解%線性規劃%完全算法%商品流
흑백여행상문제%NP-난해%선성규화%완전산법%상품류
黑白旅行商问题(BWTSP)是近年来出现的新NP-难解问题,根据图中边是否对称可以分为无向BWTSP和有向BWTSP两种.现有无向BWTSP的Ghiani线性规划中约束条件数目为指数多个.权值阈值等于+∞的有向BWTSP通过转换为RATSP问题而存在多项式个约束条件的线性规划.针对一般的有向BWTSP,提出了一种仅包含多项式个约束条件的新线性规划.其基本思想是首先将有向BWTSP问题归约为ATSP问题,然后利用ATSP包含n(n+4)个约束条件的Finke-Claus-Gunn线性规划,通过定义剩余和消耗基数商品流,分析了环路上的弧应满足的约束条件,并证明这些n2+2|W|的约束条件即是基数约束条件;类似地通过定义剩余和消耗权值商品流,得到n2+n+2|B|个权值约束条件. 最终得到原始问题仅包含3n2+7n个约束条件的线性规划.由于无向BWTSP问题和权值阈值等于+∞的有向BWTSP均是一般有向BWTSP的特例,故此结果对于它们同样有效.
黑白旅行商問題(BWTSP)是近年來齣現的新NP-難解問題,根據圖中邊是否對稱可以分為無嚮BWTSP和有嚮BWTSP兩種.現有無嚮BWTSP的Ghiani線性規劃中約束條件數目為指數多箇.權值閾值等于+∞的有嚮BWTSP通過轉換為RATSP問題而存在多項式箇約束條件的線性規劃.針對一般的有嚮BWTSP,提齣瞭一種僅包含多項式箇約束條件的新線性規劃.其基本思想是首先將有嚮BWTSP問題歸約為ATSP問題,然後利用ATSP包含n(n+4)箇約束條件的Finke-Claus-Gunn線性規劃,通過定義剩餘和消耗基數商品流,分析瞭環路上的弧應滿足的約束條件,併證明這些n2+2|W|的約束條件即是基數約束條件;類似地通過定義剩餘和消耗權值商品流,得到n2+n+2|B|箇權值約束條件. 最終得到原始問題僅包含3n2+7n箇約束條件的線性規劃.由于無嚮BWTSP問題和權值閾值等于+∞的有嚮BWTSP均是一般有嚮BWTSP的特例,故此結果對于它們同樣有效.
흑백여행상문제(BWTSP)시근년래출현적신NP-난해문제,근거도중변시부대칭가이분위무향BWTSP화유향BWTSP량충.현유무향BWTSP적Ghiani선성규화중약속조건수목위지수다개.권치역치등우+∞적유향BWTSP통과전환위RATSP문제이존재다항식개약속조건적선성규화.침대일반적유향BWTSP,제출료일충부포함다항식개약속조건적신선성규화.기기본사상시수선장유향BWTSP문제귀약위ATSP문제,연후이용ATSP포함n(n+4)개약속조건적Finke-Claus-Gunn선성규화,통과정의잉여화소모기수상품류,분석료배로상적호응만족적약속조건,병증명저사n2+2|W|적약속조건즉시기수약속조건;유사지통과정의잉여화소모권치상품류,득도n2+n+2|B|개권치약속조건. 최종득도원시문제부포함3n2+7n개약속조건적선성규화.유우무향BWTSP문제화권치역치등우+∞적유향BWTSP균시일반유향BWTSP적특례,고차결과대우타문동양유효.
