Box
Box
Posts List
  1. 二分查找
  2. 狄克斯特拉算法
  3. 贪婪算法
  4. 动态规划
  5. 最长公共子串
  6. 最长公共子序列之解决方案

图解算法

2018.07.09 Dai Dai Algorithm  热度 ℃

二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def binary_search(list, item):
    low = 0
    high = len(list) - 1
    while low <= high:
        mid = int((low + high) / 2)  # 中间的
        guess = list[mid]
        if guess == item:
            return mid
        if guess > item:
            high = mid - 1
        else:
            low = mid + 1
    return None


my_list = [1, 3, 5, 7, 9]
print(binary_search(my_list, 3))
print(binary_search(my_list, -1))

  • 最短路径问题：使用广度优先搜索，使用图来建立问题模型

  • 假设你经营着一个芒果农场,需要寻找芒果销售商,以便将芒果卖给他。在Facebook,你与芒果销售商有联系吗?为此,你可在朋友中查找。

  • 查找最短路径，广度优先搜索可回答两类问题

    • 第一类问题:从节点A出发,有前往节点B的路径吗?(在你的人际关系网中,有芒果销 售商吗?)
    • 第二类问题:从节点A出发,前往节点B的哪条路径最短?(哪个芒果销售商与你的关系 最近?)
1
2
3
4
5
6
7
8
9
graph = {}
graph["you"] = ["alice", "bob", "claire"]
graph["bob"] = ["anuj", "peggy"]
graph["alice"] = ["peggy"]
graph["claire"] = ["thom", "jonny"]
graph["anuj"] = []
graph["peggy"] = []
graph["thom"] = []
graph["jonny"] = []
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from collection import deque
search_queue = deque()  # 创建一个队列
search_queue += graph['you']  # 将你的邻居都加入到这个搜索队列中

while search_queue:  # 只要队列不为空
    person = search_queue.popleft()  # 就取出其中的第一个人
    if person_is_seller(person):  # 检查这个人是否是芒果商
        print('{} is a mango seller!'.format('person')  # 是芒果商
        return True
    else:
        search_queue += graph[person]  # 不是芒果销售商。将这个人的朋友都加入搜索队列
return False  # 如果到达了这里，就说明队列中没人是芒果商

def person_is_seller(name):
    return name[-1] == 'm'

将一个人加入对列的时间是固定的O(1)，总时间就为O(人数)。所以广度优先搜索的运行时间为O(人数+边数)

狄克斯特拉算法

  • 问题：其中每个数字表示的都是时间,单位分钟。为找出从起点到终点耗时最短的路径,你将使用 狄克斯特拉算法。
1
2
3
4
5
6
graph TD
    A[起点] -->|6| B(A)
    A[起点] -->|2| C(B)
    C -->|3| B
    B -->|1| D(终点)
    C -->|5| D(终点)
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
graph = {}

graph["you"] = ["alice", "bob", "claire"]

# 使用散列表
graph["start"] = {}
graph["start"]["a"] = 6
graph["start"]["b"] = 2

graph["a"] = {}
graph["a"]["fin"] = 1
graph["b"] = {}
graph["b"]["a"] = 3
graph["b"]["fin"] = 5
graph["fin"] = {}  # 终点没有任何邻居


infinity = float("inf")

# 创建开销表
infinity = float("inf")
costs = {}
costs["a"] = 6
costs["b"] = 2
costs["fin"] = infinity

# 创建这个散列表
parents = {}
parents["a"] = "start"
parents["b"] = "start"
parents["fin"] = None

# 存储处理过的节点
processed = []

# 代码
node = find_lowest_cost_node(costs)  # 在未处理的节点中找出开销量最小的节点
while node is not None:  # 这个while循环在所有节点都被处理过后结束
    cost = costs[node]
    neighbors = graph[node]
    for n in neighbors.key():  # 遍历当前节点
        new_cost = cost + neighbors[n]
        if costs[n] > new_costs:  # 如果经过当前节点前往该邻居更近
            costs[n] = new_costs  # 就更新该邻居的开销
            parents[n] = node  # 同时将该邻居的父节点设置为当前节点
    processed.append(node)  # 将当前节点标记为处理过
    node = find_lowest_cost_node(costs)  # 找出接下来要处理的节点

def find_lowest_cost_node(costs):
    lowest_cost = float("inf")
    lowest_cost_node = None
    for node in costs:  # 遍历所有的节点
        cost = costs[node]
        if cost < lowest_cost and node not in processed:  # 如果当前节点的开销更低且未处理过
            lowest_cost = cost  # 就将其视为开销最低的节点
            lowest_cost_node = node
    return lowest_cost_node
  • 第一步：找出最便宜的节点
  • 第二步：计算经起点的下一节点前往其各个节点所需的时间
  • 第三步：重复
  • 重复第一步:找出可在最短时间内前往的节点。你对节点B执行了第二步,除节点B外,可在最短时间内前往的节点是节点A。

  • 重复第二步:更新节点A的所有邻居的开销。

  • 算法异同：

    • 使用广度优先搜索来查找两点之间的最短路径，这里的“最短路径”的意思是段数最少
    • 在狄克斯特拉算法中,你给每段都分配了一个数字或权重,因此狄克斯特拉算法找出的是总权重最小的路径。

  • 使用：

    • 要计算非加权图中的最短路径,可使用广度优先搜索。要计算加权图中的最短路径,可使用狄克斯特拉算法。
    • 狄克斯特拉算法只适用于有向无环图

贪婪算法

  • 贪婪算法并不能得到最优解，因为每步都是局部最优解

动态规划

  • 使用动态规划时，要么考虑拿走整件商品，要么考虑不拿，而没法判断该不该拿走商品的一部分。

问题：

  • 假设你要去伦敦度假，假期两天，但你想去游览的地方很多。你没法前往每个地方游览，因此你列个单子。
名胜 时间 评分
威斯敏斯特教堂 0.5天 7
环球剧场 0.5天 6
英国国家美术馆 1天 9
大英博物馆 2天 9
圣保罗大教堂 0.5天 8
  • 思路：
    • 使用网格，先建立空网格
0.5 1 1.5 2
威斯敏斯特教堂
环球剧场
英国国家美术馆
大英博物馆
圣保罗大教堂
    • 网格填充结果
0.5 1 1.5 2
威斯敏斯特教堂（w） 7（w） 7（w） 7（w） 7（w）
环球剧场（g） 7（w） 13（wg） 13（wg） 13（wg）
英国国家美术馆（n） 7（w） 13（wg） 16（wn） 22（wgn）
大英博物馆（b） 7（w） 13（wg） 16（wn） 22（wgn）
圣保罗大教堂（s） 8（s） 15（ws） 21（wgs） 24（wns）

填充表格从左到右，然后下一行，重复。

最长公共子串

  • 问题：HISH和FISH的最长公共子串是？

  • 思路：

    • 画表格
H I S H
F
I
S
H
    • 填充表格
H I S H
F 0 0 0 0
I 0 1 0 0
S 0 0 2 0
H 0 0 0 3

若果横纵字母相同则对应空格为1加上空格左上角邻居的值

1
2
3
4
5
# 实现这个公式的伪代码
if word_a[i] == word_b[j]:  # 两个字母相同
    cell[i][j] = cell[i-1][j-1] + 1
else:  # 两个字母不同
    cell[i][j] = 0

最长公共子序列之解决方案

  • 最长公共子序列：两个单词都有的序列包含的字母数

  • 问题：求fish和fosh的最长公共子序列

  • 思路：

    • 画网格
H O S H
F
I
S
H
    • 填充表格
H O S H
F 1 1 1 1
I 1 1 1 1
S 1 1 2 2
H 1 1 2 3

如果两个字母不同，就选择上方和左邻居中较大的那个
如果两个字母相同，就将当前单元格的值设为左上方单元格的值加1

1
2
3
4
if word_a[i] == word_b[j]:  # 两个字母相同
    cell[i][j] = cell[i-1][j-1] + 1
else:  # 两个字母不同
    cell[i][j] = max(cell[i-1][j], cell[i][j-1])
Supporting
Scan, Support Daidai
  • WeChat scan
  • Alipay scan