关于tsp问题的动态规划求解的matlab实现 |
您所在的位置:网站首页 › tsp算法代码matlab › 关于tsp问题的动态规划求解的matlab实现 |
目录
声明题目问题分析代码实现结果
声明
笔者另外加一句话哈,如果有笔者表述不清或写不清楚的地方,欢迎读者来联系和讨论,大家一起进步。 这篇文章的代码是笔者自己用动态规划的思想用matlab实现的,里面的用到了矩阵运算和matlab内置函数的使用,相比c写起来代码少了很多,数学好的看起来应该更加简单易懂。 但是是根据一位大牛的文章写的,这里附上他文章的网址。如果大家想看更详细的分析,可以去他的网站上看。 https://blog.csdn.net/joekwok/article/details/4749713 TSP问题(旅行商问题)是指旅行家要旅行n个城市,要求各个城市经历且仅经历一次然后回到出发城市,并要求所走的路程最短。 假设从顶点s出发,令d(i, V’)表示从顶点i出发经过V’(是一个点的集合)中各个顶点一次且仅一次,最后回到出发点s的最短路径长度。 推导:(分情况来讨论) ①当V’为空集,那么d(i, V’),表示从i不经过任何点就回到s了,如上图的 城市3->城市0(0为起点城市)。此时d(i, V’)=Cis(就是 城市i 到 城市s 的距离)、 ②如果V’不为空,那么就是对子问题的最优求解。你必须在V’这个城市集合中,尝试每一个,并求出最优解。 d(i, V’)=min{Cik + d(k, V’-{k})} 注:Cik表示你选择的城市和城市i的距离,d(k, V’-{k})是一个子问题。
|
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |