发表于 | 分类于 | 阅读次数:
字数统计: 949 | 阅读时长 ≈ 4

如何根据两点 入规划从一个地铁站到另外一个地铁站的小汽车出现路线？

也就是地图提供的寻路？

这个是预期准备做的项目题干

dijkstra 算法 找最短路径

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131

import random


class Node(object):
    def __init__(self, user_id):
        self.user_id = user_id  # 用户节点 id
        self.friends = list()  # 用户指向的节点，元素表示节点 id
        self.weights = list()  # 用户指向的节点，其边的权重值


def set_user_relation(user_num, relation_num):
    """
    随机生成用户间的关系
    :param user_num: 用户数量 即节点的数量
    :param relation_num: 好友关系的数量 即边的数量
    :return:
    """
    # 生成所有表示用户的节点
    use_nodes = list()
    for u in range(user_num):
        use_nodes.append(Node(u))

    # 生成所有表示好友关系的边
    for r in range(relation_num):
        friend_a_id = random.randrange(user_num)
        friend_b_id = random.randrange(user_num)
        # 自己不能是自己的好友 如果生成的两个好友 id 相同，跳过
        if friend_a_id == friend_b_id or friend_b_id in use_nodes[friend_a_id].friends:
            continue
        friend_a = use_nodes[friend_a_id]
        friend_a.friends.append(friend_b_id)  # 用户 friend_a 的好友
        friend_a.weights.append(round(random.random(), 2))  # 权重值
    return use_nodes


def dijkstra(graph, source):
    """
    Dijkstra 单源最短路径算法简单实现
    :param graph: 图
    :param source: 源点（起始点）
    :return: pre_node 前驱节点
    """
    nodes_list = list()
    # 图 graph 中的节点id的集合
    for node in range(len(graph)):
        nodes_list.append(graph[node].user_id)

    # 保存了从起始点 source 到任意节点到最小权重值（最短路径大小）
    min_weights_list = list([float("Inf")] * len(graph))  # 无穷大 Inf , 下标与节点对应
    # 从源点 source 出发，已经找到 最小权重值（最短路径值大小）的节点集合
    found_nodes = list()  # 元素表示节点 id
    # 前驱节点
    pre_node = list([None] * len(graph))  # 下标与节点对应，其元素为下标对应的前驱节点

    # 初始的时候
    if len(graph[source].friends) == 0:
        return pre_node
    for node in range(len(graph[source].friends)):
        min_weights_list[graph[source].friends[node]] = graph[source].weights[node]
        # 初始，与源点 source 直连的节点，其前驱节点为 source
        pre_node[graph[source].friends[node]] = source
    # min_weights_list[source] = 0  # 去掉这一步，便于查找最小权重值
    found_nodes.append(source)

    while len(set(nodes_list) - set(found_nodes)) != 0:
        # 图可能是不连通，min_weights_list 中, 源点 source 到某些节点的权重值无穷大
        if min(min_weights_list) == float("Inf"):
            break

        # 第一步 查找最小权重值的节点
        min_weight_index = min_weights_list.index(min(min_weights_list))  # 下标对应节点的id
        found_nodes.append(min_weight_index)

        # 第二步 更新权重值
        for node in range(len(graph[min_weight_index].friends)):
            # 已经找到最短路径的节点，不再更新
            if graph[min_weight_index].friends[node] in found_nodes:
                continue
            if min_weights_list[min_weight_index] + graph[min_weight_index].weights[node] < \
                    min_weights_list[graph[min_weight_index].friends[node]]:
                # 更新 min_weights_list 中节点的权重值
                min_weights_list[graph[min_weight_index].friends[node]] = min_weights_list[min_weight_index] + \
                                                                          graph[min_weight_index].weights[node]
                # 更新前驱节点
                pre_node[graph[min_weight_index].friends[node]] = min_weight_index
        # 该点权重值置为无穷大，为下一次循环准备
        min_weights_list[min_weight_index] = float("Inf")

    return pre_node


def shortest_path(graph, source, pre_node):
    """
    打印源点 source 到其它节点到最短路径
    :param graph: 图
    :param source: 源点
    :param pre_node: 前驱节点列表
    :return:
    """
    print("------------- 源点 %s 到其它各节点的最短路径 ----------" % source)
    for k, _ in enumerate(graph):
        pre = pre_node[k]
        if pre is None:
            print("源点 %s 到 %s 的最短路径：不存在" % (source, k))
            continue
        path = [str(k)]
        while pre != source and pre is not None:
            path.append(" -> ")
            path.append(str(pre))
            pre = pre_node[pre]
        if pre == source:
            path.append(" -> ")
            path.append(str(pre))
        print("源点 %s 到 %s 的最短路径：%s" % (source, k, ''.join(path[::-1])))


if __name__ == "__main__":
    user_nodes_list = set_user_relation(10, 20)
    for i in range(len(user_nodes_list)):
        if len(user_nodes_list[i].friends):
            print("用户 {} 的好友: {}, \t权重值 {}".format(user_nodes_list[i].user_id, user_nodes_list[i].friends,
                                                   user_nodes_list[i].weights))
        else:
            print("用户 {} 的好友: 不存在".format(user_nodes_list[i].user_id))
    print("\n------------- Dijkstra 单源最短路径算法 --------------\n")
    s = 1  # 源点
    pre_node_list = dijkstra(user_nodes_list, s)
    print("各下标节点对应的前驱节点：", pre_node_list, "\n")
    # 打印路径
    shortest_path(user_nodes_list, s, pre_node_list)

发表于 | 分类于 | 阅读次数:
字数统计: 455 | 阅读时长 ≈ 1

python的优点

  • 简单 语法优雅
  • 易学 入手非常快
  • 免费/开源
  • 自动内存管理 C C++内存管理会带来很大的麻烦 程序非常容易出现内存方面的漏洞 但是python中内存管理是自动完成的 可以专注于程序本身
  • 可以移植
  • 解释性 大多数的计算机语言是编译型的 运行之前需要将源码编译为操作系统可以执行的二进制格式 这样大型项目编译过程非常消耗时间 python解释器把源代码转换成字节码的中间形式 然后再把它翻译成计算机使用的机器语言并运行

  • 面向对象 混合型

  • 可扩展

  • 丰富的第三方库

缺点

  • 速度慢
  • 强制缩进？？ 习惯很正常
  • 单行语句

如果没有对性能上的高要求 python在大部分领域都可以胜任

有些需要Cython甚至C这些工具

golang项目 设计一塌糊涂 但是多核支持好 轻松跑出需要的性能 python的服务往往一个小问题就很致命

10qps以下 学艺不精找不到问题 往往以为python本身这么慢

动态类型如果代码写得烂 下限更低
对解释器的依赖容易出现各种问题 部署的时候还要专门的一块代码去帮客户配置环境

文件过多 导致部署不方便 golang的话 是一个binary完事

不那么容易暴露内部实现 因为给的是可执行文件

解决性能不够好的问题

golang相对来说 菜鸟也能写出性能远高于python的程序

语法简单 总体上也比较安全 不用瞻前顾后