搜索算法的抽象

-灵感来自2024秋的算法设计与分析课-

前言

在这个学期的算法课中，我们重点学习了回溯法和分支限界法两大类搜索算法，过去我总是把DFS、BFS等各种搜索算法分开来，比较其差异，在本文中，我希望对搜索算法做一个抽象，预期可以由一个简洁的抽象模型延伸出我们熟悉的具体的搜索策略。

搜索模型与搜索过程的抽象

用 Haskell 语言展示我总结出的模型：

class (Ord node) => Search env node where 
    initN :: env -> node 
    check :: env -> node -> Bool
    child :: env -> node -> [node]  
    search :: env -> node

Search env node: 搜索需要两个要素，搜索环境 env 和搜索结点 node，且我们需要根据 node 的优先级来决定扩展顺序，那么我们希望 node 之间是可比的（orderable）所以需要给 node 加以 Ord 约束；
initN :: env -> node: 搜索需要初始化，搜索树需要有根节点，所以我们希望可以根据搜索环境 env 生成一个简单的搜索根结点 node ；
check :: env -> node -> Bool: 搜索需要停止，所以我们需要有一个函数可以根据搜索环境 env 的性质，判断当前 node 是否是问题的解；
child :: env -> node -> [node]: 搜素需要可继续，搜索树的活结点是可扩展的，所以我们需要函数 child 根据环境 env 和当前扩展结点 node，生成一系列子结点 [node]；
search :: env -> node: 搜索的主函数，它的目标是在搜索环境中搜索，最终得到终止结点 node ，node 是我们需要的最优解。

如果我们需要写一个具体问题的搜索算法，我们需要给出搜索环境 env 的抽象，结点 node 的设计、并且实现以上的 initN, check, child, search 函数。

搜索模型可以被抽象，搜索过程也可以，于是我提供了 search 函数的默认实现（因为 initN, check, child 往往和具体的问题本身强相关，所以需要实例化的时候提供，无法依赖默认实现）。该函数抽象了搜索的基本过程——搜索总是从根节点（initN）出发，每次检查（check）当前优先级最高的结点是否是问题的一个解，是则返回此结点并结束搜索，否则拓展（child）出其子结点，根据优先级，对活结点列表进行重排，重复迭代此过程：

search e = 
    let 
        step :: [node] -> node
        step (n:ns) 
            | check e n   = n    
            | otherwise = step $ sort (ns ++ child e n) 
    in  step [initN e]

示例：由模型实例化出的TSP搜索

搜索环境，即有向带权图 Graph ，抽象如下：

type Vertex = Int
type Distance = Int 
type Edge = (Vertex, Vertex, Distance)
data Graph = Graph { vertices :: [Vertex], edges :: [Edge] }

另外搜索过程还需依赖图的函数，如 minOut, distance：

minOut :: Graph -> [(Vertex, Distance)]      
minOut (Graph vs es) = [ (v, minimum ds) | 
                            v <- vs,  
                            let es' = filter (\(v1, _, _) -> v1 == v) es,
                            let ds = [ d | (_, _, d) <- es']]

distance :: Graph -> (Int, Int) -> Maybe Distance
distance (Graph _ []) _ = Nothing       
distance (Graph vs ((v1, v2, d):es)) (s, t) 
    | s == v1 && t == v2    = Just d 
    | otherwise             = distance (Graph vs es) (s, t)

结点设计 TspNode：

一个结点需要保存的信息有当前开销 cost，已访问的顶点列表，启发值（总开销上界）：

data TspNode = TspNode {
    cost :: Int,
    visited :: [Vertex],        -- reverse 
    heuristic :: Int    -- heuristic / priority 
} deriving (Show)

结点 heuristic 值越低，其扩展优先级越高：（注意这里的 GT,LT,EQ 不是优先级的大小，而是 heuristic 值的大小，排序函数 sort 将对 node 按 heuristic 升序排列）

instance Ord TspNode where 
    compare :: TspNode -> TspNode -> Ordering
    compare n1 n2 
        | heuristic n1 > heuristic n2 = GT
        | heuristic n1 < heuristic n2 = LT
        | otherwise                   = EQ

搜索函数实例化：

我们需要让 Graph TspNode 成为 Search 类型类的实例，search 可以使用默认实现，所以还需要实现 initN, check, child 函数：

initN:

根节点开销 cost 为 0, 已访问结点列表 visited 为空，开销上界 heuristic 不重要，因为根节点总会被第一个检查并移出活结点列表，永远不会参与排序，所以 heuristic 置 0 即可：
```
initN :: Graph -> TspNode
initN _ = TspNode 0 [] 0
```

check:

如果当前结点已访问了所有顶点（从起点出发，遍历一圈，回到起点），那么判定这是问题的一个解：

check :: Graph -> TspNode -> Bool
check g (TspNode _ vs _)
    | length vs == length (vertices g)    = True
    | otherwise                           = False

child:

总体逻辑与课堂上讲的一致，根据visited列表计算未被访问的相邻结点，若已访问所有其他顶点，那么尝试回到起点：

child :: Graph -> TspNode -> [TspNode]
child g n =
    let 
        upBound :: [Vertex] -> Int
        upBound vs = sum [ d | (s,d) <- minOut g , s `notElem` vs ]

        at = if null (visited n) then 0 else head (visited n)   -- then-clause only for initNode
        nodes = 
            [TspNode cost' visited' heuristic' | 
                v <- filter 
                    (\v' -> v' `notElem` visited n && isJust (distance g (at, v'))) -- or abstract this function to `checkChildValid`
                    ((tail . vertices) g),    -- `tail` for drop the origin vertex (0 here) 
                let way = fromJust $ distance g (at, v),
                let cost' = cost n + way,
                let visited' = v: visited n,
                let heuristic' = upBound visited' + cost']
        back = 
            case distance g (at, 0) of 
                Just wayback -> let cost' = cost n + wayback 
                                    visited' = 0: visited n 
                                    heuristic' = cost' 
                                in [TspNode cost' visited' heuristic']
                Nothing -> []

    in if length (visited n) == length (vertices g) - 1 then back else nodes

程序总体框架：

其他实例简述

我们可以把 DFS 和 BFS 也通过此模型来表现，在数据结构的课上，我们往往分别使用递归、队列+迭代这样两种不一样的程序结构来做实现，那么在这个模型下，改变结点的优先级依据，就改变了搜索拓展结点的选择策略，即改变搜索行为。

假设有这样的一个结点：

data Node a = Node {
    info :: a,          -- 问题相关的具体结点信息
    level :: Int,       -- 结点所在的搜索树的层次
    order :: Int        -- 结点被产生的次序
}

深搜总是拓展当前搜索树中最深的活结点，如果要使用此结点在任意搜索环境下进行深度优先搜索，那么需要将结点的优先级设置为 level ：

instance Ord (Node a) where
    compare :: Node a -> Node a -> Ordering
    compare n1 n2
        | level n1 > level n2 = LT  -- DEPTH first 
        | level n1 < level n2 = LT
        | otherwise           = EQ

宽搜总是拓展当前搜索树中最早被生成的活结点，如果要使用此结点在任意搜索环境下进行宽度优先搜索，那么需要将结点的优先级设置为 order：

instance Ord (Node a) where
    compare :: Node a -> Node a -> Ordering
    compare n1 n2
        | order n1 > order n2 = LT  -- BREADTH first 
        | order n1 < order n2 = LT
        | otherwise           = EQ

不足之处

没有将该搜索抽象应用于更多的具体问题：

本来是准备把课本的经典案例都用基于此模型实现一遍，但是——时间不够了，DDL就在眼前，所以只提供了TSP问题在该模型下的实例化；
解的数量：

这里我将解的数量限制为1，默认将第一个解作为问题的解，这在部分情况下是有效的，例如这里实现的TSP问题，因为heuristic的计算逻辑保证了首解就是最优解，但是也可能存在其他情况，(a) 首解只是最优解的近似，最优解可能在后面产生，(b) 需要保留多个解，这些情况都是目前的模型无法处理的。