算法@贪心算法

Dijkstra 求单源最短路径问题

假如你现在在华山景区任意一个景点处，如何找到通往所有景点的最短路径呢？荷兰的 艾兹格 W 迪科斯彻 解决了这个问题...
把景点和距离抽象为，类似下面的有向图/无向图，用邻接矩阵存储数据。
从当前所在位置源点u开始
(1)初始化----每个点到u的最短距离dist[i] = map[u][i] 集合S={源点u} 集合V_S={除源点u外的所有顶点}
(2)找最小----在集合V_S找到和源点相连的最近的顶点a
(3)加入S战队----把a从V_S中取出放到S中
(4)判断结束----如果V_S为空则算法结束
(5)借东风----借助a走捷径，如果其他顶点x经过a后的距离dist[a] map[a][x]小于其他路线的距离dist[x]，则更新dist[x]为此时的短距离，并把x的前驱节点p[x]=a
(6)跳转到(2)

1.  
   如上图从1开始走
2.  
   --------------V_S={2，3, 4， 5}中2距离1最近则
3.  
   1-2
4.  
   和2直接相连的3、4暂时均可走捷径则更新dist[3],dist[4]
5.  
   1-2-3
6.  
   1-2-4
7.  
   --------------V_S={3,4,5}中3距离1最近则
8.  
   1-2-3
9.  
   和3相连的4、5中5暂时可以走捷径则更新dist[5]
10.  
    --------------V_S={4,5}中5距离1最近则
11.  
    1-2-3-5
12.  
    --------------V_S={4}中4距离1最近(只剩4了)
13.  
    --------------V_S={}为空，算法结束
14.  
     
15.  
    最终结果
16.  
    1-2
17.  
    1-2-3
18.  
    1-2-4
19.  
    1-2-3-5

1.  
   # -*- coding: utf-8 -*-
2.  
   # @Time : 2021/8/23 14:37
3.  
   # @Author : HUGBOY
4.  
   # @File : Dijkstra.py
5.  
   # @Software: PyCharm
6.  
    
7.  
   INF = float("inf") # 正无穷大
8.  
   S = set() # 集合
9.  
   V_S = set() # 集合
10.  
     
11.  
    Encode = { # 景点代号
12.  
    1: '玉泉院', 2: '北峰', 3: '苍龙岭', 4: '金锁关',
13.  
    5: '东峰', 6: '长空栈道鹞子翻身', 7: '南峰', 8: '中锋',
14.  
    9: '西峰', 10: '西索道', 11: '游客中心', 12: '北索道'
15.  
    }
16.  
     
17.  
     
18.  
    def Dijkstra(u):
19.  
    # 初始化
20.  
    for i in range(1, N 1):
21.  
    V_S.add(i)
22.  
    Dist[i] = Map[u][i]
23.  
    if Dist[i] == INF: # 与源点u不相邻
24.  
    P[i] = -1
25.  
    else: # 与源点u相邻
26.  
    P[i] = u
27.  
     
28.  
    Dist[u] = 0 # u到源点距离为0
29.  
    S.add(u) # 初始时集合S中只有一个元素: 源点u
30.  
    V_S.remove(u) # 集合V_S有除源点u之外的所有元素
31.  
     
32.  
    for i in range(1, N 1):
33.  
    temp = INF
34.  
    t = u
35.  
     
36.  
    # 从V_S中寻找距离源点最近的景点t "找最小"
37.  
    for j in V_S:
38.  
    if Dist[j] < temp:
39.  
    t = j
40.  
    temp = Dist[j]
41.  
    if t == u:
42.  
    return
43.  
    else:
44.  
    S.add(t)
45.  
    V_S.remove(t)
46.  
     
47.  
    # 更新邻接景点t的景点的数据 "借东风"
48.  
    for j in V_S:
49.  
    if Map[t][j] < INF:
50.  
    if Map[t][j] Dist[t] < Dist[j]:
51.  
    Dist[j] = Map[t][j] Dist[t]
52.  
    P[j] = t
53.  
     
54.  
    def Display(u):
55.  
     
56.  
    print("从 %s 出发到达各个景点的 最短时间 及 路线" % Encode[u])
57.  
    for i in range(1, N 1):
58.  
    if Dist[i] == INF:
59.  
    print("sorry, 目的地 %d %s 不可达 !" % (i, Encode[i]))
60.  
    else:
61.  
    print("[%d]%s 最短时间: %d min " % (i, Encode[i], Dist[i]))
62.  
    FindPath(i)
63.  
     
64.  
    def FindPath(i):
65.  
    x = P[i]
66.  
    stack = []
67.  
    print("路线:")
68.  
    while x != -1:
69.  
    stack.append(x)
70.  
    x = P[x]
71.  
    while len(stack):
72.  
    print('%s-- ' % (Encode[stack[-1]]), end='')
73.  
    stack.pop()
74.  
    print(Encode[i])
75.  
     
76.  
    if __name__ == '__main__':
77.  
     
78.  
    N = 12
79.  
    M = 16
80.  
     
81.  
    # N = int(input("请输入景点个数: \t"))
82.  
    # M = int(input("请输入景点之间的路线个数: \t"))
83.  
     
84.  
    # 初始化 N*N邻接矩阵 初始值为正无穷，景区编号从1开始 0行、0列的值无意义
85.  
    # Map = [[INF] * (N 1) for i in range(N 1)]
86.  
     
87.  
    # while M:
88.  
    # u, v, w = input("请输入景点之间的路线及距离: \t").split()
89.  
    # u, v, w = int(u), int(v), int(w)
90.  
    # Map[u][v] = min(Map[u][v], w) # 取最小值
91.  
    # Map[v][u] = min(Map[v][u], w)
92.  
    # M -= 1
93.  
     
94.  
    inf = INF
95.  
    Map = [[inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf], [inf, inf, 360, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf], [inf, 360, inf, 75, inf, inf, inf, inf, inf, inf, inf, inf, 5], [inf, inf, 75, inf, 75, inf, inf, inf, inf, inf, inf, inf, inf], [inf, inf, inf, 75, inf, 40, inf, inf, 20, 40, inf, inf, inf], [inf, inf, inf, inf, 40, inf, 20, inf, 30, inf, inf, inf, inf], [inf, inf, inf, inf, inf, 20, inf, 20, inf, inf, inf, inf, inf], [inf, inf, inf, inf, inf, inf, 20, inf, 30, 40, inf, inf, inf], [inf, inf, inf, inf, 20, 30, inf, 30, inf, 30, inf, inf, inf], [inf, inf, inf, inf, 40, inf, inf, 40, 30, inf, 5, inf, inf], [inf, inf, inf, inf, inf, inf, inf, inf, inf, 5, inf, 40, inf], [inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, 40, inf, 20], [inf, inf, 5, inf, inf, inf, inf, inf, inf, inf, inf, 20, inf]]
96.  
     
97.  
    Dist = [INF] * (N 1) # 到源点最短距离
98.  
    P = [0] * (N 1) # 最短距离路线终点景点的 前驱景点
99.  
     
100.  
     st = int(input("请输入您当前所在位置代号: \t"))
101.  
     Dijkstra(st)
102.  
     Display(st)

1.  
   D:\python\python.exe E:/PYTHON/Class/ALG/趣学算法/Dijkstra.py
2.  
   请输入您当前所在位置代号: 7
3.  
   从 南峰 出发到达各个景点的 最短时间 及 路线
4.  
   [1]玉泉院 最短时间: 470 min
5.  
   路线:
6.  
   南峰-- 西峰-- 西索道-- 游客中心-- 北索道-- 北峰-- 玉泉院
7.  
   [2]北峰 最短时间: 110 min
8.  
   路线:
9.  
   南峰-- 西峰-- 西索道-- 游客中心-- 北索道-- 北峰
10.  
    [3]苍龙岭 最短时间: 125 min
11.  
    路线:
12.  
    南峰-- 中锋-- 金锁关-- 苍龙岭
13.  
    [4]金锁关 最短时间: 50 min
14.  
    路线:
15.  
    南峰-- 中锋-- 金锁关
16.  
    [5]东峰 最短时间: 40 min
17.  
    路线:
18.  
    南峰-- 长空栈道鹞子翻身-- 东峰
19.  
    [6]长空栈道鹞子翻身 最短时间: 20 min
20.  
    路线:
21.  
    南峰-- 长空栈道鹞子翻身
22.  
    [7]南峰 最短时间: 0 min
23.  
    路线:
24.  
    南峰
25.  
    [8]中锋 最短时间: 30 min
26.  
    路线:
27.  
    南峰-- 中锋
28.  
    [9]西峰 最短时间: 40 min
29.  
    路线:
30.  
    南峰-- 西峰
31.  
    [10]西索道 最短时间: 45 min
32.  
    路线:
33.  
    南峰-- 西峰-- 西索道
34.  
    [11]游客中心 最短时间: 85 min
35.  
    路线:
36.  
    南峰-- 西峰-- 西索道-- 游客中心
37.  
    [12]北索道 最短时间: 105 min
38.  
    路线:
39.  
    南峰-- 西峰-- 西索道-- 游客中心-- 北索道
40.  
     
41.  
    Process finished with exit code 0

HuffmanCode 哈夫曼编码问题(不等长编码)

1.  
   # -*- coding: utf-8 -*-
2.  
   # @Time : 2021/8/24 20:19
3.  
   # @Author : HUGBOY
4.  
   # @File : HuffCode.py
5.  
   # @Software: PyCharm
6.  
    
7.  
   # 节点 数据结构
8.  
   class HNodeType(object):
9.  
   def __init__(self, weight, parent, lchild, rchild):
10.  
    self.weight = weight
11.  
    self.parent = parent
12.  
    self.lchild = lchild
13.  
    self.rchild = rchild
14.  
    self.value = ''
15.  
     
16.  
    # 编码 数据结构
17.  
    class HCodeType(object):
18.  
    def __init__(self):
19.  
    self.bit = []
20.  
    #self.start = start
21.  
     
22.  
    # 构造哈夫曼树
23.  
    def HuffmanTree(HuffNode, N):
24.  
    # 初始化哈夫曼树列表中的节点
25.  
    for i in range(2 * N - 1): # N个叶子 => 2*N - 1 个节点
26.  
    node = HNodeType(0, -1, -1, -1) # 参数: 权值 双亲 左孩子 右孩子
27.  
    HuffNode.append(node)
28.  
     
29.  
    # 输入叶子节点权值
30.  
    for i in range(N):
31.  
    value, weight = input("请输入第%d个叶子的 字符 权值>>" % (i 1)).split()
32.  
    HuffNode[i].value, HuffNode[i].weight = str(value), float(weight)
33.  
     
34.  
    # 构造 Huffman 树
35.  
     
36.  
    for i in range(N - 1): # 2*N - 1 - N 即 N - 1 个双亲节点，需要执行N - 1次树的合并
37.  
    w1 = w2 = MAXWEIGHT # 两个最小树的权值
38.  
    ind1 = ind2 = -1 # 两个最小树的双亲
39.  
     
40.  
    # 找两个最小且无双亲的节点合并
41.  
    for j in range(N i):
42.  
    if HuffNode[j].parent == -1:
43.  
    if HuffNode[j].weight < w1:
44.  
    # 把旧最小信息w2 ind2
45.  
    w2 = w1
46.  
    ind2 = ind1
47.  
    # 把新最小信息w1 ind1
48.  
    w1 = HuffNode[j].weight
49.  
    ind1 = j
50.  
     
51.  
    elif HuffNode[j].weight < w2:
52.  
    w2 = HuffNode[j].weight
53.  
    ind2 = j
54.  
     
55.  
    HuffNode[ind1].parent = N i
56.  
    HuffNode[ind2].parent = N i
57.  
    # 设置合并后生成的节点
58.  
    HuffNode[N i].parent = -1
59.  
    HuffNode[N i].weight = w1 w2
60.  
    HuffNode[N i].lchild = ind1
61.  
    HuffNode[N i].rchild = ind2
62.  
     
63.  
    print("第%d轮 %.2f 与 %.2f 合并啦 !" % (i 1, HuffNode[ind1].weight, HuffNode[ind2].weight))
64.  
     
65.  
    # 哈夫曼树编码
66.  
    def HuffmanCode(HuffCode, N):
67.  
     
68.  
    # 初始化哈夫曼编码节点
69.  
    for i in range(N):
70.  
    node = HCodeType()
71.  
    HuffCode.append(node)
72.  
     
73.  
     
74.  
     
75.  
    for i in range(N):
76.  
    temp = HCodeType() # 临时存放某字符编码
77.  
    c = i
78.  
    p = HuffNode[c].parent
79.  
    while p != -1:
80.  
    if HuffNode[p].lchild == c:
81.  
    temp.bit.append(0)
82.  
    else:
83.  
    temp.bit.append(1)
84.  
    #temp.start -= 1
85.  
    c = p
86.  
    p = HuffNode[c].parent
87.  
    # 保存叶子节点的编码到HuffCode中
88.  
     
89.  
    HuffCode[i].bit = temp.bit
90.  
     
91.  
    #HuffCode[i].start = temp.start
92.  
     
93.  
     
94.  
    if __name__ == '__main__':
95.  
     
96.  
    MAXLEAF = 30 # 叶子数 (待编码字符个数)
97.  
    HuffNode = [] # 哈夫曼树节点
98.  
    HuffCode = [] # 哈夫曼编码节点
99.  
    #MAXBIT = 100
100.  
     MAXWEIGHT = 10000
101.  
     MAXNODE = 2 * MAXLEAF - 1
102.  
      
103.  
     N = int(input("请输入叶子数 N>>"))
104.  
     HuffmanTree(HuffNode, N)
105.  
     HuffmanCode(HuffCode, N)
106.  
      
107.  
     for i in range(N):
108.  
     print(HuffNode[i].value, HuffCode[i].bit)

1.  
   D:\python\python.exe E:/PYTHON/Class/ALG/趣学算法/HuffCode.py
2.  
   请输入叶子数 N>>6
3.  
   请输入第1个叶子的 字符 权值>>a 0.05
4.  
   请输入第2个叶子的 字符 权值>>b 0.32
5.  
   请输入第3个叶子的 字符 权值>>c 0.18
6.  
   请输入第4个叶子的 字符 权值>>d 0.07
7.  
   请输入第5个叶子的 字符 权值>>e 0.25
8.  
   请输入第6个叶子的 字符 权值>>f 0.13
9.  
   第1轮 0.05 与 0.07 合并啦 !
10.  
    第2轮 0.12 与 0.13 合并啦 !
11.  
    第3轮 0.18 与 0.25 合并啦 !
12.  
    第4轮 0.25 与 0.32 合并啦 !
13.  
    第5轮 0.43 与 0.57 合并啦 !
14.  
    a [0, 0, 0, 1]
15.  
    b [1, 1]
16.  
    c [0, 0]
17.  
    d [1, 0, 0, 1]
18.  
    e [1, 0]
19.  
    f [1, 0, 1]
20.  
     
21.  
    Process finished with exit code 0

Prim 最小生成树问题

1.  
   #-*- coding: utf-8 -*-
2.  
   #@Time : 2021/8/25 19:11
3.  
   #@Author : HUGBOY
4.  
   #@File : Prim.py
5.  
   #@Software: PyCharm
6.  
    
7.  
    
8.  
    
9.  
   def Prim(N, u0, C):
10.  
     
11.  
    # 初始化closeV closeLen
12.  
    for i in range(N):
13.  
    closeV[i] = u0
14.  
    closeLen[i] = C[u0][i]
15.  
    if i == u0:
16.  
    closeLen[i] = 0
17.  
    # 从指定位置u0开始寻找
18.  
    U.add(u0)
19.  
    V_U = V - U
20.  
    for _ in range(N): # 循环N次 U最多添加N个顶点元素
21.  
     
22.  
    temp = INF
23.  
    t = u0
24.  
    # 在V_U中找距离集合U最近(边长最小)的顶点t 放到U
25.  
    for i in V_U:
26.  
    if closeLen[i] < temp:
27.  
    t = i # 记录该顶点 更新temp
28.  
    temp = closeLen[i]
29.  
     
30.  
    if t == u0: # 未找到
31.  
    break
32.  
     
33.  
    U.add(t)
34.  
    print(t)
35.  
    V_U.remove(t)
36.  
     
37.  
    # 更新closeV minLen 的值
38.  
    for j in V_U:
39.  
    if C[t][j] < closeLen[j]:
40.  
    closeLen[j] = C[t][j]
41.  
    closeV[j] = t
42.  
     
43.  
    if __name__ == '__main__':
44.  
     
45.  
    INF = float("inf") # 无穷大
46.  
    U = set() # 集合
47.  
     
48.  
    N, M = input("请输入 顶点数 边数>>>").split()
49.  
    N, M = int(N), int(M)
50.  
     
51.  
    C = [[INF] * N for i in range(N)] # N*N 邻接矩阵C[n][n]
52.  
     
53.  
    for i in range(M):
54.  
    u, v, w = input("请输入第%d条边 顶点 顶点 权值>>>" % (i 1)).split() # 顶点从1开始数
55.  
    C[int(u)-1][int(v)-1] = int(w)
56.  
    C[int(v)-1][int(u)-1] = int(w)
57.  
     
58.  
    # inf = INF
59.  
    # C = [[inf, 23, inf, inf, inf, 28, 36], [inf, inf, 20, inf, inf, inf, 1], [inf, inf, inf, 15, inf, inf, 4], [inf, inf, inf, inf, 3, inf, 9], [inf, inf, inf, inf, inf, 17, 16], [inf, inf, inf, inf, inf, inf, 25], [inf, inf, inf, inf, inf, inf, inf]]
60.  
     
61.  
    u0 = int(input("请输入 任意顶点u0>>>")) - 1
62.  
     
63.  
     
64.  
    closeV = [u0] * N # 临近点(和自己相连边长最小的点)
65.  
    closeLen = [INF] * N # 临近距离
66.  
    V = {i for i in range(N)} # 顶点全集
67.  
     
68.  
    print(V, U)
69.  
    Prim(N, u0, C)
70.  
    print("closeLen[]\t", closeLen)

1.  
   D:\python\python.exe E:/PYTHON/Class/ALG/Prim.py
2.  
   请输入 顶点数 边数>>>7 12
3.  
   请输入第1条边 顶点 顶点 权值>>>1 2 23
4.  
   请输入第2条边 顶点 顶点 权值>>>1 6 28
5.  
   请输入第3条边 顶点 顶点 权值>>>1 7 36
6.  
   请输入第4条边 顶点 顶点 权值>>>2 3 20
7.  
   请输入第5条边 顶点 顶点 权值>>>2 7 1
8.  
   请输入第6条边 顶点 顶点 权值>>>3 4 15
9.  
   请输入第7条边 顶点 顶点 权值>>>3 7 4
10.  
    请输入第8条边 顶点 顶点 权值>>>4 5 3
11.  
    请输入第9条边 顶点 顶点 权值>>>4 7 9
12.  
    请输入第10条边 顶点 顶点 权值>>>5 6 17
13.  
    请输入第11条边 顶点 顶点 权值>>>5 7 16
14.  
    请输入第12条边 顶点 顶点 权值>>>6 7 25
15.  
    请输入 任意顶点u0>>>1
16.  
    {0, 1, 2, 3, 4, 5, 6} set()
17.  
    1
18.  
    6
19.  
    2
20.  
    3
21.  
    4
22.  
    5
23.  
    closeLen[] [0, 23, 4, 9, 3, 17, 1]
24.  
     
25.  
    Process finished with exit code 0