搜索算法的形式化描述：状态、动作、状态转移、路径、测试目标
状态：从原问题转化出的问题描述；
动作：从当前时刻所处状态转移到下一时刻所处状态所进行操作，一般而言这些操作都是离散的；
状态转移：对某一时刻对应状态进行某一种操作后，所能够到达状态；
路径：一个状态序列，该状态序列被一系列操作所连接；
测试目标：评估当前状态是否为所求解的目标状态；
问题：寻找从Arad到Bucharest的一条最短路径
辅助信息：任意一个城市与Bucharest的直线距离
代码实现
import sys
from collections import deque
class Romania:
"""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."""
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']
}
straight_line = {'Arad': 366, 'Bucharest': 0,'Craiova': 160,'Drobeta': 242, 'Eforie': 161,'Fagaras': 178, 'Giurgiu': 77, 'Hirsova': 151,'Iasi': 226, 'Lugoj': 244,
'Mehadia': 241,'Neamt': 234,'Oradea': 380, 'Pitesti': 98,'Rimnicu': 193,'Sibiu': 253,'Timisoara': 329,'Urziceni': 80,
'Vaslui': 199,'Zerind': 374,
}
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,'Craiova':120},
'Eforie': {'Hirsova': 86},
'Fagaras': {'Sibiu': 99,'Bucharest':211},
'Hirsova': {'Urziceni': 98,'Eforie':86},
'Iasi': {'Vaslui': 92, 'Neamt': 87},
'Lugoj': {'Timisoara': 111, 'Mehadia': 70},
'Oradea': {'Zerind': 71, 'Sibiu': 151},
'Pitesti': {'Rimnicu': 97,'Craiova':138,'Bucharest':101},
'Rimnicu': {'Sibiu': 80,'Craiova':146,'Pitesti':97},
'Urziceni': {'Vaslui': 142,'Bucharest':85,'Hirsova':98},
'Zerind':{'Arad':75,'Oradea':71},
'Timisoara':{'Arad':118,'Logoj':111},
'Mehadia':{'Lugoj':70,'Drobeta':75},
'Sibiu':{'Oradea':151,'Arad':140,'Rimnicu':80,'Fagaras':99},
'Giurgiu':{'Bucharest':90},
'Neamt':{'Iasi':87},
'Vaslui':{'Iasi':92,'Urziceni':142}
}
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
# actions返回该城市能到达的所有城市，返回一个列表
def actions(self, state):
citys=[]
# 根据字典的值查找键
for item in self.neighbor_map:
for city in self.neighbor_map.get(item):
if city == state:
citys.append(item)
if self.neighbor_map.get(state):
return self.neighbor_map.get(state) + citys
else:
return citys
# result返回该城市到终点的距离，即启发函数的值
def result(self, action):
return self.straight_line.get(action)
def goal_test(self, state):
return state == self.goal
# path——cost返回从state1到达state2的路程
def path_cost(self, state1, state2):
return self.neighbormapWithweight.get(state1).get(state2)
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 "".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."""
if problem.actions(self.state):
return [self.child_node(action)
for action in problem.actions(self.state)]
def child_node(self, action):
"""[Figure 3.10]"""
next_state = action
next_node = Node(next_state, self, action,path_cost=self.path_cost+problem.path_cost(self.state,action))
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)
problem=Romania('Arad','Bucharest')
start=Node('Arad')
frontier = []
explored = set()
frontier.append(start)
while 1:
node = frontier.pop()
if problem.goal_test(node.state):
print('贪婪搜索最佳路线为：')
print(node.solution())
print('贪婪搜索最佳路线长度为：')
print(node.path_cost)
break
else:
explored.add(node.state)
for node1 in node.expand(problem):
if node1.state not in explored:
frontier.append(node1)
frontier.sort(key=lambda x: problem.result(x.state),reverse=True)
A*搜索将最后一句更换为
frontier.sort(key=lambda x: problem.result(x.state)+x.path_cost,reverse=True)
实现结果
A*最佳路线为： ['Arad', 'Sibiu', 'Rimnicu', 'Pitesti', 'Bucharest'] A*搜索最佳路线长度为： 418
贪婪搜索最佳路线为： ['Arad', 'Sibiu', 'Fagaras', 'Bucharest'] 贪婪搜索最佳路线长度为： 450
