2手房产App网站开发,wordpress 弹窗登录插件,网站内容包括,如何进行关键词分析动态规划
动态规划(dynamic programming)是运筹学的一个分支#xff0c;是求解决策过程(decision process)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时#xff0c;提出了著名的最优化原理(pri…动态规划
动态规划(dynamic programming)是运筹学的一个分支是求解决策过程(decision process)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时提出了著名的最优化原理(principle of optimality)把多阶段过程转化为一系列单阶段问题利用各阶段之间的关系逐个求解创立了解决这类过程优化问题的新方法——动态规划。
https://blog.csdn.net/hebtu666/article/category/8018091基础总结 状态压缩
我们在进行动态规划时有时状态相当复杂看上去需要很多空间比如一个数组才能表示一个状态那么就需要对状态进行某种编码进行压缩表示。
比如状态和某个集合有关集合里可以有一些元素没有另一些元素那么就可以用一个整数表示该集合每个元素对应于一个bit有该元素则该bit就是1。
这个皇后问题就可以帮助理解https://blog.csdn.net/hebtu666/article/details/84631083 旅行商问题 旅行商问题(TravelingSalesmanProblemTSP)是一个经典的组合优化问题。经典的TSP可以描述为一个商品推销员要去若干个城市推销商品该推销员从一个城市出发需要经过所有城市后回到出发地。应如何选择行进路线以使总的行程最短。从图论的角度来看该问题实质是在一个带权完全无向图中找一个权值最小的Hamilton回路。由于该问题的可行解是所有顶点的全排列随着顶点数的增加会产生组合爆炸它是一个NP完全问题。由于其在交通运输、电路板线路设计以及物流配送等领域内有着广泛的应用国内外学者对其进行了大量的研究。早期的研究者使用精确算法求解该问题常用的方法包括分枝定界法、线性规划法、动态规划法等。但是随着问题规模的增大精确算法将变得无能为力因此在后来的研究中国内外学者重点使用近似算法或启发式算法主要有遗传算法、模拟退火法、蚁群算法、禁忌搜索算法、贪婪算法和神经网络等。 如图我们如何从0点出发以最小代价走过所有的点 分析 抛开这个图我们试想我们可能从0点一次性走到哪些点呢
只可能1点、2点、3点、4点废话
那我们如果知道了
1从1点开始走经过所有的点最后走到了0点的最小距离a
2从2点开始走经过所有的点最后走到了0点的最小距离b
3从3点开始走经过所有的点最后走到了0点的最小距离c
4从4点开始走经过所有的点最后走到了0点的最小距离d
请再次注意
我们可能从0点一次性走到哪些点呢
只可能1点、2点、3点、4点废话
所以我们可以从0点走到1点再从1点经过最小距离走到0点。
2点、3点、4点同理。
那么我们取min(a3,bMAX,c4,dMAX)即可。
3为0点走到1点的距离4为0点走到3点的距离。
MAX代表此路不通。。 那我们继续思考abcd怎么求呢其实同样的 比如求a 从1点开始走经过所有的点最后走到了0点的最小距离a
同样的思考我们可能从1点一次性走到哪些点呢
答可以走到0点、2点、3点、4点。
注意由于问题要求为只能经过每一个顶点一次所以我们要去掉0点因为我们经过0点最后再到0点就会重复所以
“经过所有的点”是不准确的是除0点的所有的点。
所以只有三个点可能从1点走过去我们需要求
1从2点开始走经过除0点所有的点最后走到了0点的最小距离x
2从3点开始走经过除0点所有的点最后走到了0点的最小距离y
3从4点开始走经过除0点所有的点最后走到了0点的最小距离z
然后取min(x到2点的距离y到3点的距离z到4点的距离) 归纳表达式
1我们会发现每一次状态转移其实对应的是一个点的集合 以后还会有经过除12点经过除123点等等。 2还有从哪个点开始走 这两个条件就可以描述当前的状态。
我们把上面的总结用公式表示出来
S为已经访问过的点的集合
v表示当前所在点。
那么dp[S][v]就表示为从点v出发访问剩余点最终返回0点的最小长度。
我们把刚才的求解过程用公式表达出来。 ∉这个符号我实在没找到理解意思。 压缩
像这样状态可以根据集合表示的DP我们称作状态压缩DP。
状态和某个集合有关集合里可以有一些元素没有另一些元素那么就可以用一个整数表示该集合每个元素对应于一个bit有该元素则该bit就是1。
本题来说所有点都在集合里就是11111
哪个点没在对应的位就为0 注意对于状态不是整数而是集合的情况通常不太容易确定DP的顺序如果确实不好想顺序可以通过记忆化搜索来做。
集合S如果对于任意S(i)S(j)那么一定有ij。所以确定了顺序。 确定dp表的大小有n个城市从0开始编号那么dp表的行数就是n列数就是2^(n-1)
int n;
int d[MAX_N][MAX_N];//邻接矩阵
int dp[1MAX_N][MAX_N];
对于数字x要看它的第i位是不是1那么可以通过 (x i) 1取出那一位来看
先用足够大的值初始化dp数组不要影响结果然后核心代码
for(int S (1n)-2 ; S 0 ; s--)//每一个集合
{for(int v 0 ; v n ; v)//每一个出发点{for(int u 0 ; u n ; u)//访问每一个点{if(!(Su1))//判断是否在集合中{dp[S][v] min(dp[S][v] , dp[S | 1u][u]d[v][u]);}}}
} 总结 当我们把状态压缩应用到动态规划中可以用来精简状态节约空间也方便转移。
最常见的就是用二进制来表是状态利用各种位移运算就可以实现O(1)的转移。
