[已解决]用python的hill climbing算法求解最短距离

盐焗小星球

Given a set of n cities, the goal is to find the shortest distance that a travelling salesman must travel in order to visit all the cities and return to the starting point. If we are to solve the problem using Hill Climbing algorithm, suggest a suitable initial solution for this problem, and implement the Cost function that returns the total distance for a given solution.
给定一组n个城市，目标是找到一个旅行推销员必须走的最短距离，以便访问所有的城市并返回起点。如果我们要用Hill Climbing algorithm算法来解决这个问题，请为这个问题提出一个合适的初始解决方案并实现cost function以返回给定解决方案的总距离。

最佳答案

月排行榜 / 总排行榜

sfqxx

2023-5-21 22:29:01

Hill Climbing（山峰爬升）算法的一个合适的初始解决方案是生成一个城市索引的随机排列，并将其作为初始解决方案返回。

这是Python中Cost函数的一种实现：

1. 
   
2. import math
   
3. 
   
4. def distance(x1, y1, x2, y2):
   
5.     return math.sqrt((x1-x2)**2 + (y1-y2)**2)
   
6. 
   
7. def cost(solution, distances):
   
8.     total_distance = 0
   
9.     n = len(solution)
   
10.    
    
11.     for i in range(n):
    
12.         current_city = solution[i]
    
13.         next_city = solution[(i+1)%n] # 循环遍历城市
    
14.         total_distance += distances[current_city][next_city]
    
15.    
    
16.     return total_distance

复制代码

要使用此函数，`solution` 是表示城市索引的排列列表(从 0 到 n-1)，而 `distances` 则是包含城市之间成对距离的二维列表。例如，如果有三个坐标为(0,0), (0,1) 和 (1,1) 的城市，则 `distances` 矩阵如下：

1. 
   
2. distances = [
   
3.     [0, 1, math.sqrt(2)],
   
4.     [1, 0, 1],
   
5.     [math.sqrt(2), 1, 0]
   
6. ]

复制代码

其中 `distance [0] [1]`是城市0和1之间的距离(为1)，`distance [0] [2]`是城市0和2之间的距离(即sqrt (2))。

跳转到最佳答案楼层

sfqxx

Hill Climbing（山峰爬升）算法的一个合适的初始解决方案是生成一个城市索引的随机排列，并将其作为初始解决方案返回。

这是Python中Cost函数的一种实现：

1. 
   
2. import math
   
3. 
   
4. def distance(x1, y1, x2, y2):
   
5.     return math.sqrt((x1-x2)**2 + (y1-y2)**2)
   
6. 
   
7. def cost(solution, distances):
   
8.     total_distance = 0
   
9.     n = len(solution)
   
10.    
    
11.     for i in range(n):
    
12.         current_city = solution[i]
    
13.         next_city = solution[(i+1)%n] # 循环遍历城市
    
14.         total_distance += distances[current_city][next_city]
    
15.    
    
16.     return total_distance

复制代码

要使用此函数，`solution` 是表示城市索引的排列列表(从 0 到 n-1)，而 `distances` 则是包含城市之间成对距离的二维列表。例如，如果有三个坐标为(0,0), (0,1) 和 (1,1) 的城市，则 `distances` 矩阵如下：

1. 
   
2. distances = [
   
3.     [0, 1, math.sqrt(2)],
   
4.     [1, 0, 1],
   
5.     [math.sqrt(2), 1, 0]
   
6. ]

复制代码

其中 `distance [0] [1]`是城市0和1之间的距离(为1)，`distance [0] [2]`是城市0和2之间的距离(即sqrt (2))。