Python中具有键值引用的字典

Question

在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.

的上下文：，我正在尝试为一个AI创建60^5游戏状态，我打算为一个游戏实现它。我需要分析所有的游戏状态在深度的5，以确定哪个是最好的。然后，为了达到深度5的状态，我需要知道在深度1，2，3和4下采取什么步骤来达到这个游戏状态。我不知道字典是否是实现这一目标的最佳方法，所以如果可能的话，我很想听听其他一些建议。

Answer 1

两种解决方案

第一次回归

第二深度优先搜索

第一个解决方案-使用递归

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

Answer 2

你可以用networkx来做

from collections import Mapping
import networkx as nx

graph_data = {1 : 
       {2 : 
        {3 : 4}},
       5 : 
       {6 :
        {7 : 8}}
      }
# Empty directed graph
G = nx.DiGraph()

# Iterate through the layers
q = list(graph_data.items())
while q:
    v, d = q.pop()
    for nv, nd in d.items():
        G.add_edge(v, nv)
        if isinstance(nd, Mapping):
            q.append((nv, nd))
        else:
            if not isinstance(nd, dict):
                G.add_edge(nv, nd)

作为最后一步，我们可以使用nx.shortest_path函数。

all_paths = nx.shortest_path(G, target=8)
max_len_key =  max(all_paths, key=lambda k: len(all_paths[k]))
print(all_paths[max_len_key])

产出如下：

[5, 6, 7, 8]

Answer 3

为了加快速度，我会考虑创建一个{key: parent_key} dict。在你的情况下

dic = {1:None, 2:1, 3:2, 4:3, 
       5:None, 6:5, 7:6, 8:7}

如果这些键是一些复杂的游戏状态，您可以将它们作为简单的ID，并将实际状态保存在单独的dict或偶数列表中。或者你可以

class State:
    pass

StateNode = namedtuple('StateNode', ('state', 'parent_id'))
dic = {1: StateNode(State(), None), 2: StateNode(State(), 1), 3: StateNode(State(), 2)}

无论哪种方式，当您知道您的叶节点的id (我假设您知道)时，您可以简单地从dict中绘制节点，直到到达具有父None的节点为止。