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

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

    一、前言 

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

     二、问题

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

    三、代码分析

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

    1.输入

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

    1.  ·········
    2.     var nums int
    3. 	// 读取二维数组的行数和列数
    4. 	fmt.Print("请输入（城市）点数: ")
    5. 	fmt.Scanln(&nums)
    6. 	// 初始化一个二维数组
    7. 	arc := make([][]int, nums)
    8. 	for i := range arc {
    9. 		arc[i] = make([]int, nums)
    10. 	}
    11. 	// 从控制台读取二维数组的值
    12. 	fmt.Println("请输入二维数组的元素，每行输入完毕后按回车键：")
    13. 	for i := 0; i < nums; i++ {
    14. 		for j := 0; j < nums; j++ {
    15. 			var putin int
    16. 			fmt.Scanf("%d", &putin)
    17. 			if putin == 0 {
    18. 				putin = 2004
    19. 			}
    20. 			arc[i][j] = putin
    21. 		}
    22. 		fmt.Scanln() // 跳过每行输入后的换行符
    23. 	}
    24. 	var LengthOfd int = int(math.Pow(2, float64(nums-1)))
    25. 	//下面的这个d就是那个动态规划法的表
    26. 	d := make([][]int, nums)
    27. 	for i := range d {
    28. 		d[i] = make([]int, LengthOfd)
    29. 	}
    30. 	//同样设置一个跟d一样的矩阵，来存最近的前驱
    31. 	front := make([][]int, nums)
    32. 	for i := range front {
    33. 		front[i] = make([]int, LengthOfd)
    34. 	}
    35. 	//初始化设置成很大的
    36. 	for i := range d {
    37. 		for j := range d[i] {
    38. 			d[i][j] = 2004
    39. 			front[i][j] = 2004
    40. 		}
    41. 	}
    42. 	for i := 0; i < nums; i++ {
    43. 		d[i][0] = arc[i][0]
    44. 		front[i][0] = 0
    45. 	}
    46. 	// 创建一维存所有要做子集的点。
    47. 	numName := make([]int, nums) //生成1，2，3
    48. 	for i := 1; i <= nums; i++ {
    49. 		numName[i-1] = i
    50. 	}
    51. 	numName = numName[:len(numName)-1]
    52. 	subset := subsets(numName) //生成子集
    53. 	sort.Slice(subset, func(i, j int) bool {
    54. 		return len(subset[i]) < len(subset[j])
    55. 	})
    56. 	fmt.Println(subset)
    57. ·······

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

    1. //来自于本站其他用户博文
    2. func subsets(nums []int) [][]int {
    3.  
    4.     l := list.New()
    5.     result := list.New()
    6.     
    7.     for i := 0; i <= len(nums); i++ {
    8.          dfs(nums, 0, i, l, result)
    9.     }
    10.    
    11.     arr := make([][]int, result.Len())
    12.     k := 0
    13.     for e := result.Front(); e != nil; e = e.Next(){
    14.         curl := e.Value.(*list.List)
    15.         arr[k] = make([]int, curl.Len())
    16.         k++
    17.     }
    18.  
    19.     i := 0;
    20.     for e := result.Front(); e != nil; e = e.Next() {
    21.         curl := e.Value.(*list.List)
    22.         j := 0
    23.         for p := curl.Front(); p != nil; p = p.Next() {
    24.            arr[i][j] = p.Value.(int)
    25.            j++
    26.         }
    27.         
    28.         i++;
    29.     }
    30.  
    31.     return arr
    32. }
    33.  
    34. func dfs(nums []int, start int, len int, l *list.List, result *list.List) {
    35.  
    36.     if start == len {
    37.         a := list.New()
    38.         for e := l.Front(); e != nil; e = e.Next() {
    39.             a.PushBack(e.Value)
    40.         }
    41.         result.PushBack(a)
    42.         return
    43.     }
    44.  
    45.     for i := start; i < len; i++ {
    46.         l.PushBack(nums[i])
    47.         dfs(nums, i+1, len, l, result)
    48.         b := l.Back()
    49.         l.Remove(b)
    50.     }
    51. }

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

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

    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]。依照此种规律，便可结合下文的代码内容分析：

    1. 	//下面才刚刚开始tsp
    2. 	for j := 1; j < len(subset); j++ { //以d中的列开始扫描，也就是上面的subset（V），表头内容
    3. 		for i := 1; i < nums; i++ { //挨个查找看看那个数字没在V的里面，真没在就去赋值，正在查找横表头有无
    4. 			judge := false
    5. 			for _, theNum := range subset[j] {
    6. 				if theNum == i {
    7. 					judge = true //在的在的，就不用操作了
    8. 					continue
    9. 				}
    10. 			}
    11. 			if judge == false { //wok，真没在
    12.  
    13. 				var edge int = 1314
    14.  
    15. 				for _, theNum := range subset[j] { //theNum，表头中含有的内容
    16. 					temp := arc[i][theNum] + d[theNum][j-theNum-len(subset[j])+1]
    17. 					if temp < edge {
    18. 						edge = temp
    19. 						d[i][j] = edge
    20. 						front[i][j] = theNum
    21. 					}
    22. 					//d[i][j] = int(math.Min(float64(d[i][j]), float64(arc[i][theNum]+d[theNum][j-1])))
    23. 				}
    24. 			}
    25. 		}
    26. 	}
    27. 	//求解最终结果
    28. 	TheLastEdge := 520
    29. 	for k := 1; k < nums; k++ {
    30. 		temp := arc[0][k] + d[k][LengthOfd-1-int(math.Pow(2, float64(k-1)))]
    31. 		if temp < TheLastEdge {
    32. 			TheLastEdge = temp
    33. 			d[0][LengthOfd-1] = TheLastEdge
    34. 			front[0][LengthOfd-1] = k
    35. 		}
    36. 	}

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

    3.输出

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

    1. 	fmt.Print("TSP最短的路径是：", "0")
    2. 	//打印路径
    3. 	for i, j, count := LengthOfd-1, 0, 0; ; {
    4. 		j = front[j][i]
    5. 		i = i - j - count
    6. 		fmt.Print("->", j)
    7. 		count++
    8. 		if i <= 0 {
    9. 			fmt.Println("->0")
    10. 			break
    11. 		}
    12. 	}
    13. 	//画表
    14. 	for i := 0; i < len(subset); i++ {
    15. 		str := fmt.Sprint(subset[i])
    16. 		fmt.Printf("%10s", str)
    17. 		//fmt.Print(subset[i], "\t\t")
    18. 	}
    19. 	fmt.Println()
    20. 	for i := 0; i < nums; i++ {
    21. 		for j := 0; j < LengthOfd; j++ {
    22. 			bye := "-"
    23. 			if d[i][j] == 2004 {
    24. 				fmt.Printf("%10s", bye)
    25. 			} else {
    26. 				fmt.Printf("%10d", d[i][j])
    27. 			}
    28.  
    29. 		}
    30. 		fmt.Println()
    31. 	}
    32.  
    33. 	fmt.Println("最短路径是：", d[0][LengthOfd-1])

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

    四、代码

    1. // TSP Problem
    2. // Created By DDD on 2024.5.25
    3. //
    4.  
    5. package main
    6.  
    7. import (
    8. 	"container/list"
    9. 	"fmt"
    10. 	"math"
    11. 	"sort"
    12. )
    13.  
    14. func subsets(nums []int) [][]int {
    15.  
    16. 	l := list.New()
    17. 	result := list.New()
    18.  
    19. 	for i := 0; i <= len(nums); i++ {
    20. 		dfs(nums, 0, i, l, result)
    21. 	}
    22.  
    23. 	arr := make([][]int, result.Len())
    24. 	k := 0
    25. 	for e := result.Front(); e != nil; e = e.Next() {
    26. 		curl := e.Value.(*list.List)
    27. 		arr[k] = make([]int, curl.Len())
    28. 		k++
    29. 	}
    30.  
    31. 	i := 0
    32. 	for e := result.Front(); e != nil; e = e.Next() {
    33. 		curl := e.Value.(*list.List)
    34. 		j := 0
    35. 		for p := curl.Front(); p != nil; p = p.Next() {
    36. 			arr[i][j] = p.Value.(int)
    37. 			j++
    38. 		}
    39.  
    40. 		i++
    41. 	}
    42.  
    43. 	return arr
    44. }
    45.  
    46. func dfs(nums []int, start int, len int, l *list.List, result *list.List) {
    47.  
    48. 	if start == len {
    49. 		a := list.New()
    50. 		for e := l.Front(); e != nil; e = e.Next() {
    51. 			a.PushBack(e.Value)
    52. 		}
    53. 		result.PushBack(a)
    54. 		return
    55. 	}
    56.  
    57. 	for i := start; i < len; i++ {
    58. 		l.PushBack(nums[i])
    59. 		dfs(nums, i+1, len, l, result)
    60. 		b := l.Back()
    61. 		l.Remove(b)
    62. 	}
    63. }
    64.  
    65. func main() {
    66. 	var nums int
    67. 	// 读取二维数组的行数和列数
    68. 	fmt.Print("请输入（城市）点数: ")
    69. 	fmt.Scanln(&nums)
    70. 	// 初始化一个二维数组
    71. 	arc := make([][]int, nums)
    72. 	for i := range arc {
    73. 		arc[i] = make([]int, nums)
    74. 	}
    75. 	// 从控制台读取二维数组的值
    76. 	fmt.Println("请输入二维数组的元素，每行输入完毕后按回车键：")
    77. 	for i := 0; i < nums; i++ {
    78. 		for j := 0; j < nums; j++ {
    79. 			var putin int
    80. 			fmt.Scanf("%d", &putin)
    81. 			if putin == 0 {
    82. 				putin = 2004
    83. 			}
    84. 			arc[i][j] = putin
    85. 		}
    86. 		fmt.Scanln() // 跳过每行输入后的换行符
    87. 	}
    88. 	var LengthOfd int = int(math.Pow(2, float64(nums-1)))
    89. 	//下面的这个d就是那个动态规划法的表
    90. 	d := make([][]int, nums)
    91. 	for i := range d {
    92. 		d[i] = make([]int, LengthOfd)
    93. 	}
    94. 	//同样设置一个跟d一样的矩阵，来存最近的前驱
    95. 	front := make([][]int, nums)
    96. 	for i := range front {
    97. 		front[i] = make([]int, LengthOfd)
    98. 	}
    99. 	//初始化设置成很大的
    100. 	for i := range d {
    101. 		for j := range d[i] {
    102. 			d[i][j] = 2004
    103. 			front[i][j] = 2004
    104. 		}
    105. 	}
    106. 	for i := 0; i < nums; i++ {
    107. 		d[i][0] = arc[i][0]
    108. 		front[i][0] = 0
    109. 	}
    110. 	// 创建一维存所有要做子集的点。
    111. 	numName := make([]int, nums) //生成1，2，3
    112. 	for i := 1; i <= nums; i++ {
    113. 		numName[i-1] = i
    114. 	}
    115. 	numName = numName[:len(numName)-1]
    116. 	subset := subsets(numName) //生成子集
    117. 	sort.Slice(subset, func(i, j int) bool {
    118. 		return len(subset[i]) < len(subset[j])
    119. 	})
    120. 	fmt.Println(subset)
    121. 	//下面才刚刚开始tsp
    122. 	for j := 1; j < len(subset); j++ { //以d中的列开始扫描，也就是上面的subset（V），表头内容
    123. 		for i := 1; i < nums; i++ { //挨个查找看看那个数字没在V的里面，真没在就去赋值，正在查找横表头有无
    124. 			judge := false
    125. 			for _, theNum := range subset[j] {
    126. 				if theNum == i {
    127. 					judge = true //在的在的，就不用操作了
    128. 					continue
    129. 				}
    130. 			}
    131. 			if judge == false { //wok，真没在
    132.  
    133. 				var edge int = 1314
    134.  
    135. 				for _, theNum := range subset[j] { //theNum，表头中含有的内容
    136. 					temp := arc[i][theNum] + d[theNum][j-theNum-len(subset[j])+1]
    137. 					if temp < edge {
    138. 						edge = temp
    139. 						d[i][j] = edge
    140. 						front[i][j] = theNum
    141. 					}
    142. 					//d[i][j] = int(math.Min(float64(d[i][j]), float64(arc[i][theNum]+d[theNum][j-1])))
    143. 				}
    144. 			}
    145. 		}
    146. 	}
    147. 	//求解最终结果
    148. 	TheLastEdge := 520
    149. 	for k := 1; k < nums; k++ {
    150. 		temp := arc[0][k] + d[k][LengthOfd-1-int(math.Pow(2, float64(k-1)))]
    151. 		if temp < TheLastEdge {
    152. 			TheLastEdge = temp
    153. 			d[0][LengthOfd-1] = TheLastEdge
    154. 			front[0][LengthOfd-1] = k
    155. 		}
    156. 	}
    157.  
    158. 	fmt.Print("TSP最短的路径是：", "0")
    159. 	//打印路径
    160. 	for i, j, count := LengthOfd-1, 0, 0; ; {
    161. 		j = front[j][i]
    162. 		i = i - j - count
    163. 		fmt.Print("->", j)
    164. 		count++
    165. 		if i <= 0 {
    166. 			fmt.Println("->0")
    167. 			break
    168. 		}
    169. 	}
    170. 	//画表
    171. 	for i := 0; i < len(subset); i++ {
    172. 		str := fmt.Sprint(subset[i])
    173. 		fmt.Printf("%10s", str)
    174. 		//fmt.Print(subset[i], "\t\t")
    175. 	}
    176. 	fmt.Println()
    177. 	for i := 0; i < nums; i++ {
    178. 		for j := 0; j < LengthOfd; j++ {
    179. 			bye := "-"
    180. 			if d[i][j] == 2004 {
    181. 				fmt.Printf("%10s", bye)
    182. 			} else {
    183. 				fmt.Printf("%10d", d[i][j])
    184. 			}
    185.  
    186. 		}
    187. 		fmt.Println()
    188. 	}
    189.  
    190. 	fmt.Println("最短路径是：", d[0][LengthOfd-1])
    191. }
    192.  
    193. /*
    194. 4
    195. 0 3 6 7
    196. 5 0 2 3
    197. 6 4 0 2
    198. 3 7 5 0
    199. */

    五、参考文献

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

    Go的主函数不需要写return

  • 相关阅读:
    一条 SQL 语句是如何执行的
    Skywalking全部
    【MySQL】视图操作
    一文理解 Docker 的 ENTRYPOINT、CMD 和 k8s 的 command、args
    部署LVS-DR群集
    浅析MVC、MVP、MMVM 架构
    用C++ Thread实现简单的socket多线程通信
    ADB命令
    产品经理应具备的能力
    DVWA-XSS（DOM）Low/Medium/High低中高级别
  • 原文地址：https://blog.csdn.net/FellAveal/article/details/139202813