罗马尼亚旅游问题 贪婪最佳优先搜索 A*搜索【python】_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版）》，仅作为学习分享用。