【算法设计与分析】基于Go语言实现动态规划法解决TSP问题

 本文针对于最近正在学习的Go语言，以及算法课实验所需内容进行Coding，一举两得！     

一、前言 

        由于这个实验不要求向之前的实验一样做到那种连线的可视化，故可以用图形界面不那么好实现的语言进行编写，考虑到Go语言的方兴未艾，所以采用此种语言解决问题。

---

 二、问题

        TSP问题的大致解法，老师在课上已经说过了，清华大学出版社的《算法设计与分析》（第二版，然而书上伪代码存在一些疏漏）里面也有所阐述，这里不做细致解释。

---

三、代码分析

        主要可分为三个部分，输入、输出、计算。

1.输入

        输入部分需要一个整型变量存点（城市）的数量，一个矩阵存点到点的距离，另外增设一个矩阵存到某个点的最近的前驱。这里还有一个重要的问题是如何做出这些点的子集，也就是所要画的图（实验结果）的表头横向内容，代码如下：

 ·········var nums int// 读取二维数组的行数和列数fmt.Print("请输入（城市）点数: ")fmt.Scanln(&nums)// 初始化一个二维数组arc := make([][]int, nums)for i := range arc {arc[i] = make([]int, nums)}// 从控制台读取二维数组的值fmt.Println("请输入二维数组的元素，每行输入完毕后按回车键：")for i := 0; i < nums; i++ {for j := 0; j < nums; j++ {var putin intfmt.Scanf("%d", &putin)if putin == 0 {putin = 2004}arc[i][j] = putin}fmt.Scanln() // 跳过每行输入后的换行符}var LengthOfd int = int(math.Pow(2, float64(nums-1)))//下面的这个d就是那个动态规划法的表d := make([][]int, nums)for i := range d {d[i] = make([]int, LengthOfd)}//同样设置一个跟d一样的矩阵，来存最近的前驱front := make([][]int, nums)for i := range front {front[i] = make([]int, LengthOfd)}//初始化设置成很大的for i := range d {for j := range d[i] {d[i][j] = 2004front[i][j] = 2004}}for i := 0; i < nums; i++ {d[i][0] = arc[i][0]front[i][0] = 0}// 创建一维存所有要做子集的点。numName := make([]int, nums) //生成1，2，3for i := 1; i <= nums; i++ {numName[i-1] = i}numName = numName[:len(numName)-1]subset := subsets(numName) //生成子集sort.Slice(subset, func(i, j int) bool {return len(subset[i]) < len(subset[j])})fmt.Println(subset)
·······

        这里前面几个变量我不加以赘述，简单的创建和初始化（如果你用的其他语言写这道题，相信你能做到这个），这里说一下最小子集的寻找，我参考了LeetCode上一道题（力扣上的子集问题）以及CSDN上相关博主给出的解答（子集问题的GO语言其中一解，这里选择解题代码并未考虑时间及空间复杂度，大家可以试着采用leetcode上更快更好的代码），代码大意是采用了深度优先搜索的方式进行生成，下面是本题借用函数：

//来自于本站其他用户博文
func subsets(nums []int) [][]int {l := list.New()result := list.New()for i := 0; i <= len(nums); i++ {dfs(nums, 0, i, l, result)}arr := make([][]int, result.Len())k := 0for e := result.Front(); e != nil; e = e.Next(){curl := e.Value.(*list.List)arr[k] = make([]int, curl.Len())k++}i := 0;for e := result.Front(); e != nil; e = e.Next() {curl := e.Value.(*list.List)j := 0for p := curl.Front(); p != nil; p = p.Next() {arr[i][j] = p.Value.(int)j++}i++;}return arr
}func dfs(nums []int, start int, len int, l *list.List, result *list.List) {if start == len {a := list.New()for e := l.Front(); e != nil; e = e.Next() {a.PushBack(e.Value)}result.PushBack(a)return}for i := start; i < len; i++ {l.PushBack(nums[i])dfs(nums, i+1, len, l, result)b := l.Back()l.Remove(b)}
}

         之后就是对得到的子集排序，因为上面代码跑出来的子集并非是有序的。

        这样便得到了计算所需的所有变量。

2.计算 

        计算这个方面可以参考书中的伪代码，值得注意的是在判断大小的一些地方需要改变传参。大家可通过书中样例矩阵以及表格进行相关推导，不难发现第0列被初始化，第1到3列依靠0列更新，3到5列依靠1到3列更新，第七列特别只有第0行需要更新，而我们的最终结果需要的表格的横向表头的二维数组长这样：

        所以，我们不难发现，它的长度似乎和计算有一些联系：在遍历{1}的时候，填充2和3，依靠0到1的数值，所以计算d[2][1] = arc[2][1] + d[1][0]，d[3][1] = arc[3][1] + d[1][0]。依照此种规律，便可结合下文的代码内容分析：

	//下面才刚刚开始tspfor j := 1; j < len(subset); j++ { //以d中的列开始扫描，也就是上面的subset（V），表头内容for i := 1; i < nums; i++ { //挨个查找看看那个数字没在V的里面，真没在就去赋值，正在查找横表头有无judge := falsefor _, theNum := range subset[j] {if theNum == i {judge = true //在的在的，就不用操作了continue}}if judge == false { //wok，真没在var edge int = 1314for _, theNum := range subset[j] { //theNum，表头中含有的内容temp := arc[i][theNum] + d[theNum][j-theNum-len(subset[j])+1]if temp < edge {edge = tempd[i][j] = edgefront[i][j] = theNum}//d[i][j] = int(math.Min(float64(d[i][j]), float64(arc[i][theNum]+d[theNum][j-1])))}}}}//求解最终结果TheLastEdge := 520for k := 1; k < nums; k++ {temp := arc[0][k] + d[k][LengthOfd-1-int(math.Pow(2, float64(k-1)))]if temp < TheLastEdge {TheLastEdge = tempd[0][LengthOfd-1] = TheLastEdgefront[0][LengthOfd-1] = k}}

         最后求解最后的那个框，例如本题目就是{1,2,3}下面的第0行的内容。和上面写到的，平常的点求该问题的解法如出一辙，这里并不是很好理解，计算公式甚至可以理解成是我在纯粹的找规律凑数。值得注意的是，在计算的同时front矩阵也在记录他们的上一个点（前驱），这个在后面输出发挥着重要作用。

3.输出

        这里要注意以下路径是怎么打印出来的。i是直接指向最后更新的那个框框的纵坐标，j是横坐标，count用来计数确保不会在移动的途中迷路，根据书上表格，我们并不难发现下面的规律，j直接取front中的值会直接得到前驱节点的值，那么我们就应该在j行去定位这个前驱的下一个前驱，那么我们就只差寻找这个地方的纵坐标，相当巧合的是，现在的i减去现在的j的值再减去这次遍历计数器的值，正好到了我们要寻找的那个地方。（这里在草稿纸上列出我们需要加起来的点，恰好可以得出普适的规律）。

	fmt.Print("TSP最短的路径是：", "0")//打印路径for i, j, count := LengthOfd-1, 0, 0; ; {j = front[j][i]i = i - j - countfmt.Print("->", j)count++if i <= 0 {fmt.Println("->0")break}}//画表for i := 0; i < len(subset); i++ {str := fmt.Sprint(subset[i])fmt.Printf("%10s", str)//fmt.Print(subset[i], "\t\t")}fmt.Println()for i := 0; i < nums; i++ {for j := 0; j < LengthOfd; j++ {bye := "-"if d[i][j] == 2004 {fmt.Printf("%10s", bye)} else {fmt.Printf("%10d", d[i][j])}}fmt.Println()}fmt.Println("最短路径是：", d[0][LengthOfd-1])

        大致就是这样得到了最后结果，然后再对齐一下表格。

---

四、代码

// TSP Problem
// Created By DDD on 2024.5.25
//package mainimport ("container/list""fmt""math""sort"
)func subsets(nums []int) [][]int {l := list.New()result := list.New()for i := 0; i <= len(nums); i++ {dfs(nums, 0, i, l, result)}arr := make([][]int, result.Len())k := 0for e := result.Front(); e != nil; e = e.Next() {curl := e.Value.(*list.List)arr[k] = make([]int, curl.Len())k++}i := 0for e := result.Front(); e != nil; e = e.Next() {curl := e.Value.(*list.List)j := 0for p := curl.Front(); p != nil; p = p.Next() {arr[i][j] = p.Value.(int)j++}i++}return arr
}func dfs(nums []int, start int, len int, l *list.List, result *list.List) {if start == len {a := list.New()for e := l.Front(); e != nil; e = e.Next() {a.PushBack(e.Value)}result.PushBack(a)return}for i := start; i < len; i++ {l.PushBack(nums[i])dfs(nums, i+1, len, l, result)b := l.Back()l.Remove(b)}
}func main() {var nums int// 读取二维数组的行数和列数fmt.Print("请输入（城市）点数: ")fmt.Scanln(&nums)// 初始化一个二维数组arc := make([][]int, nums)for i := range arc {arc[i] = make([]int, nums)}// 从控制台读取二维数组的值fmt.Println("请输入二维数组的元素，每行输入完毕后按回车键：")for i := 0; i < nums; i++ {for j := 0; j < nums; j++ {var putin intfmt.Scanf("%d", &putin)if putin == 0 {putin = 2004}arc[i][j] = putin}fmt.Scanln() // 跳过每行输入后的换行符}var LengthOfd int = int(math.Pow(2, float64(nums-1)))//下面的这个d就是那个动态规划法的表d := make([][]int, nums)for i := range d {d[i] = make([]int, LengthOfd)}//同样设置一个跟d一样的矩阵，来存最近的前驱front := make([][]int, nums)for i := range front {front[i] = make([]int, LengthOfd)}//初始化设置成很大的for i := range d {for j := range d[i] {d[i][j] = 2004front[i][j] = 2004}}for i := 0; i < nums; i++ {d[i][0] = arc[i][0]front[i][0] = 0}// 创建一维存所有要做子集的点。numName := make([]int, nums) //生成1，2，3for i := 1; i <= nums; i++ {numName[i-1] = i}numName = numName[:len(numName)-1]subset := subsets(numName) //生成子集sort.Slice(subset, func(i, j int) bool {return len(subset[i]) < len(subset[j])})fmt.Println(subset)//下面才刚刚开始tspfor j := 1; j < len(subset); j++ { //以d中的列开始扫描，也就是上面的subset（V），表头内容for i := 1; i < nums; i++ { //挨个查找看看那个数字没在V的里面，真没在就去赋值，正在查找横表头有无judge := falsefor _, theNum := range subset[j] {if theNum == i {judge = true //在的在的，就不用操作了continue}}if judge == false { //wok，真没在var edge int = 1314for _, theNum := range subset[j] { //theNum，表头中含有的内容temp := arc[i][theNum] + d[theNum][j-theNum-len(subset[j])+1]if temp < edge {edge = tempd[i][j] = edgefront[i][j] = theNum}//d[i][j] = int(math.Min(float64(d[i][j]), float64(arc[i][theNum]+d[theNum][j-1])))}}}}//求解最终结果TheLastEdge := 520for k := 1; k < nums; k++ {temp := arc[0][k] + d[k][LengthOfd-1-int(math.Pow(2, float64(k-1)))]if temp < TheLastEdge {TheLastEdge = tempd[0][LengthOfd-1] = TheLastEdgefront[0][LengthOfd-1] = k}}fmt.Print("TSP最短的路径是：", "0")//打印路径for i, j, count := LengthOfd-1, 0, 0; ; {j = front[j][i]i = i - j - countfmt.Print("->", j)count++if i <= 0 {fmt.Println("->0")break}}//画表for i := 0; i < len(subset); i++ {str := fmt.Sprint(subset[i])fmt.Printf("%10s", str)//fmt.Print(subset[i], "\t\t")}fmt.Println()for i := 0; i < nums; i++ {for j := 0; j < LengthOfd; j++ {bye := "-"if d[i][j] == 2004 {fmt.Printf("%10s", bye)} else {fmt.Printf("%10d", d[i][j])}}fmt.Println()}fmt.Println("最短路径是：", d[0][LengthOfd-1])
}/*
4
0 3 6 7
5 0 2 3
6 4 0 2
3 7 5 0
*/

---

五、参考文献

 算法分析与设计课程实验——TSP问题与01背包问题的动态规划算法实现-CSDN博客

---

Go的主函数不需要写return