I. 问题重述

利用哥尼斯堡七桥问题来解决检察员应该采取怎样的走法才能走完全部街道，如下图，并且使其行走的距离最短。

图例.png

II. 合理性假设及符号说明

假设：

a,b,c,d,e,f,g,h,k,k,l,m 这13个点的代号分别为：0，1，2，3，4，5，6，7，8，9， 10, 11, 12
了解欧拉回路是什么，想要解决行走的最短路径问题，首先需要了解到怎样行走能走完全部的道路，并且要考虑走的重复路程最短的情况。

1. 有向图的欧拉回路

一个有向图存在欧拉回路的前提条件是这个图是个连通图，其次要求其每个点的入度等于出度，或者其中有一个点的出度比入度大1，另一个点的入度比出度大一这样就存在一条欧拉回路。

如果其每个点的入度等于出度则从任意一点出发，可以走出一条欧拉回路，如果是第二种情况，则必须从出度大于入度 1 的点出发到入度大于出度 1 的点结束，走出一条欧拉道路。

2. 无向图的欧拉回路

跟有向图一样，首先必须连通，其次如果最多只有两个奇点。则满足欧拉回路或欧拉道路，有奇点就从任意一个奇点出发找科形成一条欧拉道路，否则从任意一点出发都能找出欧拉回路。

III. 模型设计分析

利用 PyCharm 编程，参考哥尼斯堡七桥问题的解法，

第一步：假设两个节点之间的路径用一个列表来囊括（一共25条路径）；

第二步：考虑检察员的起始位置，当然，这个问题其实对最佳路径的求得毫无影响，因为不管他的起始位置在何处，纵观全局来看，他在每一个节点的最佳行走路径已经被确定了；

第三步：编程，确定最佳路径，判断是否为欧拉回路；

第四步：执行，检查运行结果

V. 数值计算及有效性分析

查看当检查员从d点出发时的运行结果：

是欧拉道路:3 -> 0 -> 2 -> 1 -> 0 -> 4 -> 5 -> 1 -> 3 -> 5 -> 6 -> 2 -> 9 -> 8 -> 5 -> 11 -> 7 -> 4 -> 10 -> 7 -> 11 -> 8 -> 9 -> 12 -> 6 -> 11

数值计算

欧拉道路(无重复的路径)：f→b→a→c→b→d→a→e→f→g→j→i→f→l→h→e→k→l→j→m→l

欧拉路径的值：72

结合图形分析，上述欧拉路径覆盖了每一个节点，但是遗忘了三条边。所以，走完所有路线的最佳解法是综合考虑遗漏的三条边的解法。

最优路径：d→f→b→a→c→b→d→a→e→f→g→c→g→j→i→f→l→h→e→k→h→k→l→j→m→g→m→l

最短路径的值： 81

VI. 参考文献

[1] https://blog.csdn.net/u013803572/article/details/82979237

VII. 附录（程序及其它说明）

# 路线图
# 假设：a,b,c,d,e,f,g,h,k,k,l,m 这13个点的代号为0，1，2，3，4，5，6，7，8，9，10,11,12
eulerEdges = [
    (0, 2),(0, 1),(0, 3),(0, 4),(1, 2),
    (1, 3),(1, 5),(6, 2),(3, 5),(4, 5),
    (4, 7),(4 ,10),(5, 6),(5, 8),(5, 11),
    (6, 9),(6, 12),(7, 10),(7, 11),(8, 9),
    (8, 11),(9, 11),(9, 12),(10, 11),(11, 12)
]#  这个列表里的25个元素均代表一条路径
# 可以通过修改start的值来确定起始位置
start = 3    # 检查员起始位置，笔者认为从效率考虑，应该从d点开始检查
visited = [0 for i in range(len(eulerEdges))] #访问过的路
queue = [] # 保存路径信息
# print(queue)
eulerFlag = False

def isEuler():
    allVisited = True
    for e in visited:
        if e == 0:
            allVisited = False
    if allVisited:
        if queue[0] == queue[len(queue) - 1]:
            return 1
        else:
            return 2
    return 0

def printPath(flag):
    if flag == 1:
        print("是欧拉回路:", end="")
    else:
        print("是欧拉道路:", end="")
    for i in range(len(queue)):
        if i < len(queue) - 1:
            print(queue[i], "-> ", end="")
        else:
            print(queue[i])

# 搜索过程只保存一条路的状态的信息，且不重复经过某一路线
def dfs(u):
    li = queue.append(u)
    flag = isEuler()  # 判断当前路径是不是欧拉路，如果是则打印
    if flag > 0:
        eulerFlag = True
        printPath(flag)
    for i in range(len(eulerEdges)):
        if visited[i] == 1:
            continue
        edge = eulerEdges[i]
        if edge[0] == u:
            visited[i] = 1
            dfs(edge[1])
            #queue.pop()     # 将搜索过的点弹出队列
            # visited[i] = 0  # 重置访问状态
        elif edge[1] == u:
            visited[i] = 1
            dfs(edge[0])
            #queue.pop()     # 将搜索过的点弹出队列
            # visited[i] = 0  # 重置访问状态
dfs(start)
# if not eulerFlag:  # 判断另一种情况
#     print("否则：不是欧拉回路或欧拉道路")

运行结果：

是欧拉道路:3 -> 0 -> 2 -> 1 -> 0 -> 4 -> 5 -> 1 -> 3 -> 5 -> 6 -> 2 -> 9 -> 8 -> 5 -> 11 -> 7 -> 4 -> 10 -> 7 -> 11 -> 8 -> 9 -> 12 -> 6 -> 11