当前位置:   article > 正文

罗马尼亚旅游问题 贪婪最佳优先搜索 A*搜索【python】_python从arad到bucharest的最短路径

python从arad到bucharest的最短路径


一、问题描述

在罗马尼亚旅游问题中,搜索从城市Arad出发到达Bucharest的路径。其中neighbor_map可以得到所需要的城市和哪些城市相邻,比如:Arad有三个邻居:Zerind,Sibiu,Timisora,由Arad到达这三个城市的代价可由以下字典neighbormapWithweight获得。城市的坐标由如下字典提供,Romania_map_location。
请用贪婪最佳优先搜索和A*搜索求出最短路径。

在这里插入图片描述
字典如下:

neighbor_map = {'Arad': ['Zerind', 'Sibiu', 'Timisoara'], 'Bucharest': ['Urziceni', 'Pitesti', 'Giurgiu', 'Fagaras'],
                'Craiova': ['Drobeta', 'Rimnicu', 'Pitesti'], 'Drobeta': ['Mehadia'], 'Eforie': ['Hirsova'],
                'Fagaras': ['Sibiu'], 'Hirsova': ['Urziceni'], 'Iasi': ['Vaslui', 'Neamt'],
                'Lugoj': ['Timisoara', 'Mehadia'],
                'Oradea': ['Zerind', 'Sibiu'], 'Pitesti': ['Rimnicu'], 'Rimnicu': ['Sibiu'], 'Urziceni': ['Vaslui']}

neighbormapWithweight = {'Arad': {'Zerind': 75, 'Sibiu': 140, 'Timisoara': 118},
                         'Bucharest': {'Urziceni': 85, 'Pitesti': 101, 'Giurgiu': 90, 'Fagaras': 211},
                         'Craiova': {'Drobeta': 120, 'Rimnicu': 146, 'Pitesti': 138},
                         'Drobeta': {'Mehadia': 75},
                         'Eforie': {'Hirsova': 86},
                         'Fagaras': {'Sibiu': 99},
                         'Hirsova': {'Urziceni': 98},
                         'Iasi': {'Vaslui': 92, 'Neamt': 87},
                         'Lugoj': {'Timisoara': 111, 'Mehadia': 70},
                         'Oradea': {'Zerind': 71, 'Sibiu': 151},
                         'Pitesti': {'Rimnicu': 97},
                         'Rimnicu': {'Sibiu': 80},
                         'Urziceni': {'Vaslui': 142}
                         }

romania_map_locations = dict(
    Arad=(91, 492), Bucharest=(400, 327), Craiova=(253, 288),
    Drobeta=(165, 299), Eforie=(562, 293), Fagaras=(305, 449),
    Giurgiu=(375, 270), Hirsova=(534, 350), Iasi=(473, 506),
    Lugoj=(165, 379), Mehadia=(168, 339), Neamt=(406, 537),
    Oradea=(131, 571), Pitesti=(320, 368), Rimnicu=(233, 410),
    Sibiu=(207, 457), Timisoara=(94, 410), Urziceni=(456, 350),
    Vaslui=(509, 444), Zerind=(108, 531))

  • 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

二、贪婪最佳优先搜索和A*搜索的理解

1.贪婪最佳优先搜索

  • 贪婪优先搜索试图优先扩展最接近目标的结点,通过一个启发函数h(n)来预测结点是否接近目标。
  • h(n)=结点n到目标节点的最小代价路径的代价估计值
  • 这个代价估计值可以是题目中给出的,或者是两点之间的距离——例如:曼哈顿距离、欧式距离等。
  • 贪婪优先搜索类似于深度优先搜索。通过不断扩展frontier表中具有最小代价值的结点进行搜索。
  • 贪婪优先搜索有时可能找不到解。

贪婪优先搜索的搜索过程:
贪婪优先算法
如上图所示,贪婪优先算法先扩展frontier表中代价最小的结点。在本例中,由于路径距离在不断减小,于是不会回溯并走到其他的路线上,而若其他路径可拓展的结点还有更小的代价,根据算法就会优先拓展代价更小的结点。

2.A*搜索算法

在写这一篇内容之前我完全理解错了A*搜索的含义,我将根据书籍资料,以及我理解错误的点对其进行深入说明

  • A*算法综合了贪婪最佳优先搜索和一致代价搜索。但是,其算法本质就是一致代价搜索!因为它只是改变了一致代价搜索中对于frontier表的排序条件,改用累计代价和预估代价的和来进行排序,而不改变其他。
    • 一致代价搜索是优先扩展所有可拓展结点中累计代价最小的一个。也就是无论搜索的步数到达到达哪一步,该算法总是首先考虑所有可拓展的结点中,从开始结点到该结点的代价和最小的结点。其算法将附图在下方。
  • 它判断寻找新结点的方式是通过f(n)=g(n)+h(n)。h(n)我们在贪婪优先搜索中说过是一个启发函数,表示从n结点到目标结点的代价估计值。而g(n)则是一致代价中从开始结点到n结点的已知代价。
  • 在满足可采纳性条件一致性条件的情况下,该算法可以求出最优解。

一致代价搜索的伪代码:
在这里插入图片描述

A*搜索的搜索过程:
在这里插入图片描述

三、A*搜索的代码

1.A*搜索的思路

因为A*搜索的本质就是一致代价搜索,所以依据上述一致代价搜索的伪代码,将frontier表中的排序方式按照f(n)来进行就可以。
但是在题目中给出的字典表并不全面,搜索过程中可能会出现有些困难的部分,所以我先进行了基本的字典表处理,处理过程在第四部分内容中有进行注释,结果如下:

#邻接城市表:
{'Zerind': {'Arad': 75, 'Oradea': 71},
 'Sibiu': {'Arad': 140, 'Fagaras': 99, 'Oradea': 151, 'Rimnicu': 80},
 'Lugoj': {'Timisoara': 111, 'Mehadia': 70},
 'Rimnicu': {'Sibiu': 80, 'Craiova': 146, 'Pitesti': 97},
 'Timisoara': {'Arad': 118, 'Lugoj': 111},
 'Drobeta': {'Mehadia': 75, 'Craiova': 120},
 'Fagaras': {'Sibiu': 99, 'Bucharest': 211},
 'Vaslui': {'Iasi': 92, 'Urziceni': 142},
 'Arad': {'Zerind': 75, 'Sibiu': 140, 'Timisoara': 118},
 'Craiova': {'Drobeta': 120, 'Rimnicu': 146, 'Pitesti': 138},
 'Neamt': {'Iasi': 87},
 'Iasi': {'Vaslui': 92, 'Neamt': 87},
 'Hirsova': {'Urziceni': 98, 'Eforie': 86},
 'Oradea': {'Zerind': 71, 'Sibiu': 151},
 'Giurgiu': {'Bucharest': 90},
 'Pitesti': {'Rimnicu': 97, 'Bucharest': 101, 'Craiova': 138},
 'Eforie': {'Hirsova': 86},
 'Urziceni': {'Vaslui': 142, 'Bucharest': 85, 'Hirsova': 98},
 'Bucharest': {'Urziceni': 85, 'Pitesti': 101, 'Giurgiu': 90, 'Fagaras': 211},
 'Mehadia': {'Drobeta': 75, 'Lugoj': 70}}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22

然后依据给出的Problem和Node类补全其余代码即可。

2.A*搜索的代码

import math
import sys
from collections import deque


class Problem:
    """The abstract class for a formal problem. You should subclass
    this and implement the methods actions and result, and possibly
    __init__, goal_test, and path_cost. Then you will create instances
    of your subclass and solve them with the various search functions."""

    def __init__(self, initial, goal=None):
        """The constructor specifies the initial state, and possibly a goal
        state, if there is a unique goal. Your subclass's constructor can add
        other arguments."""
        self.initial = initial
        self.goal = goal

    def actions(self, state):
        """Return the actions that can be executed in the given
        state. The result would typically be a list, but if there are
        many actions, consider yielding them one at a time in an
        iterator, rather than building them all at once."""
        raise NotImplementedError

    def result(self, state, action):
        """Return the state that results from executing the given
        action in the given state. The action must be one of
        self.actions(state)."""
        raise NotImplementedError

    def goal_test(self, state):
        """Return True if the state is a goal. The default method compares the
        state to self.goal or checks for state in self.goal if it is a
        list, as specified in the constructor. Override this method if
        checking against a single self.goal is not enough."""
        if isinstance(self.goal, list):
            return is_in(state, self.goal)
        else:
            return state == self.goal

    def path_cost(self, c, state1, action, state2):
        """Return the cost of a solution path that arrives at state2 from
        state1 via action, assuming cost c to get up to state1. If the problem
        is such that the path doesn't matter, this function will only look at
        state2. If the path does matter, it will consider c and maybe state1
        and action. The default method costs 1 for every step in the path."""
        return c + 1

    def value(self, state):
        """For optimization problems, each state has a value. Hill Climbing
        and related algorithms try to maximize this value."""
        raise NotImplementedError


# ______________________________________________________________________________


class Node:
    """A node in a search tree. Contains a pointer to the parent (the node
    that this is a successor of) and to the actual state for this node. Note
    that if a state is arrived at by two paths, then there are two nodes with
    the same state. Also includes the action that got us to this state, and
    the total path_cost (also known as g) to reach the node. Other functions
    may add an f and h value; see best_first_graph_search and astar_search for
    an explanation of how the f and h values are handled. You will not need to
    subclass this class."""

    def __init__(self, state, parent=None, action=None, path_cost=0):
        """Create a search tree Node, derived from a parent by an action."""
        self.state = state
        self.parent = parent
        self.action = action
        self.path_cost = path_cost
        self.depth = 0
        if parent:
            self.depth = parent.depth + 1

    def __repr__(self):
        return "<Node {}>".format(self.state)

    def __lt__(self, node):
        return self.state < node.state

    def expand(self, problem):
        """List the nodes reachable in one step from this node."""
        return [self.child_node(problem, action)
                for action in problem.actions(self.state)]

    def child_node(self, problem, action):
        """[Figure 3.10]"""
        next_state = problem.result(self.state, action)
        next_node = Node(next_state, self, action, problem.path_cost(self.path_cost, self.state, action, next_state))
        return next_node

    def solution(self):
        """Return the sequence of actions to go from the root to this node."""
        return [node.state for node in self.path()[0:]]

    def path(self):
        """Return a list of nodes forming the path from the root to this node."""
        node, path_back = self, []
        while node:
            path_back.append(node)
            node = node.parent
        return list(reversed(path_back))

    # We want for a queue of nodes in breadth_first_graph_search or
    # astar_search to have no duplicated states, so we treat nodes
    # with the same state as equal. [Problem: this may not be what you
    # want in other contexts.]

    def __eq__(self, other):
        return isinstance(other, Node) and self.state == other.state

    def __hash__(self):
        # We use the hash value of the state
        # stored in the node instead of the node
        # object itself to quickly search a node
        # with the same state in a Hash Table
        return hash(self.state)


neighbor_map = {'Arad': ['Zerind', 'Sibiu', 'Timisoara'], 'Bucharest': ['Urziceni', 'Pitesti', 'Giurgiu', 'Fagaras'],
                'Craiova': ['Drobeta', 'Rimnicu', 'Pitesti'], 'Drobeta': ['Mehadia'], 'Eforie': ['Hirsova'],
                'Fagaras': ['Sibiu'], 'Hirsova': ['Urziceni'], 'Iasi': ['Vaslui', 'Neamt'],
                'Lugoj': ['Timisoara', 'Mehadia'],
                'Oradea': ['Zerind', 'Sibiu'], 'Pitesti': ['Rimnicu'], 'Rimnicu': ['Sibiu'], 'Urziceni': ['Vaslui']}

neighbormapWithweight = {'Arad': {'Zerind': 75, 'Sibiu': 140, 'Timisoara': 118},
                         'Bucharest': {'Urziceni': 85, 'Pitesti': 101, 'Giurgiu': 90, 'Fagaras': 211},
                         'Craiova': {'Drobeta': 120, 'Rimnicu': 146, 'Pitesti': 138},
                         'Drobeta': {'Mehadia': 75},
                         'Eforie': {'Hirsova': 86},
                         'Fagaras': {'Sibiu': 99},
                         'Hirsova': {'Urziceni': 98},
                         'Iasi': {'Vaslui': 92, 'Neamt': 87},
                         'Lugoj': {'Timisoara': 111, 'Mehadia': 70},
                         'Oradea': {'Zerind': 71, 'Sibiu': 151},
                         'Pitesti': {'Rimnicu': 97},
                         'Rimnicu': {'Sibiu': 80},
                         'Urziceni': {'Vaslui': 142}
                         }

romania_map_locations = dict(
    Arad=(91, 492), Bucharest=(400, 327), Craiova=(253, 288),
    Drobeta=(165, 299), Eforie=(562, 293), Fagaras=(305, 449),
    Giurgiu=(375, 270), Hirsova=(534, 350), Iasi=(473, 506),
    Lugoj=(165, 379), Mehadia=(168, 339), Neamt=(406, 537),
    Oradea=(131, 571), Pitesti=(320, 368), Rimnicu=(233, 410),
    Sibiu=(207, 457), Timisoara=(94, 410), Urziceni=(456, 350),
    Vaslui=(509, 444), Zerind=(108, 531))

straight_line_distance_to_Bucharest = dict(
    Arad=366, Bucharest=0, Craiova=160,
    Drobeta=242, Eforie=161, Fagaras=178,
    Giurgiu=77, Hirsova=151, Iasi=266,
    Lugoj=244, Mehadia=241, Neamt=234,
    Oradea=380, Pitesti=98, Rimnicu=193,
    Sibiu=253, Timisoara=329, Urziceni=80,
    Vaslui=199, Zerind=374)

"""将通过每一个城市都可以找到它的邻居"""
all_city_neighbor = set(neighbor_map)

for i in neighbor_map:
    for a_city in neighbor_map[i]:
        if a_city not in all_city_neighbor:
            all_city_neighbor.add(a_city)

city_neighbor = {a: {} for a in all_city_neighbor}

for i in city_neighbor:
    if i in neighbormapWithweight:
        city_neighbor[i] = neighbormapWithweight[i]
for i in city_neighbor:
    for j in neighbormapWithweight:
        if i in neighbormapWithweight[j]:
            city_neighbor[i][j] = neighbormapWithweight[j][i]
print(city_neighbor)

start = "Arad"
goal = "Bucharest"

start_to_goal_distance = dict()
for i in romania_map_locations:
    """用曼哈顿距离"""
    # start_to_goal_distance[i] = abs(romania_map_locations[i][0] - romania_map_locations[goal][0]) \
    #                             + abs(romania_map_locations[i][1] - romania_map_locations[goal][1])
    """用A-B启发函数值"""
    # start_to_goal_distance[i] = straight_line_distance_to_Bucharest[i]
    """用直线距离"""
    start_to_goal_distance[i] = math.sqrt((romania_map_locations[i][0] - romania_map_locations[goal][0]) ** 2
                                          + (romania_map_locations[i][1] - romania_map_locations[goal][1]) ** 2)
print(start_to_goal_distance)

"""A*搜索——类似于一致代价搜索"""
def astar_search(problem):
    node_new = Node(problem.initial)  # 初始化node结点
    frontier = []  # frontier表的初始化
    frontier.append(node_new)  # 添加初始结点
    explored = []  # explored表初始化

    while True:
        # 当frontier表中没有结果时返回失败
        if len(frontier) == 0:
            return
        # 从frontier表中取出最优的结点拓展
        node_new = frontier[0]
        # 从frontier表中删除已经拓展的结点
        del frontier[0]
        # 若找到目标结点则对路径进行输出
        if problem.goal_test(node_new.state):
            print("最小的代价值为", node_new.path_cost)
            return node_new.solution()
        # 将已经搜索表拓展新的结点
        explored.append(node_new)
        # 搜索并拓展新的frontier表
        for p in city_neighbor[node_new.state]:
            child = Node(p, node_new, None, (city_neighbor[node_new.state][p] + node_new.path_cost))
            # 如果新的子结点不在explored和frontier中,则在frontier表中加入新的拓展结点
            figure = 0
            for i in explored or frontier:
                if i.state == child.state:
                    figure += 1
            if figure <= 0:
            # if child.state not in explored or frontier:
                frontier.append(Node(child.state, node_new, None, child.path_cost))
            # 如果新结点在frontier中,则更新其一致代价
            else:
                for i in frontier:
                    if i.state == child.state:
                        if i.path_cost < child.path_cost:
                            i.path_cost = child.path_cost
                            break
        # 对新加入的结点或者更新的结点进行排序
        frontier = sorted(frontier, key=lambda x: x.path_cost + start_to_goal_distance[x.state])

"""实现并输出A*搜索的路径"""
romania_problem = Problem(start, goal)
road = astar_search(romania_problem)
print(road)
  • 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
  • 132
  • 133
  • 134
  • 135
  • 136
  • 137
  • 138
  • 139
  • 140
  • 141
  • 142
  • 143
  • 144
  • 145
  • 146
  • 147
  • 148
  • 149
  • 150
  • 151
  • 152
  • 153
  • 154
  • 155
  • 156
  • 157
  • 158
  • 159
  • 160
  • 161
  • 162
  • 163
  • 164
  • 165
  • 166
  • 167
  • 168
  • 169
  • 170
  • 171
  • 172
  • 173
  • 174
  • 175
  • 176
  • 177
  • 178
  • 179
  • 180
  • 181
  • 182
  • 183
  • 184
  • 185
  • 186
  • 187
  • 188
  • 189
  • 190
  • 191
  • 192
  • 193
  • 194
  • 195
  • 196
  • 197
  • 198
  • 199
  • 200
  • 201
  • 202
  • 203
  • 204
  • 205
  • 206
  • 207
  • 208
  • 209
  • 210
  • 211
  • 212
  • 213
  • 214
  • 215
  • 216
  • 217
  • 218
  • 219
  • 220
  • 221
  • 222
  • 223
  • 224
  • 225
  • 226
  • 227
  • 228
  • 229
  • 230
  • 231
  • 232
  • 233
  • 234
  • 235
  • 236
  • 237
  • 238
  • 239
  • 240
  • 241
  • 242

四、结果与两种算法的对比

贪婪优先算法和A算法结果对比:
请添加图片描述
其中红线表示贪婪最佳优先搜索结果,蓝线表示A搜索。

  • 完备性角度上分析,因为测试的数据很少,所以无论是贪婪最佳优先搜索和A算法都可以找到最终的解,但是由于贪婪最佳优先搜索的性质,存在无解的情况,而A算法在满足一致性条件和可采纳性条件的情况下一定能求出解。
  • 最优性角度上分析:通过罗马尼亚旅游问题可以看出,A*搜索算法的结果要明显优于贪婪最佳优先搜索,并且在满足一致性条件和可采纳性条件的基础上可以求出最优解。
  • 时间和空间复杂度角度上分析:因为这两种算法虽然搜索的算法是相似的,A*是贪婪最佳优先算法的优化算法,只有启发函数的判断存在差异,所以时间和空间复杂度可以判断为相同。

该篇内容和算法思路来源于《人工智能:一种现代的方法(第3版)》,仅作为学习分享用。

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/不正经/article/detail/194891?site
推荐阅读
相关标签
  

闽ICP备14008679号