首页 文章

algorythm在多分支树中找到“下一个邻居匹配”

提问于
浏览
0

我有一个数据结构,基本上是一个具有多个分支的树 . 该程序在python中实现(3.5,目前,如果重要的话) .

问题:从任意节点开始,找到距离最短的“匹配”节点 .

“距离”的定义具有尽可能少的“回溯”(当从起始节点返回到父节点时发生回溯) .

这意味着起始节点的子节点是首选,然后是起始节点的父节点的子节点,第三种选择是起始节点的父节点的父节点的子节点等 .

天真的实现导致无限递归:

def find(self, name, skip=None):
        if self.name == name:
            return self
        for c in self.child:
            if c != skip:
                s = c.find(name, skip)
                if s is not None:
                    return s
        if name != 'Start':
            if self.parnt is not None:
                return self.parnt.find(name, self)
        return None

我还没有找到一个不需要分支标记的算法,这很麻烦 .

当前实现还存在实现深度优先搜索的问题,而广度优先搜索将是优选的 .

有人可以提出有效的算法吗?

1 回答

  • 0

    我用以下代码找到了一种方法:

    def find(self, name, tovisit=None, visited=None):
        if tovisit is None:
            tovisit = []
        if visited is None:
            visited = []
        tovisit.append(self)
        while tovisit:
            s = tovisit.pop()
            visited.append(s)
            if s.name == name:
                return s
            for c in s.child:
                if c not in visited:
                    tovisit.append(c)
            if name != 'Start':
                if s.parnt is not None and s.parnt not in visited:
                    tovisit.append(s.parnt)
        return None
    

    此迭代解决方案依赖于两个列表来处理广度优先并避免重新访问节点 .

    我暂时不接受我自己的答案,希望可以提出更好的解决方案 .

相关问题