以下是以动态规划算法状态压缩法为基础进行。
城市距离图
以以上4个城市为例，形成一张二维矩阵表
城市距离二维矩阵表
状态压缩法使用二进制记录经过城市节点的距离，以以上4个城市为例，下面是4*7的DP数组
计算过程表
推而广之，n个城市下，城市距离二维矩阵表空间复杂度是n*n，计算过程DP表空间复杂度
空间复杂度
优化点
北京超市实际数量
百度搜索结果：全北京超市总数：60218个，就近选择100个超市送货，DP表空间复杂度就是
空间复杂度
100个超市中很多都不是直接可达的，造成空间浪费
整型数组的大小受限于开发语言和操作系统
Java语言整型数组上限为225 * 225 ，即26个超市
所以使用HASH表来代替计算过程二维表
KEY=总坐标,横坐标
VALUE=DP表对应值
结果
修改后空间使用
可计算城市节点数不受语言和操作系统限制
节省了存储空间
单系统存取情况下，HASH比数组效率低
以下是以动态规划算法状态压缩法为基础进行。 以以上4个城市为例，形成一张二维矩阵表 状态压缩法使用二进制记录经过城...
动态规划 动态规划（Dynamic Programming）是解决多阶段决策问题常用的最优化理论，动态规划和分治法...
问题描述： 旅行商问题，即TSP问题（Travelling Salesman Problem）又译为旅行推销员问题...
动态规划处理，效率不高，还有优化空间
一、动态规划 模拟退火算法解决TSP问题： 思路： 参数选取，包括初始温度、冷却系数(coolingFactor,...
0X00 例子 动态规划的空间优化（滚动数组） 0 ^ 1 = 0 1 ^ 1 = 0 少状态时用位运算在原地记录...
只能用动态规划算法计算最长回文，如下还有优化的空间嘛？不要扯马拉车，只能用动态规划哈。
动态规划(Dynamic Programming) ◼ 动态规划，简称DP是求解最优化问题的一种常用策略 ◼ 通常...
主要参考：Python求解tsp问题（动态规划，简单易懂）CSDN博客 解题思路主要有两部分： i为当前节点（城市...
动态规划-0-1背包问题 动态规划（dynamic programming）是解决多阶段决策问题常用的最优化理论，...
本文标题：TSP问题动态规划状态压缩法的空间优化
本文链接：https://www.haomeiwen.com/subject/ecaxuftx.html
网友评论