函数以使用python查找图形中的最高分路径

Question

我想做一个函数，在有向图中找到最高的分数。我有一个开始节点，不能通过同一个节点两次。我尝试使用递归来获得值的总和，直到我到达一个端点节点。然后我会将我的函数回调到开始节点，并尝试其他选项，直到我点击另一个。等等。你知道吗

我的问题是，当我返回到一个具有多条路径的节点时，该节点的得分值是它可以采用的所有路径的总和。我只想要一条特定路径的和。你知道吗

以下是我目前的代码：

caminho = list()
def maxscore(start, parentals, score):
    global caminho
    parentals += start + '|'

    if len(graph[start]) > 0:
        for i in graph[start]:
            if i not in parentals.split('|'):
                value = graph[start][i]
                if value:
                    score += value

                func = maxscore(i, parentals, score)

            else:
                continue

        if func[0] > score:
            score = func[0]
            caminho = parentals.split('|')

        return score, caminho

    else:
        return score, start

graph = {
    'a': {'b': 2, 'c': 4},
    'b': {'d': 5},
    'c': {'a': 1, 'e': 3},
    'd': {'f': 4},
    'e': {'b': 2, 'f': 3, 'g': 2},
    'f': {},
    'g': {}
}

print(maxscore('a', '', 0))

我怎么能让它工作到最后只有最好的分数与路径（卡米尼奥）它采取。你知道吗

对不起，如果我说不清楚的话。有问题尽管问。你知道吗

Answer 1

以下是一种方法：

def maxscore(start, path, score):
    best_score = -1
    best_i = None
    best_path = None

    current_path = path + [start]
    for i in graph[start]:
        if not i in path:
            score_i, path_i = maxscore(i, current_path, score + graph[start][i])
            if score_i > best_score:
                best_score = score_i
                best_i = i
                best_path = path_i
    if best_i is None:
        return score, current_path
    else:
        return best_score, best_path

graph = {
    'a': {'b': 2, 'c': 4},
    'b': {'d': 5},
    'c': {'a': 1, 'e': 3},
    'd': {'f': 4},
    'e': {'b': 2, 'f': 3, 'g': 2},
    'f': {},
    'g': {}
}

print(maxscore('a', [], 0))

输出：

(18, ['a', 'c', 'e', 'b', 'd', 'f'])

注意事项：

• 在问题代码中，卡米尼奥和他的父母起着同样的作用。仅仅拥有一个列表比使用一个字符串更容易。你知道吗
• 在for循环中，我们测试每个边。如果边的结束节点还不在路径中，我们计算该边后面的最大分数。我们必须比较每一个可能的边缘，并保持一个最好的分数。我们只能在测试完所有可能的边之后从maxscore()返回。你知道吗
• 如果没有找到自由边，我们只返回当前的分数和路径
• 如果找到自由边，则返回最佳边的分数和路径

注：修改代码后，可以缩短一点。best_i不是真正需要的，测试if best_i is None可以被if best_path is None代替。你知道吗

另外，如果需要字符串形式的路径，可以打印（“|”.join（best|path））。你知道吗

Answer 2

您可能希望按值发送score变量，但您是按引用发送的，因此所有可能路径的分数都会添加到该变量中。你知道吗

这是我的方法：

def maxscore(start, parentals, score):
    newParentals = parentals + start + '|'
    print newParentals, score
    scores = []
    if graph[start]:
        for nextNode in graph[start]:
            if nextNode not in newParentals.split('|'):
                scores.append(maxscore(nextNode, newParentals, score + graph[start][nextNode]))
        return sorted(scores)[-1]
    else:
        return score

graph = {
    'a': {'b': 2, 'c': 4},
    'b': {'d': 5},
    'c': {'a': 1, 'e': 3},
    'd': {'f': 4},
    'e': {'b': 2, 'f': 3, 'g': 2},
    'f': {},
    'g': {}
}

print(maxscore('a', '', 0))

这就是印刷的内容：

a| 0
a|c| 4
a|c|e| 7
a|c|e|b| 9
a|c|e|b|d| 14
a|c|e|b|d|f| 18
a|c|e|g| 9
a|c|e|f| 10
a|b| 2
a|b|d| 7
a|b|d|f| 11
18

您可以看到它如何检查所有可能的路径，然后选择最高分：D