标签:node __ 求解 人工智能 self state action 线代 def
《人工智能:线代方法》 第二部分问题求解 通过搜索进行问题求解(2)
3.4 无信息搜索策略(Blind Search)
![](/i/l/?n=23&i=blog/1571518/202301/1571518-20230129211941311-667344799.png)
![](/i/l/?n=23&i=blog/1571518/202301/1571518-20230129212632692-1136451984.png)
3.4.1 广度优先搜索
![](/i/l/?n=23&i=blog/1571518/202301/1571518-20230129213016877-1852174791.png)
![](/i/l/?n=23&i=blog/1571518/202301/1571518-20230129213038049-1371538187.png)
"""
搜索
创建问题类和问题实例,并通过调用各种搜索函数来解决它们。
"""
import sys
from collections import deque
from utils import *
class Problem:
def __init__(self, initial, goal=None):
self.initial = initial
self.goal = goal
def action(self, state):
raise NotCodeError
def result(self, state, action):
raise NotCodeError
def is_goal(self, state):
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 c + 1
def value(self, state):
raise NodeCodeError
class Node:
"""搜索树中的节点"""
def __init__(self, state, parent=None, action=None, path_cost=0):
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):
return [self.child_node(problem, action)
for action in problem, action]
def child_node(self, problem, action):
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))
def solution(self):
return [node.action for node in self.path()[1:]]
# class Node continued
def path(self):
node, path = self, []
while node:
path_back.append(node)
node = node.parent
return list(reversed(path_back))
def __eq__(self, other):
return isinstance(other, Node) and self.state == other.state
def __hash__(self):
return hash(self.state)
"""
BFS
通过调用函数实现伪代码
"""
def breadth_first_search(problem):
frontier = deque([Node(problem.initial)]) # FIFO queue
while frontier:
node = frontier.popleft()
if problem.is_goal(node.state):
return node
frontier.extend(node.expand(problem))
return None
3.4.2 Dijkstra算法或一致代价搜索
![](/i/l/?n=23&i=blog/1571518/202301/1571518-20230129221235120-1868732467.png)
![](/i/l/?n=23&i=blog/1571518/202301/1571518-20230129220247858-918971617.png)
![](/i/l/?n=23&i=blog/1571518/202301/1571518-20230129220255898-594913843.png)
3.4.3 深度优先搜索和内存问题
3.4.4 深度受限和迭代加深搜索
![](/i/l/?n=23&i=blog/1571518/202301/1571518-20230129220629129-161603244.png)
![](/i/l/?n=23&i=blog/1571518/202301/1571518-20230129220638793-164476062.png)
![](/i/l/?n=23&i=blog/1571518/202301/1571518-20230129220830055-122871411.png)
![](/i/l/?n=23&i=blog/1571518/202301/1571518-20230129220836295-1383225816.png)
![](/i/l/?n=23&i=blog/1571518/202301/1571518-20230129220842378-1304500209.png)
![](/i/l/?n=23&i=blog/1571518/202301/1571518-20230129220850124-42125639.png)
![](/i/l/?n=23&i=blog/1571518/202301/1571518-20230129220909602-1335852456.png)
3.4.5 双向搜索
![](/i/l/?n=23&i=blog/1571518/202301/1571518-20230129220925136-2098113657.png)
3.4.6 无信息搜索算法对比
![](/i/l/?n=23&i=blog/1571518/202301/1571518-20230129220949980-790028525.png)
![](/i/l/?n=23&i=blog/1571518/202301/1571518-20230129221138607-558171681.png)
标签:node,
__,
求解,
人工智能,
self,
state,
action,
线代,
def
From: https://www.cnblogs.com/isLinXu/p/17073974.html