欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-06-04 16:05:37
...

目录结构

第7章 狄克斯特拉算法

第8章 贪婪算法

狄克斯特拉算法

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

  • 图A是使用广度优先搜索算法计算最短路径的图结构(非加权图)

    ——在非加权图中计算最短路径,可使用广度优先搜索

  • 图B是使用狄克斯特拉算法计算最短路径的图结构(加权图)

    ——在加权图中计算最短路径,可使用狄克斯特拉算法

什么是狄克斯特拉算法

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

使用狄克斯特拉算法

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

实现狄克斯特拉算法

  • 使用下图来实现狄克斯特拉算法

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

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

贪婪算法

教室调度问题

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

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

什么是贪婪算法

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

背包问题

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

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

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

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

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

集合覆盖问题

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

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

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

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

NP完全问题

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

识别NP问题

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