带多项式量级约束条件的多商品流BWTSP线性规划
文献类型：期刊论文
| 作者 | 江贺 ; 张宪超 ; 车皓阳 ; 陈国良 |
| 刊名 | 计算机研究与发展
 |
| 出版日期 | 2007 |
| 卷号 | 44期号:10页码:1796-1800 |
| 关键词 | 黑白旅行商问题 NP-难解 线性规划 完全算法 商品流 多项式 约束条件 多商品流 线性规划 Traveling Salesman Problem 权值 旅行商问题 阈值 基数 条件数 转换 指数 证明 思想 环路 归约Polynomials Traveling salesman problem |
| ISSN号 | 1000-1239 |
| 其他题名 | a multi-commodity flow linear programming with polynomial constraints for black and white traveling salesman problem |
| 中文摘要 | 黑白旅行商问题(BWTSP)是近年来出现的新NP-难解问题,根据图中边是否对称可以分为无向BWTSP和有向BWTSP两种.现有无向BWTSP的Ghiani线性规划中约束条件数目为指数多个.权值阈值等于+∞的有向BWTSP通过转换为RATSP问题而存在多项式个约束条件的线性规划.针对一般的有向BWTSP,提出了一种仅包含多项式个约束条件的新线性规划.其基本思想是首先将有向BWTSP问题归约为ATSP问题,然后利用ATSP包含n(n+4)个约束条件的Finke-Claus-Gunn线性规划,通过定义剩余和消耗 |
| 收录类别 | EI |
| 语种 | 中文 |
| 公开日期 | 2011-07-01 |
| 附注 | The black and white salesman problem (BWTSP) is a new NP-hard problem, which can be divided into the undirected BWTSP and the directed BWTSP according to the symmetry of edges in graph. As a basis of complete algorithm design for NP-hard problems, the num |
| 源URL | [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. |
入库方式： OAI收割
来源：软件研究所
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。