MIP经典问题：旅行商问题 (traveling salesman problem)
2024-08-25 22:22:41
*本文主要记录和分享学习到的知识，算不上原创。
*参考文献见链接。
旅行商问题、背包问题都是0-1规划问题中最为经典的问题。
通常来说，当我们学习并熟悉一种求解混合整数问题的技巧时，可以用这种技巧来求解旅行商问题或者背包问题，以此来验证自己对该技巧的掌握程度。
目录
什么是旅行商问题
旅行商问题的数学模型
什么是旅行商问题
定义
Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city and returns to the origin city?
时间复杂度
分类
其中，sTSP是最简单的TSP问题。
旅行商问题的数学建模
Integer programming formulation of sTSP
变量
This formulation associates a binary variable xij with each edge (i, j), equal to 1 if and only if the edge appears in the optimal tour. The formulation of TSP is as follows.
模型
Integer programming formulation of aTSP
变量
xij is a binary variable, associated with arc (i,j) and equal to 1 if and only if the arc appears in the optimal tour.
模型
参考文献
https://en.wikipedia.org/wiki/Travelling_salesman_problem
最新文章
- Struts2中的ModelDriven机制及其运用
- 【C语言学习笔记】存储类、链接和内存管理
- shell学习笔记（1）-变量
- POJ动态规划题目列表
- 使用webview如何做超时判断
- C++程序设计实践指导1.9统计与替换字符串中的关键字改写要求实现
- %hd %d %ld %u ......
- 航道水下地形DEM构建方法比较
- Xcode4 布置Git环境Your working copy is out of date. Try pulling from the remote to get the latest change
- Codeforces Round #243 (Div. 1)-A,B,C-D
- 用SqlBulkCopy批量插入数据到SqlServer数据库表中
- Monit : 开源监控工具介绍
- Mac os 下brew的安装与使用—— Homebrew
- UnicodeEncodeError: 'ascii' codec can't encode characters in position 0-25: ordinal not in range(128)
- python之路——2
- 容错处理库Polly使用文档
- 爬虫框架：scrapy
- POJ3041 Asteroids（匈牙利算法）
- 关于分部视图（Partial View）
- 如何生成SSH key