python中是否有任何方法可以获取嵌套字典中值所属的键?
一个例子是:
dic = {1 :
{2 :
{3 : 4}},
5 :
{6 :
{7 : 8}}
}
然后我想知道要到达4
或所需的路径8
。
这看起来像:
find_path(dic, 8)
应该返回类似
5, 6, 7 # since dic[5][6][7] leads to 8.
对于上下文:我正在尝试为60^5
打算为游戏实现的AI创建游戏状态。我需要深入分析所有游戏状态,5
以确定哪个最好。然后,为了到达深度5的状态,我需要知道在深度1、2、3和4采取什么步骤才能达到该游戏状态。我不知道词典是否最适合实现这一目标,因此,如果可能的话,我想听听其他建议。
两种解决方案
第一-递归
第二-深度优先搜索
第一个解决方案-使用递归
def find_path(d, value, path = [], sol = []):
for k, v in d.items():
if isinstance(v, dict):
path.append(k)
find_path(v, value, path, sol)
path.pop()
elif v == value:
path.append(k)
sol.append(path[:])
path.pop()
return sol
dic = {1 : {2 :
{3 : 4}
},
5 : {6 :
{7 : 8}}}
for v in range(10):
found = find_path(dic, v, [], [])
if found:
print("{} -> {}".format(v, found[0)) # showing first solution
# found will show them all
else:
print("No path to {}".format(v))
输出量
No path to 0
No path to 1
No path to 2
No path to 3
4 -> [1, 2, 3]
No path to 5
No path to 6
No path to 7
8 -> [5, 6, 7]
No path to 9
第二种解决方案-使用深度优先搜索
from collections import deque
def find_using_dfs(d, value):
" Finds using depth first searh through dictionary "
# Use queue for Depth First Search (LIFO)
stack = deque()
for k, v in d.items():
stack.append((v, [k]))
while stack:
v, path = stack.pop()
if isinstance(v, dict):
for k, viter in v.items():
path.append(k)
stack.append((viter, path[:]))
path.pop()
elif v == value:
return path
return None
dic = {1 : {2 :
{3 : 4}
},
5 : {6 :
{7 : 8}}}
for v in range(0, 10):
found = find_path_proc(dic, v)
if found:
print("{} -> {}".format(v, found))
else:
print("No path to {}".format(v))
输出量
No path to 0
No path to 1
No path to 2
No path to 3
4 -> [1, 2, 3]
No path to 5
No path to 6
No path to 7
8 -> [5, 6, 7]
No path to 9
本文收集自互联网,转载请注明来源。
如有侵权,请联系[email protected] 删除。
我来说两句