搜索算法-递归风格

深度优先搜索

原理：
图 $G$ 中，无环路的路径 $x\to v, v\in W$ (目标顶点), 且不经过顶点集 $x \not \in V$ ：

如果 $x\in W$ , 则单顶点路径 $w$ 是这样的路径
$x\to y \to v, v\in W$ 是这样的路径，其中 $y\to v$ 是无环路径，且不经过 $x,V$

伪代码

function dfs(start, isgoal, visited=[])
    if isgoal(start)
        return [start]
    else
        push start to visited
    for child in children of start excluding visited
        path = dfs(child, isgoal, visited)
        if path is not empty
            return [start] + path
    else
        # has no child or no child returns a path
        return []

Python 实现

def dfsi(start, isgoal, visited=[]):
    if isgoal(start):
        return [start]
    else:
        visited += [start]
    for child in rule(start):
        if child not in visited:
            path = dfsi(child, isgoal, visited)
            if path:
                return [start] + path
            else:
                visited.append(child)
    else:
        return []

graph = {'A':{'B','C'},'B':{'D','E'}, 'C':{'E', 'F', 'H'}, 'D':{'I', 'J'}, 'E':{'G', 'K'}, 'F':{'L','M', 'H'}, 'H':{'N', 'M'}}

rule = lambda x: graph.get(x, {})
isgoal = lambda x: x == 'N'
p = dfsi('A', isgoal)
print(p)
# => ['A', 'C', 'F', 'H', 'N']

宽度有限搜索

伪代码

function bfs(starts, isgoal, possible=None, visited=[])
     for start in starts
        if start is goal
            return [start]
        else
            push start to visited
    new_starts =[]
    if possible is None
        possible = [[start] for start in starts]
    new_possible = []
    for start, path in zip(starts, possible)
        for child in rule(start) excluding visited
                if child is goal
                    return path + [child]
                else
                    push child to new_starts
                    push path + [child] to new_possible
    return bfsi(new_starts, isgoal, new_possible, visited)

稍微简化一下，完全等价，但是减少了存储。

function bfs(starts, isgoal, possible=None, visited=[])
     for start in starts
        if start is goal
            return [start]
        else
            push start to visited
    new_starts =[]
    if possible is None
        possible = [[] for start in starts]
    new_possible = []
    for start, path in zip(starts, possible)
        for child in rule(start) excluding visited
                if child is goal
                    return path + [start, child]
                else
                    push child to new_starts
                    push path + [start] to new_possible
    return bfsi(new_starts, isgoal, new_possible, visited)

Python 实现


def bfsi(starts, isgoal, possible=None, visited=[]):

    for start in starts:
        if isgoal(start):
            return [start]
        else:
            visited.append(start)
    new_starts =[]
    if possible is None:
        possible = [[start] for start in starts]
    new_possible = []
    for start, path in zip(starts, possible):
        for child in rule(start):
            if child not in visited:
                if isgoal(child):
                    return path + [child]
                else:
                    new_starts.append(child)
                    new_possible.append(path + [child])
    return bfsi(new_starts, isgoal, new_possible, visited)

graph = {'A':{'B','C'},'B':{'D','E'}, 'C':{'E', 'F', 'H'}, 'D':{'I', 'J'}, 'E':{'G', 'K'}, 'F':{'L','M', 'H'}, 'H':{'N', 'M'}}

rule = lambda x: graph.get(x, {})
isgoal = lambda x: x == 'N'
p = bfsi(['A'], isgoal)
print(p)

# 等价地
def bfsi(starts, isgoal, possible=None, visited=[]):

    for start in starts:
        if isgoal(start):
            return [start]
        else:
            visited.append(start)
    new_starts =[]
    if possible is None:
        possible = [[] for start in starts]
    new_possible = []
    for start, path in zip(starts, possible):
        for child in rule(start):
            if child not in visited:
                if isgoal(child):
                    return path + [start, child]
                else:
                    new_starts.append(child)
                    new_possible.append(path + [start])
    return bfsi(new_starts, isgoal, new_possible, visited)

或者简单封装一下

def bfsi(start, isgoal, possible=None, visited=[]):

    def _bfsi(starts, isgoal, possible=None, visited=[]):

        for start in starts:
            if isgoal(start):
                return [start]
            else:
                visited.append(start)
        new_starts =[]
        if possible is None:
            possible = [[start] for start in starts]
        new_possible = []
        for start, path in zip(starts, possible):
            for child in rule(start):
                if child not in visited:
                    if isgoal(child):
                        return path + [child]
                    else:
                        new_starts.append(child)
                        new_possible.append(path + [child])
        return _bfsi(new_starts, isgoal, new_possible, visited)
    return _bfsi([start], isgoal, possible, visited)

graph = {'A':{'B','C'},'B':{'D','E'}, 'C':{'E', 'F', 'H'}, 'D':{'I', 'J'}, 'E':{'G', 'K'}, 'F':{'L','M', 'H'}, 'H':{'N', 'M'}}

rule = lambda x: graph.get(x, {})
isgoal = lambda x: x == 'N'
p = bfsi('A', isgoal)
print(p)

最后编辑于：2021.02.07 13:43:53