无信息搜索

1. 无信息搜索概念

$a.$边界（$frontier$）

边界是当前已发现，但是还未被拓展的节点的集合，是搜索的边界。

$b.$边界的拓展（$expand$）

在搜索过程中，我们会展开当前边界的所有可能的后继状态，并把它加入边界中。这相当于下一步Search的探索动作。然后当前的边界就会被丢弃。

$c.$搜索的评估标准

• 完备性 (Completeness) - 如果搜索问题存在解，该策略是否保证在无限计算资源下找到它？
• 最优性 (Optimality) - 该策略是否保证找到到目标状态的最低成本路径？
• 分支因子 $b$ - 每次边界节点出队并被其子节点替换时，边界上节点数量的增加为$O(b)$。在搜索树的深度$k$处，存在$O(b^k)$个节点。
• 最大深度 $m$。
• 最浅解的深度 $s$。

2. 树搜索结构

大多数搜索算法的实现都会在节点对象内部编码关于父节点、到节点的距离以及状态的信息，这个过程被称为树搜索。

根据树搜索的特征，可以如下初始化节点结构：

class Node:
    """Node in search tree"""
    def __init__(self, state, parent=None, action=None, path_cost=None):
        self.state = state
        self.parent = parent
        self.action = action
        self.path_cost = path_cost
        self.depth = 0 if self.depth == None else parent.depth + 1

并定义如下的问题模型：

class Problem(ABC):
    """problem abstract class"""

    def __init__(self, initial_state):
        self.initial_state = initial_state
    
    @abstractmethod
    def actions(self, state):
        """return action lists"""
        pass
    
    @abstractmethod
    def result(self, state, action):
        """return action result"""
        pass
    
    @abstractmethod
    def is_goal(self, state):
        """return if current state is goal state"""
        pass
    
    def step_cost(self, state, action, next_state):
        """return the cost from state to next_state"""
        return 1

然后树搜索和边界拓展的流程即可如下表示：

def expand(problem, node):
    # store current node's state
    s = node.state
    for action in problem.actions(s):
        s_prime = problem.result(s, action)
        cost = node.path_cost + problem.step_cost(s, action, s_prime)

        # generate frontier node
        yield Node(state=s_prime, parent=node, action=action, path_cost=cost)

def make_node(initial_state):
    return Node(initial_state)

def tree_search(problem, frontier):
    # add previous state
    frontier.add(make_node(problem.initial_state))

    # start searching
    while not frontier.is_empty():
        # remove current node and expand frontier
        node = frontier.remove()

        if problem.is_goal(node.state):
            return node

        for child_node in expand(problem, node):
            frontier.add(child_node)

    return None

3. 深度优先搜索（DFS）

$a.$相关概念

• 边界表示：在深度有限搜索中，我们移除最深的节点并用其子节点替换。这意味着子节点现在是新的最深节点——它们的深度比前一个最深节点的深度大1。
• 完备性：深度优先搜索是不完备的。如果状态空间图中存在循环，这不可避免地意味着相应的搜索树在深度上是无限的。
• 最优性：深度优先搜索只是简单地找到搜索树中“最左边”的解，而不考虑路径成本，因此不是最优的。
• 时间复杂度：在最坏的情况下，深度优先搜索可能最终会探索整个搜索树。因此，给定一个最大深度为$m$的树，DFS的运行时间是$O(b^m)$。

• 空间复杂度：考虑一棵结构“不幸”的树，并用栈模拟搜索：
  • 在深度0：我们访问根节点，并将其所有$b$个子节点压入栈。此时栈的大小为$b$。
  • 在深度1：算法从栈顶弹出一个节点$C1$进行探索。然后，它将$C1$的所有$b$个子节点压入栈。此时栈的大小变成了$(b-1) + b$。$b-1$是上一层未访问的兄弟节点，$b$是当前层新加入的子节点。
  • 在深度$d$：当我们沿着一条路径深入到深度$d$时，栈里有
    • 当前节点（深度$d$）的所有兄弟节点。数量最多为$b-1$。
    • 父节点（深度$d-1$）的所有兄弟节点。数量最多为$b-1$。

栈的总大小 $\approx (b-1) + (b-1) + ... + (b-1)$ （共$m$项），栈的总大小$\approx m * (b-1)$。

$b.$简单实现

搜索算法的核心在于边界的拓展，我们定义如下的类来表示边界：

class Frontier(ABC):
    @abstractmethod
    def add(self, node):
        pass

    @abstractmethod
    def remove(self):
        pass

    @abstractmethod
    def is_empty(self):
        pass

然后使用栈结构模拟DFS的边界拓展流程：

class StackFrontier(Frontier):
    def __init__(self):
        self.stack = []
    
    def add(self, node):
        self.stack.append(node)

    def remove(self):
        if self.is_empty():
            raise Exception("Cannot remove from empty frontier")
        return self.stack.pop()
    
    def is_empty(self):
        return len(self.stack) == 0

然后将DFS的边界传入到树搜索中即可：

def depth_first_search(problem):
    return tree_search(problem, StackFrontier())

4. 广度优先搜索（BFS）

$a.$相关概念

• 描述：在广度优先搜索（BFS）是一种探索策略，总是选择从起始节点开始最浅的边界节点进行扩展。
• 边界表示：如果我们想在访问更深的节点之前访问更浅的节点，我们必须按插入顺序访问节点。因此，我们希望有一个结构能够输出最早入队的对象来表示我们的边界。
• 完备性：如果存在解，那么最浅节点$s$的深度必须是有限的，所以BFS最终必须搜索到这个深度。因此，它是完备的。
• 最优性：BFS通常不是最优的，因为它在决定替换边界上的哪个节点时不考虑成本。BFS保证最优的特殊情况是所有边成本都相等，因为这将BFS简化为下面讨论的统一成本搜索的特例。
• 时间复杂度： 在最坏的情况下，我们必须搜索$1 + b + b^2 + \ldots + b^s$个节点，因为我们遍历了从1到$s$的每个深度的所有节点。因此，时间复杂度是$O(b^s)$。
• 空间复杂度 - 在最坏的情况下，边界包含对应于最浅解的层级中的所有节点。由于最浅的解位于深度$s$，因此在该深度有$O(b^s)$个节点。

$b.$简单实现

同样，我们使用队列结构来实现BFS的边界拓展流程：

from collections import deque

class QueueFrontier(Frontier):
    def __init__(self):
        self.queue = deque()
    
    def add(self, node):
        self.queue.append(node)

    def remove(self):
        return self.queue.popleft()

    def is_empty(self):
        return len(self.queue) == 0

def breadth_first_search(problem):
    return tree_search(problem, QueueFrontier())

5. 统一成本搜索（Uniform Cost Search）

$a.$相关概念

• 描述: 统一成本搜索总是选择从起始节点开始成本最低的边界节点进行扩展。
• 边界表示: 为了表示UCS的边界，通常选择基于堆的优先队列，其中给定入队节点$v$的优先级是从起始节点到$v$的路径成本，或$v$的反向成本。直观地说，以这种方式构建的优先队列在我们移除当前最小成本路径并用其子节点替换时，会简单地重新排列自身以维持按路径成本的期望顺序。
• 完备性：统一成本搜索是完备的。如果存在目标状态，它必须有某个有限长度的最短路径；因此，UCS最终必须找到这个最短长度的路径。
• 最优性：如果我们假设所有边成本都是非负的，UCS也是最优的。通过构造，由于我们按路径成本递增的顺序探索节点，我们保证能找到到目标状态的最低成本路径。
• 时间复杂度：将最优路径成本定义为$C^*$，状态空间图中两个节点之间的最小成本定义为$\epsilon$。那么，在最差的情况下，我们必须探索深度从1到$C^*/\epsilon$的所有节点，导致运行时间为$O(b^{C^*/\epsilon})$。
• 空间复杂度：我们可以类比BFS的空间复杂度计算来得出UCS的空间复杂度。在UCS取出最优解之前，边界中可能包含所有路径成本小于$C^*$的节点，而每一层的最小路径成本为$\epsilon$，那么UCS的“等效深度”就是$C^*/\epsilon$，根据BFS的空间复杂度计算公式，即得UCS的空间复杂度为$O(b^{C^*/\epsilon})$。

$b.$简单实现

我们使用优先队列来实现UCS的边界拓展流程：

import heapq

class PriorityQueueFrontier(Frontier):
    def __init__(self):
        self.heap = []
        
        # deal with identical priority
        self.counter = 0 
    
    def add(self, node):
        heapq.heappush(self.heap, (node.path_cost, self.counter, node))
        self.counter += 1

    def remove(self):
        _, _, node = heapq.heappop(self.heap)
        return node

    def is_empty(self):
        return len(self.heap) == 0

def uniform_cost_search(problem):
    return tree_search(problem, PriorityQueueFrontier())