维特比(Viterbi)算法是一种动态规划算法,在处理隐马尔可夫(HMM)最优路径问题时经常被使用.
动态规划算法
动态规划是运筹学的一个分支,是求解决策过程最优化的数学方法，通常情况下应用于最优化的问题,
这类问题一般有很多可行的解,每个解有一个值,而我们希望从中找到最优的答案.
在计算机科学领域,应用动态规划的思想解决的最基本的一个问题就是寻找有向无环图(DAG)当中两个点之间的最短路径
实际应用于地图导航、语音识别、分词、机器翻译等等.
问题
看下面一个简易版的地图
假设从北京驱车前往广州需要跨越 a,b,c,d,e五省,每个省均有4个城市1,2,3,4
各城市间的距离与图上城市间距离一致,求北京前往广州的最短路径.
穷举法
首先想到的就是穷举法,非别计算出所有可能的路径距离,然后求最优解.对于这个问题,需要计算4*4*4*4*4=1024次.
在实际应用中,随着节点数的增加,计算的复杂度也相应的增加,图2为上例中所有可能出现的结果(为便于观察,微调了下位置)
假设两地间隔N个省,每个省有M个城市,那么实际的计算复杂度为O(N^M)
维特比算法
维特比算法假设,从北京到上海有一条最短路径(图3中红色部分),这条路径经过e2,那么包含在这条路径中,从北京到e2的这条子路径,也一定是北京到e2间的最短路径.
这个很好证明,如果有从北京到e2的更短的路径,那么原先的最短路径也就不是最短路径了.
同理,那么从北京到d2,c2,b2的路径也一定是最短子路径.
那么如果要求北京到e2的最短路径,那么只需要计算从北京到d层每个城市的最短路径,
然后再计算d层每个城市到e2的距离,即可得到北京到e2间的最短路线,对于最初的问题而言
先计算北京距离e层的各个点的最短距离,在计算e层各个点到上海的距离,即可得出结果.
分解算法
第一步,计算北京到a层所有城市的距离S(ai),这里计算了4次
第二步,计算北京到b层的距离,从北京出发可能经过a层的任意一个点,前往b层的任意点,
因而可能的路线有16种(4*4), 如图4
从这16中结果中,即可得到从北京出发,分别前往b1,b2,b3,b4的最短路线.
第三步,需要计算北京到c层各个点的距离,如果采用穷举法,那么c层所有可能的路线64次(444).
但根据维特比算法的假设,从北京出发,经过b层某个点到达c层某个点的最短路径,一定包含从北京出发,到达b层这个点的最短路径.
比较绕,举个具体点的例子,假设从北京出发,经过a2,b2到达c2为北京到c2间的最短路径,那么北京经过a2到b2这条子路径,一定是北京到b2的最短路径.
如此,即可在第二步计算的16中结果中,只保留b层4个点的最短路径,如图4-2
再分别计算这些点到c层各个点的路径(共16次 44),如此,原本c层需要再b层的计算的所有结果(16个)上再4,现在变为+16,总的计算次数变为了32,如图5
第四步,重复第三步的方式,计算北京到d层各个点的距离,如图6
在到达shenzhen之前,后续每一层都只需要再前一步计算的最优路线上(4个)进行4次(到1,2,3,4每个点)运算,如图7
最终,即可得到唯一的一条路径,如图8
维特比算法将原本层与层之间的
*法变为了+法,例子中的第一层北京只有1个点,到e点总的计算次数就变为了64次
1*4 + 4*4 + 4*4 + (4*4) + (4*4) + 1*4
bj到a a到b b到c c到d d到e e到shenzhen
一个层数为L,每层有N个点的篱笆图,运用维特比算法的复杂度即为O(LN^2),
而原本为
4 * 4 * 4 * 4 * 4 * 1
bj到a bj到b bj到c bj到d bj到e bj到shenzhen
代码验证
简化一下上面的问题,剔除e层,保留a,b,c,d层与起始点(beijing,shenzhen),然后绘制在坐标系上的,
坐标随便写的,能表示出层与层之间即可,如下图9
- 根据推测使用穷举法需要计算
1*4*4*4*4*1 = 256次 - 使用维特比算法需要计算
1*4+4*4+4*4+4*4+4*1 = 56次(前后两个4因为beijing,shenzheng只有1个节点)
下面进行代码验证,首先使用穷举法,计算出所有可能的结果
# -*- coding: utf-8 -*-
import psutil
import os
# 标记每个城市在的坐标
a = {"a1": (1.1, 2.5), "a2": (1.8, 2.2), "a3": (1.3, 1.5), "a4": (1.9, 1)}
b = {"b1": (3.4, 2.4), "b2": (3.9, 1.8), "b3": (3.5, 1.1), "b4": (4, 0.4)}
c = {"c1": (5.6, 2.5), "c2": (5.7, 2), "c3": (5.9, 1.5), "c4": (5.8, 0.65)}
d = {"d1": (7.3, 2.5), "d2": (7.8, 2.2), "d3": (7.5, 1.5), "d4": (7.7, 0.95)}
# 假设北京的坐标为0,0 广州的坐标为 10,10
beijing = (0, 0)
shanghai = (10, 10)
# 计算路线总长度
def sum_way(way):
result = 0
for key in way:
result += way[key]
return round(result, 2)
# 定义一个dict保存所有可能的路线
all = {}
n = 0
# step1 计算北京到a各个点的距离,三角函数 ((x2-x1)^2 + (y2-y1)^2) ** 0.5
# 所有保留2位小树
for i in a:
for j in b:
for k in c:
for m in d:
n += 1
all["beijing_" + i + "_" + j + "_" + k + "_" + m] = {
"detail": {
# 北京到a
"beijing_" + i: round((a[i][0] ** 2 + a[i][1] ** 2) ** 0.5, 2),
# a到b
i + "_" + j: round(((b[j][0] - a[i][0]) ** 2 + (b[j][1] - a[i][1]) ** 2) ** 0.5, 2),
# b到c
j + "_" + k: round(((c[k][0] - b[j][0]) ** 2 + (c[k][1] - b[j][1]) ** 2) ** 0.5, 2),
k + "_" + m: round(((d[m][0] - c[k][0]) ** 2 + (d[m][1] - c[k][1]) ** 2) ** 0.5, 2),
m + "_shenzhen": round(((10 - d[m][0]) ** 2 + (10 - d[m][1]) ** 2) ** 0.5, 2)
}
}
all["beijing_" + i + "_" + j + "_" + k + "_" + m]["length_all"] = \
sum_way(all["beijing_" + i + "_" + j + "_" + k + "_" + m]["detail"])
short_way = sorted(all.values(), key=lambda value: value["length_all"], reverse=True).pop()
print("最优路线:", "_".join([i.split("_")[0] for i in short_way["detail"]]))
print("总长度", short_way["length_all"])
print("节点计算次数", n, "次")
print('内存使用:', round(psutil.Process(os.getpid()).memory_info().rss / 1000, 2), "kb")
运算结果:
最优路线: beijing_a4_b2_c2_d1
总长度 15.76
节点计算次数 256 次
内存使用: 9576.45 kb
然后使用维特比算法
# -*- coding: utf-8 -*-
import psutil
import os
# 所有要计算的所有层节点组成一个网格
grid = [
{"a1": (1.1, 2.5), "a2": (1.8, 2.2), "a3": (1.3, 1.5), "a4": (1.9, 1)},
{"b1": (3.4, 2.4), "b2": (3.9, 1.8), "b3": (3.5, 1.1), "b4": (4, 0.4)},
{"c1": (5.6, 2.5), "c2": (5.7, 2), "c3": (5.9, 1.5), "c4": (5.8, 0.65)},
{"d1": (7.3, 2.5), "d2": (7.8, 2.2), "d3": (7.5, 1.5), "d4": (7.7, 0.95)},
{"shanghai": (10, 10)}
]
# 上一节点最短路径 初始化时设置为开始位置
shortest_path = [
{
"tag": "beijing",
"way": ["beijing"],
"step": [(0, 0)],
"step_length": [0],
"length": 0
}
]
# 对每一步计算的可能路径进行过滤,只保留到这层各个点最短路径
def get_shortest_path(temp_list):
# 先排序
temp_list.sort(key=lambda value: value["length"], reverse=True)
# 再分组
temp_dict = {}
for i in temp_list:
if temp_dict.get(i["tag"]) is None:
temp_dict[i["tag"]] = list()
temp_dict[i["tag"]].append(i)
shortest_path_temp = []
# 再保留每组最小值
for k, v in temp_dict.items():
shortest_path_temp.append(v.pop())
return shortest_path_temp
n = 0
for no, info in enumerate(grid):
temp_list = []
for key, value in info.items():
for path in shortest_path:
# 记录计算次数
n += 1;
# 取起始点坐标
start = path["step"].copy().pop()
# 取目标点坐标
end = value
# 目标点名字
name = key
# 定义一个起始点的一个tag 分组用
tag = path["tag"].split("_")[0] + "_" + name
# 记录经过的路径
way = path["way"].copy()
way.append(key)
# 记录每一步的坐标
step = path["step"].copy()
step.append(end)
# 计算起始点到目标点长度
length = round(((end[0] - start[0]) ** 2 + (end[1] - start[1]) ** 2) ** 0.5, 2)
# 记录这一步的长度
step_length = path["step_length"].copy()
# 总长度
step_length.append(length)
length_num = round(path["length"] + length, 2)
temp_list.append({"tag": tag, "way": way, "step": step, "step_length": step_length, "length": length_num})
# 分组 保留最优解
shortest_path = get_shortest_path(temp_list)
result = shortest_path.pop()
print("最优路线:", "_".join(result["way"]))
print("总长度:", result["length"])
print("节点计算次数", n, "次")
info = psutil.virtual_memory()
print('内存使用:', round(psutil.Process(os.getpid()).memory_info().rss / 1000, 2), "kb")
运算结果:
最优路线: beijing_a4_b2_c2_d1_shanghai
总长度: 15.76
节点计算次数 56 次
内存使用: 9211.9 kb
总结
- 维特比算法是一种动态规划算法,维特比算法总体思想就是,再前一步计算的最优解上,计算后一步所有可能出现的情况
- 对于一个长度(层数)为M,每层最大节点数为N的DAG,复杂度最差情况下为O(MN^2)
- 维特比算法仅解决了隐马尔可夫第三问,替代方法还有很多,不能直接将维特比算法和隐马尔可夫问题划等号
