gpt4 book ai didi

python - python中的递归搜索

转载 作者:太空宇宙 更新时间:2023-11-03 13:57:01 24 4
gpt4 key购买 nike

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

The described hierarchy

假设我将此层次结构存储在名为 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)。

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

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

最佳答案

解决方案

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

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 栗子,在现代编码教程中似乎没有太多曝光(我认为是因为以前用树解决的许多问题现在有了更简单的基于哈希表/字典的答案)。

关于python - python中的递归搜索,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/54271255/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com