《人工智能：线代方法》 第二部分问题求解 通过搜索进行问题求解(2)

3.4 无信息搜索策略(Blind Search)

3.4.1 广度优先搜索

• 代码实现

"""
搜索
创建问题类和问题实例，并通过调用各种搜索函数来解决它们。
"""
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算法或一致代价搜索

3.4.3 深度优先搜索和内存问题

3.4.4 深度受限和迭代加深搜索

3.4.5 双向搜索

3.4.6 无信息搜索算法对比