Institutional Repository
| 带多项式量级约束条件的多商品流BWTSP线性规划 | |
| Alternative Title | a multi-commodity flow linear programming with polynomial constraints for black and white traveling salesman problem |
| 江贺; 张宪超; 车皓阳; 陈国良 | |
| 2007 | |
| Source | 计算机研究与发展
 |
| ISSN | 1000-1239 |
| Volume | 44Issue:10Pages:1796-1800 |
| English Abstract | 黑白旅行商问题(BWTSP)是近年来出现的新NP-难解问题,根据图中边是否对称可以分为无向BWTSP和有向BWTSP两种.现有无向BWTSP的Ghiani线性规划中约束条件数目为指数多个.权值阈值等于+∞的有向BWTSP通过转换为RATSP问题而存在多项式个约束条件的线性规划.针对一般的有向BWTSP,提出了一种仅包含多项式个约束条件的新线性规划.其基本思想是首先将有向BWTSP问题归约为ATSP问题,然后利用ATSP包含n(n+4)个约束条件的Finke-Claus-Gunn线性规划,通过定义剩余和消耗 |
| Indexed Type | EI |
| Keyword | 黑白旅行商问题 Np-难解 线性规划 完全算法 商品流 多项式 约束条件 多商品流 线性规划 Traveling Salesman Problem 权值 旅行商问题 阈值 基数 条件数 转换 指数 证明 思想 环路 归约polynomials Traveling Salesman Problem |
| Department | 大连理工大学软件学院,大连,116621;大连理工大学软件学院,大连,116621;中国科学院软件研究所,北京,100080;中国科学技术大学计算机科学与技术系,合肥,230027 |
| Language | 中文 |
| Content Type | 期刊论文 |
| URI | http://ir.iscas.ac.cn/handle/311060/11260 |
| Collection | 天基综合信息系统全国重点实验室 |
| Recommended Citation 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. |
| Files in This Item: | ||||||
| File Name/Size | DocType | Version | Access | License | ||
| 带多项式量级约束条件的多商品流BWTSP（275KB） | 开放获取 | -- | Application Full Text | |||
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.
Edit Comment