leetcode.LCP 13. 寻宝
构造出S>M1,M2,Mn>T的图信息,求解旅行商问题
旅行商问题 贪心算法
- 1.先计算矩阵两两之间的最短路信息
- 2.计算S>Oi>Mi的最小花费
- 3.计算Mi>Oj>Mj的最小花费
- 4.计算Mj>T的最小花费
不是最优解
minimalSteps.cpp
旅行商问题 动态规划
- 1.先求出 S>Oj,Mi>Oj,S>T,Mi>T之间的最短路信息
求此矩阵信息
| $O_1$ | $O_2$ | $O_3$ | … | $O_{m-1}$ | $O_{m}$ | T | |
|---|---|---|---|---|---|---|---|
| S | … | ||||||
| $M_1$ | … | ||||||
| $M_2$ | … | ||||||
| … | … | … | … | … | … | … | … |
| $M_{n-1}$ | … | ||||||
| $M_{n}$ | … |
- 2.根据第一步得到的结果，求出 S>Oj>Mi,Mi>Oj>Mii之间的最短路信息
| S | $M_1$ | $M_2$ | … | $M_{n-1}$ | $M_{n}$ | |
|---|---|---|---|---|---|---|
| S | 0 | … | ||||
| $M_1$ | … | |||||
| $M_2$ | … | |||||
| … | … | … | … | … | … | … |
| $M_{n-1}$ | … | |||||
| $M_{n}$ | … |
- 3.根据第二步得到的结果，求旅行商问题
从S出发，经过所有的M，最后到T的旅行商问题