| 题名: | 带多项式量级约束条件的多商品流BWTSP线性规划 |
| 其他题名: | a multi-commodity flow linear programming with polynomial constraints for black and white traveling salesman problem
|
| 作者: | 江贺
; 张宪超
; 车皓阳
; 陈国良
|
| 关键词: | 黑白旅行商问题
; NP-难解
; 线性规划
; 完全算法
; 商品流
; 多项式
; 约束条件
; 多商品流
; 线性规划
; Traveling Salesman Problem
; 权值
; 旅行商问题
; 阈值
; 基数
; 条件数
; 转换
; 指数
; 证明
; 思想
; 环路
; 归约Polynomials
; Traveling salesman problem
|
| 刊名: | 计算机研究与发展
|
| 发表日期: | 2007
|
| 卷: | 44, 期:10, 页:1796-1800 | | 收录类别: | EI
|
| 部门归属: | 大连理工大学软件学院,大连,116621;大连理工大学软件学院,大连,116621;中国科学院软件研究所,北京,100080;中国科学技术大学计算机科学与技术系,合肥,230027
|
| 摘要: | 黑白旅行商问题(BWTSP)是近年来出现的新NP-难解问题,根据图中边是否对称可以分为无向BWTSP和有向BWTSP两种.现有无向BWTSP的Ghiani线性规划中约束条件数目为指数多个.权值阈值等于+∞的有向BWTSP通过转换为RATSP问题而存在多项式个约束条件的线性规划.针对一般的有向BWTSP,提出了一种仅包含多项式个约束条件的新线性规划.其基本思想是首先将有向BWTSP问题归约为ATSP问题,然后利用ATSP包含n(n+4)个约束条件的Finke-Claus-Gunn线性规划,通过定义剩余和消耗 |
| 语种: | 中文
|
| 内容类型: | 期刊论文
|
| URI标识: | http://ir.iscas.ac.cn/handle/311060/11260
|
| Appears in Collections: | 综合信息系统技术国家级重点实验室 _期刊论文
|
| File Name/ File Size |
Content Type |
Version |
Access |
License |
|
|---|
| 带多项式量级约束条件的多商品流BWTSP线性规划.pdf（275KB） | -- | -- | 限制开放 | -- | 联系获取全文 |
|
| Recommended Citation: | |
江贺,张宪超,车皓阳,等. 带多项式量级约束条件的多商品流BWTSP线性规划[J]. 计算机研究与发展,2007-01-01,44(10):1796-1800.
|
|
|
