python - python中的递归搜索

Question

我正在尝试在这种情况下实现搜索算法: 假设有5个人:#0-4的人，人们只知道谁是他们的直属下属。例如，人员 0 和 1 不管理任何人，​​人员 2 管理人员 0，人员 3 管理人员 1，而人员 4 管理人员 2 和 3。

假设我将此层次结构存储在名为 hierarchyhierarchy = [[],[],[0],[1],[2,3]] 的列表中

我要找的是直接和间接在任意一个人手下工作的人，在这种情况下，直接和间接在4下工作的人应该是0,1,2,3，或者[0,1 ,2,3] = allUnder(hierarchy,ID = 4).

我认为问题的解决方案是某种递归搜索，但我对递归很模糊。我正在寻找的算法在重复值的情况下也应该是有效的(例如假设 3 管理两个 0,1，答案应该仍然是 0,1,2,3)。

我知道我应该把我的解决方案放在第一位，但我现在真的不知道如何解决它...任何帮助将不胜感激。

更新:我也对查找特定人员的所有直接和间接管理非常感兴趣。

Answer 1

解决方案

鉴于您需要双向搜索(即能够搜索下属和经理)，您将需要某种树结构来编码其节点之间的双向链接。这是一个实现这种树的类:

class Node:
    def __init__(self, val):
        """initialize a node with the worker id value
        """
        self._children = []
        self._parent = None
        self.val = val

    def link(self, *node):
        """create a parent-child link between this (parent) node and one
        or more (children) nodes
        """
        for n in node:
            n._parent = self
            self._children.append(n)

    def get(self):
        """depth-first recursive get
        """
        return [x for y in ([n.val] + n.get() for n in self._children) for x in y]

    def getparents(self):
        """walks up parents (currently there's at most one parent per-node)
        """
        return [] if self._parent is None else [self._parent.val] + self._parent.getparents()

class Tree:
    def __init__(self, idlists):
        """initialize the tree as per the OP's example input
        """
        self._nodes = {}
        for topid,idlist in enumerate(idlists):
            self.add(topid, idlist)

    def __getitem__(self, key):
        return self._nodes[key]

    def _getnode(self, i):
        """get or create the node with id=i.
        Avoid constructing new Nodes if we don't have to 
        """
        if i in self._nodes:
            return self._nodes[i]
        else:
            n = self._nodes[i] = Node(i)
            return n

    def add(self, topid, idlist):
        """create a node with id=topid (if needed), then add
        child nodes, one per entry in idlist
        """
        self._getnode(topid).link(*(self._getnode(i) for i in idlist))

测试一下

下面是如何使用上面定义的 Tree 类来解决您指定的问题:

data = [[],[],[0],[1],[2,3]]
people = Tree(data)

## get subordinates

print(people[4].get())
# output: [2, 0, 3, 1]
print(people[2].get())
# output: [0]
print(people[1].get())
# output: []

## get managers

print(people[1].getparents())
# output: [3, 4]
print(people[2].getparents())
# output: [4]
print(people[4].getparents())
# output: []

漫步

这是一个经典的 CS 栗子，在现代编码教程中似乎没有太多曝光(我认为是因为以前用树解决的许多问题现在有了更简单的基于哈希表/字典的答案)。