CosmosNing的个人博客

探索·好奇

0%

怎样求解难解决问题?

发表于 更新于 分类于
本文字数： 4.4k 阅读时长 ≈ 4 分钟
从旅行商问题说起

引入

cover

在之前的文章中，我们遇到的问题，其对应的算法都在我们所能容忍的时间给出结果（这些问题被称作“可解决问题”）。但是，对于有些问题，通过传统的解决办法，我们甚至在有生之年也得不到结果（这些问题被称作“难解决问题”）。在这些问题中，一个比较著名的便是今天我们要一起探讨的旅行商问题（Travelling salesman problem ，简写为 TSP ）。

旅行商问题

维基百科中，给出了旅行商问题的描述。具体如下：

The travelling salesman problem (TSP) asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city and returns to the origin city?" 1

也就是说，如果已知一个城市列表以及每一对城市之间的距离，如何找到一条回路，这条回路到达过列表中的每一个城市并且总路径长度最短？

碰到这个问题，我想你脑中瞬间蹦出的解决方案就是穷举。下面，我们简单看看针对这个问题的穷举解法。

传统解法——穷举

算法简述

这个算法的总体的思路就是，枚举城市列表中的每一个排列，计算其路径长度，和当前找到的最短路径进行比较。如果新找到的排列方案的路径更短，那么更新最短路径和方案。当城市列表中所有的排列都枚举完成后，返回最短的排列方案和最短路径即可。

利用伪码描述，具体如下：

1
2
3
4
5
6
7
8
9
10
11
function TSP_Exhaustion(city_list)
    shortest_path = NULL               // 记录回路方案，初始为NULL  
    shortest_dist = ∞                  // 记录回路方案中最短路径长度,初始化为无穷大
    
    foreach permutation in city_list   // permutation表示city_list中的一个排列
        dist = CalcDist(permutation)   // 计算当前排列方案下的路径长度
        if dist < shortest_path        // 如果找到更小的，更新方案和最短路径
            shortest_dist = dist
            shortest_path = permutation
    
    return shortest_path, shortest_dist//返回结果

复杂度分析

仔细观察上述的伪码描述，我们很容易知道，该算法最耗时间的部分便是枚举城市列表中的排列部分。对于一个容量大小为 N 的城市列表，它所有的排列为 N! 。所以，该算法的时间复杂度为 O( N !) 。

这样的时间复杂度是什么概念？如果计算机可以 1秒 处理一个上述的排列，那么针对不同的数据量 N ,

有如下表格。

数据量 N 计算量 花费时间
1 1！= 1 1秒
10 10！= 3628800 42天
100 100！= 9.33262×10^157 2.95935×10^150年

由此可见，随着数据量的增大，花费的时间以惊人的速度增长着。数据量为10时，这个解决问题的速度，我们已经无法容忍，更别提100了。

对于我们来说，时间是非常宝贵的资源。那么，如何在较少的时间内，获得这个问题的答案呢？

在这类问题中，前人经过不断尝试，放弃了能获得精确解但十分耗时的算法，转而投向更节省时间的近似算法。其中一种算法便是接下来要聊到的贪心算法。

近似逼近——贪心算法

贪心算法是一种近似算法，算法的每一次迭代选取的都是当前局部最优的情况。它试图通过每一次的贪心选择，从局部最优解逐步逼近全局最优解。

贪心算法有两个关键部分：

  1. 找到贪心选择的策略
  2. 依据第一步设定的贪心策略在一个有限集上不断迭代

依据上两个关键部分，我们能够利用贪心算法解决一些 难解决问题 。

算法简述

对于旅行商问题，我们可以先随机选取一个城市作为起点，每次选取未被访问的并且路径最短的城市作为旅行商的下一站。以这个策略在城市列表中进行迭代，当所有城市都访问过后，就可以获得一个旅行商问题的看起来还不错的解。

其伪码描述如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function TSP_Greedy(city_list)
    visited = NULL                      // 存放已经访问过的城市，初始化为NULL
    dist = 0                            // 记录贪心算法找到的近似最短路径长度
    
    rand_i = rand(city_list.length)     // 随机选取一个城市列表长度范围内的下标
    start_city = city_list[rand_i]      // 将其作为起点
    visited.add(start_city)             // 标记其已被访问过
    city_current = start_city           // 当前旅行商所在的城市
    
    // 寻找下一个没有访问过的并且从当前城市出发路径最短的下一个城市
    city_next = FindNextShortestCity(start_city, visited)
    
    while city_next != NULL             // 所有的城市还未访问完
        // 计算路径长度
        dist += CalcDistBetweenCities(city_current, city_next)
        city_current = city_next        // 旅行商到达下一个城市
        visited.add(city_current)       // 标记已被访问过
        // 寻找下一个城市
        city_next = FindNextShortestCity(city_current, visited)
    
    return visited, dist                // 返回结果

复杂度分析

假设数据量为 N ，while 循环大约消耗 N 步，函数 find_next_shortest_city 也会消耗 N 步，所以贪心算法在 TSP 问题中的时间复杂度为 \(O(N^{2})\) 。

TSP贪心算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
import random

# 城市列表
cities = ['A', 'B', 'C', 'D', 'E']

# 保存任意两个城市的距离
costs = {}
costs['A'] = {'B': 1, 'C': 2, 'D': 3, 'E': 4}
costs['B'] = {'A': 1, 'C': 2, 'D': 3, 'E': 4}
costs['C'] = {'A': 1, 'B': 2, 'D': 3, 'E': 4}
costs['D'] = {'A': 1, 'B': 2, 'C': 3, 'E': 4}
costs['E'] = {'A': 1, 'B': 2, 'C': 3, 'D': 4}


def find_next_shortest_city(src, searched):
    """
    寻找下一个没有访问过的并且从当前城市出发路径最短的下一个城市
    :param src: 当前的起点
    :param searched: 已被访问过的城市集合
    :return: 符合要求的下一个城市
    """
    shortest_city = None
    shortest_dist = float('inf')
    for city, dist in costs[src].items():
        if dist < shortest_dist and city not in searched:
            shortest_city = city
            shortest_dist = dist

    return shortest_city


def tsp_greedy(city_list):
    """
    利用贪心算法近似解决TSP问题
    :param city_list: 城市列表
    :return: 访问回路方案（列表），最小代价（整数）
    """
    visited = []                            # 存放已经访问过的城市，初始化为NULL
    dist = 0                                # 记录贪心算法找到的近似最短路径长度

    # 随机选取一个城市列表长度范围内的下标
    rand_i = random.randint(0, len(city_list) - 1)
    start_city = city_list[rand_i]          # 将其作为起点
    visited.append(start_city)              # 标记其已被访问过
    city_current = start_city               # 当前旅行商所在的城市

    # 寻找下一个没有访问过的并且从当前城市出发路径最短的下一个城市
    city_next = find_next_shortest_city(start_city, visited)

    while city_next is not None:            # 所有的城市还未访问
        # 计算路径长度
        dist += costs[city_current][city_next]
        city_current = city_next            # 旅行商到达下一个城市
        visited.append(city_current)        # 标记已被访问过
        # 寻找下一个城市
        city_next = find_next_shortest_city(city_current, visited)

    return visited, dist


if __name__ == "__main__":
    v, d = tsp_greedy(cities)

    print("回路路径方案：")
    print("->".join(v))
    print("路径长度：")
    print(d)

总结

今天我和你一起了解到 旅行商问题 这类难解决问题，这类问题通常难以在可容忍的时间内获得其精确解。为了快速获得一个可能的解，可以利用近似算法逼近精确解。进一步，我们了解到贪心算法——一种近似算法，并实现了用于解决 TSP 的贪心算法。

最后，我将本文的要点总结如下：

  1. 旅行商问题这类难解决问题可以通过近似算法获得近似解
  2. 近似算法中，有一种常见的算法便是贪心算法
  3. 贪心算法有两个关键部分：
    1. 找到贪心选择的策略
    2. 依据第一步设定的贪心策略在一个有限集上不断迭代

  1. https://en.wikipedia.org/wiki/Travelling_salesman_problem↩︎