算法图解阅读笔记——第四曲（狄克斯特拉算法和贪婪算法）

系统管理员 2021-05-12 11:50 609阅读 0赞

#### 目录结构 ####

第7章 狄克斯特拉算法

第8章 贪婪算法

--------------------

#### 正文 ####

## 狄克斯特拉算法 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDkxMjE1OQ_size_16_color_FFFFFF_t_70_pic_center]

*  图A是使用广度优先搜索算法计算最短路径的图结构（非加权图）
    
    ——**在非加权图中计算最短路径，可使用广度优先搜索**
 *  图B是使用狄克斯特拉算法计算最短路径的图结构（加权图）
    
    ——**在加权图中计算最短路径，可使用狄克斯特拉算法**

### 什么是狄克斯特拉算法 ###

*  狄克斯特拉算法是一种在**加权图算法**，目的是为了**解决加权图中最短路径的问题**，只适用于有向无环图，而且图中的权值不能为负。

### 使用狄克斯特拉算法 ###

*  算法步骤：
    
    1.  找出"最便宜"的节点，即可在最短时间内到达的节点。
    2.  更新该节点的邻居开销（从起点到该节点各邻居的开销）。
    3.  重复①②这个过程，直至对图中的每个节点都这样做了。
    4.  计算得到最终路径

### 实现狄克斯特拉算法 ###

*  使用下图来实现狄克斯特拉算法
    
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDkxMjE1OQ_size_16_color_FFFFFF_t_70_pic_center 1]

def find_lowest_cost_node(costs_dict):
        """ 找开销最小的路径 """
        lowest_cost = float('inf')
        lowest_cost_node = None
        for node in costs_dict:
            cost = costs_dict[node]
            if cost < lowest_cost and node not in processed_node:
                lowest_cost = cost
                lowest_cost_node = node
        return lowest_cost_node
    
    
    graph = { }    # 创建图
    
    graph['start'] = { }
    graph['start']['a'] = 6
    graph['start']['b'] = 2
    
    graph['a'] = { }
    graph['a']['end'] = 1
    
    graph['b'] = { }
    graph['b']['a'] = 3
    graph['b']['end'] = 5
    
    graph['end'] = { }
    
    print('初始化graph：', graph)
    
    infinity = float('inf')
    
    costs = { }  # 开销图
    costs['a'] = 6
    costs['b'] = 2
    costs['end'] = infinity
    print('初始化costs：', costs)
    
    parents = { }   # 父节点图
    parents['a'] = 'start'
    parents['b'] = 'start'
    parents['end'] = None
    print('初始化parents：', parents)
    
    processed_node = []
    
    node = find_lowest_cost_node(costs)
    while node is not None:
        cost = costs[node]
        neighbors = graph[node]
    
        for neighbor in neighbors.keys():
            new_cost = cost + neighbors[neighbor]
            if costs[neighbor] > new_cost:
                costs[neighbor] = new_cost
                parents[neighbor] = node
    
        processed_node.append(node)
        node = find_lowest_cost_node(costs)
    
    
    print('狄克斯特拉算法计算costs：', costs)
    print('狄克斯特拉算法计算parents：', parents)
    
    # Out
    # 初始化graph： {'start': {'a': 6, 'b': 2}, 'a': {'end': 1}, 'b': {'a': 3, 'end': 5}, 'end': {}}
    # 初始化costs： {'a': 6, 'b': 2, 'end': inf}
    # 初始化parents： {'a': 'start', 'b': 'start', 'end': None}
    # 狄克斯特拉算法计算costs： {'a': 5, 'b': 2, 'end': 6}
    # 狄克斯特拉算法计算parents： {'a': 'b', 'b': 'start', 'end': 'a'}
    
    # 显示最终路径
    start_end_dic = dict(zip(parents.values(), parents.keys()))  # 字典key，value互换
    
    next_node = None
    for i in range(len(start_end_dic)-1):
        start_node = 'start'
    
        if i == 0:
            print('最终路径：', start_node, end='——>')
            next_node = start_end_dic[start_node]
        print(next_node, end='——>')
    
        next_node = start_end_dic[next_node]
    print('end')
    
    # Out
    # start——>b——>a——>end

## 贪婪算法 ##

### 教室调度问题 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDkxMjE1OQ_size_16_color_FFFFFF_t_70_pic_center 2]

*  算法步骤：
    
    1.  选择结束最早的课，它就是这间教室的第一堂课。
    2.  选择第一堂课结束后才开始的课，再次选择结束最早的课，它就是这间教室的第二堂课。
    3.  以此类推。

### 什么是贪婪算法 ###

*  上述教室调度问题就是使用了贪婪算法，算法很容易想到。
 *  贪婪算法，又叫贪心算法，算法很简单：**每步都取最优的做法**【每步都选择局部最优解，最终得到的就是全局最优解】

### 背包问题 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDkxMjE1OQ_size_16_color_FFFFFF_t_70_pic_center 3]

*  **注意**：贪婪算法在背包问题中可能无法获得最优解，但也会和最优解较为接近

假设有以下三样物品，背包容量为35磅：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDkxMjE1OQ_size_16_color_FFFFFF_t_70_pic_center 4]

*  根据贪婪策略，选择价格最高的音响【3000】放入背包，之后背包就无法放入剩下物品了。如果选择笔记本【2000】和吉他【1500】放入背包，最大价值达到【3500】，显然后面的方案是最优的。所以对于该问题使用贪婪策略，并非最优解。

### 集合覆盖问题 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDkxMjE1OQ_size_16_color_FFFFFF_t_70_pic_center 5]

*  如果需要找出最优解需要**列出广播台所有的可能的集合**，那么可能的集合为 2 n − 1 2^n-1 2n−1， 然后在列出的这些集合中，选择最少的广播台数并覆盖全部50各州。
 *  但是这样处理，程序的运行时间为 O ( 2 n ) O(2^n) O(2n)，其运算时间随着广播台数量呈幂集增长，太crazy了

**近似算法**：在获得的精确解需要的时间太长时，可使用近似算法

*  判断近似算法好坏的标准：
    
     *  近似算法计算速度有多快
     *  近似解与最有优解有多接近
 *  在集合问题上使用贪婪算法近似，就很不错，只要每次都选择覆盖最多未覆盖州的广播台，直到覆盖了全部50个州即可。

### NP完全问题 ###

*  上述集合问题 O ( 2 n ) O(2^n) O(2n)便是一个NP完全问题，之前第一章中旅行商问题 O ( n ! ) O(n!) O(n!)也是NP完全问题
 *  遇到NP问题就很大可能使用近似算法，除非NP问题的规模较小

**识别NP完全问题**：

*  元素较少时算法的运行速度非常快，但随着元素数量的增加，速度会变得非常慢。
 *  涉及“所有组合”的问题通常是NP完全问题。（组合问题）
 *  不能将问题分成小问题，必须考虑各种可能的情况。这可能是NP完全问题。
 *  如果问题涉及序列（如旅行商问题中的城市序列）且难以解决，它可能就是NP完全问题。
 *  如果问题涉及集合（如广播台集合）且难以解决，它可能就是NP完全问题。
 *  如果问题可转换为集合覆盖问题或旅行商问题，那它肯定是NP完全问题。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDkxMjE1OQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20210511/dfb64e67c0ca48a9aaebf92288259312.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDkxMjE1OQ_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20210511/a3dbfdcd257149d5a6dbca1d55b6b4e5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDkxMjE1OQ_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20210511/1013e96d6cc846839e3a05a4fccb4864.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDkxMjE1OQ_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20210511/2fcd0b17ed60473985da518ac441ced9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDkxMjE1OQ_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20210511/d77288ef4e7e40e1bfdd3b9afd3d5e17.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDkxMjE1OQ_size_16_color_FFFFFF_t_70_pic_center 5]: /images/20210511/26cde5879f6144a581a94decac6cf90e.png