如何在图中定义的N个允许动作中计算路径权重之和,但目标节点未使用Python固定

gr = {'0': {'4': 4, '6': 6},
      '4': {'3': 7, '9': 13, '0':4},
      '6': {'1': 7, '7':13,'0':6},
      '3': {'4': 7, '8': 11},
      '9': {'4': 13, '2': 11},
      '1': {'6': 7, '8': 9},
      '7': {'2': 9, '6': 13},
      '8': {'1': 9, '3': 11},
      '2': {'9': 11, '7': 9}}

这是一张图,我为允许的移动做出了定义,并定义了移动中的权重,因为我需要计算从“ 0”开始一定数量的移动(n)之后路径的权重之和.路径可以是随机的,但在未定义目标的情况下,可以从图中定义的路径中选择.

我已经尝试过这样的函数,其中给定的参数是起点和终点.这可以找到路径并计算行进的重量.但是我需要能够将参数作为起点和移动次数,而不是目的地,并找到路径权重的总和.此外,可以多次访问节点.请帮助我编辑此功能,否则可能我的方法有所不同.

def paths(gr, frm, to, path_len = 0, visited = None):
   if frm == to:
        return [[to, path_len]]

   visited = visited or []
   result = []
   for point, length in gr[frm].items():
       if point in visited:
           continue
       visited.append(point)
       for sub_path in paths(gr, point, to, path_len + length, visited[:]):
           result.append([frm] + sub_path)

   return result

print (paths(gr, '0', '9'))

我期望的输出是:

Path: 0->4->3->8>1->6->7->2->9->4, Sum: 44

Path: 0->6->7->2->9->4->3->8->1->6, Sum: 46

comments开始:

问题陈述是“它在允许的移动中均匀地随机选择,并跟踪其所落节点的运行总和S”.所以我的问题是找到它在K中移动的所有节点的和S.

最佳答案

这是我使用一些Python代码和Graphviz创建的图的图.

在您发布的代码中,您有一个访问列表.该列表的目的是防止一个节点被多次访问.但是,您没有将初始frm节点添加到访问列表中,因此该节点可以被访问两次.这是修复的版本:

gr = {
    '0': {'4': 4, '6': 6},
    '4': {'3': 7, '9': 13, '0': 4},
    '6': {'1': 7, '7':13, '0': 6},
    '3': {'4': 7, '8': 11},
    '9': {'4': 13, '2': 11},
    '1': {'6': 7, '8': 9},
    '7': {'2': 9, '6': 13},
    '8': {'1': 9, '3': 11},
    '2': {'9': 11, '7': 9},
}

def paths(gr, frm, to, path_len=0, visited=None):
    if frm == to:
        return [[to, path_len]]

    visited = visited or [frm]
    result = []
    for point, length in gr[frm].items():
        if point in visited:
            continue
        for sub_path in paths(gr, point, to, path_len + length, visited + [point]):
            result.append([frm] + sub_path)

    return result

# Test
frm, to = '2', '8'
for p in paths(gr, frm, to):
    print(p)

输出

['2', '9', '4', '0', '6', '1', '8', 50]
['2', '9', '4', '3', '8', 42]
['2', '7', '6', '0', '4', '3', '8', 50]
['2', '7', '6', '1', '8', 38]

正如评论中提到的Antti一样,最好使用生成器来生成此路径,该生成器会在找到路径时生成路径,而不是将所有结果保存在一个大列表中,然后将其返回.通过使用集合而不是列表,我们可以使“访问”的测试更加有效:

def paths(gr, frm, to, path_len=0, visited=None):
    if frm == to:
        yield [to, path_len]
        return

    visited = visited or {frm}
    for point, length in gr[frm].items():
        if point in visited:
            continue
        for sub_path in paths(gr, point, to, path_len + length, visited | {point}):
            yield [frm] + sub_path

我们可以使用类似的方法从给定的起始节点生成固定长度的所有路径.

gr = {
    '0': {'4': 4, '6': 6},
    '4': {'3': 7, '9': 13, '0': 4},
    '6': {'1': 7, '7':13, '0': 6},
    '3': {'4': 7, '8': 11},
    '9': {'4': 13, '2': 11},
    '1': {'6': 7, '8': 9},
    '7': {'2': 9, '6': 13},
    '8': {'1': 9, '3': 11},
    '2': {'9': 11, '7': 9},
}

def paths_by_length(gr, frm, steps, path_len=0, path=None):
    if steps == 0:
        yield path, path_len
        return

    path = path or [frm]
    steps -= 1
    for point, weight in gr[frm].items():
        new_path = path + [point]
        new_len = path_len + weight
        for sub_path, sub_length in paths_by_length(gr, point, steps, new_len, new_path):
            yield sub_path, sub_length

frm = '0'
steps = 3
for path, path_len in paths_by_length(gr, frm, steps):
    print(path, path_len)

输出

['0', '4', '9', '2'] 28
['0', '4', '9', '4'] 30
['0', '4', '0', '4'] 12
['0', '4', '0', '6'] 14
['0', '4', '3', '4'] 18
['0', '4', '3', '8'] 22
['0', '6', '7', '2'] 28
['0', '6', '7', '6'] 32
['0', '6', '1', '8'] 22
['0', '6', '1', '6'] 20
['0', '6', '0', '4'] 16
['0', '6', '0', '6'] 18

因为您的图具有如此简单的结构,并且边缘权重符合weight = frm,所以可能存在更有效的方法.另外,您可以通过多种方式简化gr,例如,您可以使用整数而不是字符串作为节点名称,这将使gr成为列表或元组而不是字典,并且每个节点的字典都没有(node,权重)对,每个节点可能只是其连接到的节点的列表或元组,因为计算边缘权重非常容易.

更新资料

您的实际问题比您最初要求的要简单得多.

我们不需要为此使用递归,只需使用一个简单的for循环即可,该循环调用random module中的choice函数来随机选择一致的移动.

from random import choice, seed

gr = (
    (4, 6), # 0
    (6, 8), # 1
    (7, 9), # 2
    (4, 8), # 3
    (0, 3, 9), # 4
    (), # 5
    (0, 1, 7), # 6
    (2, 6), # 7
    (1, 3), # 8
    (2, 4), # 9
)

# Seed the randomizer
seed(42)

def random_path(gr, node, steps):
    path = [node]
    for i in range(steps):
        node = choice(gr[node])
        path.append(node)
    return path

# Test

frm = 0
steps = 3
for i in range(10):
    path = random_path(gr, frm, steps)
    print(path, sum(path))
print()

# Find the mean score of a number of paths
steps = 1024
num = 10000
total = 0
for i in range(num):
    path = random_path(gr, frm, steps)
    total += sum(path)
print('Steps: {}, Trials: {}, Mean: {}'.format(steps, num, total / num))

输出

[0, 4, 0, 6] 10
[0, 4, 0, 4] 8
[0, 4, 9, 2] 15
[0, 6, 0, 4] 10
[0, 4, 0, 4] 8
[0, 4, 9, 2] 15
[0, 6, 0, 6] 12
[0, 6, 0, 4] 10
[0, 6, 1, 8] 15
[0, 4, 0, 6] 10

Steps: 1024, Trials: 10000, Mean: 4607.2152

如果您不需要实际路径,只需节点求和,则可以进一步简化此功能,但这将留给读者练习.