| 带多项式量级约束条件的多商品流BWTSP线性规划 |
| 其他题名 | a multi-commodity flow linear programming with polynomial constraints for black and white traveling salesman problem
|
| 江贺; 张宪超; 车皓阳; 陈国良
|
| 2007
|
| 发表期刊 | 计算机研究与发展
 |
| ISSN | 1000-1239
|
| 卷号 | 44期号:10页码:1796-1800 |
| 摘要 | 黑白旅行商问题(BWTSP)是近年来出现的新NP-难解问题,根据图中边是否对称可以分为无向BWTSP和有向BWTSP两种.现有无向BWTSP的Ghiani线性规划中约束条件数目为指数多个.权值阈值等于+∞的有向BWTSP通过转换为RATSP问题而存在多项式个约束条件的线性规划.针对一般的有向BWTSP,提出了一种仅包含多项式个约束条件的新线性规划.其基本思想是首先将有向BWTSP问题归约为ATSP问题,然后利用ATSP包含n(n+4)个约束条件的Finke-Claus-Gunn线性规划,通过定义剩余和消耗 |
| 收录类别 | EI
|
| 关键词 | 黑白旅行商问题
Np-难解
线性规划
完全算法
商品流
多项式
约束条件
多商品流
线性规划
Traveling Salesman Problem
权值
旅行商问题
阈值
基数
条件数
转换
指数
证明
思想
环路
归约polynomials
Traveling Salesman Problem
|
| 部门归属 | 大连理工大学软件学院,大连,116621;大连理工大学软件学院,大连,116621;中国科学院软件研究所,北京,100080;中国科学技术大学计算机科学与技术系,合肥,230027
|
| 语种 | 中文
|
| 内容类型 | 期刊论文
|
| URI标识 | http://ir.iscas.ac.cn/handle/311060/11260
|
| 专题 | 天基综合信息系统全国重点实验室
|
推荐引用方式
GB/T 7714 |
江贺,张宪超,车皓阳,等. 带多项式量级约束条件的多商品流BWTSP线性规划[J]. 计算机研究与发展,2007,44(10):1796-1800.
|
| APA |
江贺,张宪超,车皓阳,&陈国良.(2007).带多项式量级约束条件的多商品流BWTSP线性规划.计算机研究与发展,44(10),1796-1800.
|
| MLA |
江贺,et al."带多项式量级约束条件的多商品流BWTSP线性规划".计算机研究与发展 44.10(2007):1796-1800.
|
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。
修改评论