<p>以下是一种方法:</p>
<pre class="lang-py prettyprint-override"><code>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))
</code></pre>
<p>输出:</p>
<pre><code>(18, ['a', 'c', 'e', 'b', 'd', 'f'])
</code></pre>
<p>注意事项:</p>
<ul>
<li>在问题代码中,卡米尼奥和他的父母起着同样的作用。仅仅拥有一个列表比使用一个字符串更容易。你知道吗</li>
<li>在for循环中,我们测试每个边。如果边的结束节点还不在路径中,我们计算该边后面的最大分数。我们必须比较每一个可能的边缘,并保持一个最好的分数。我们只能在测试完所有可能的边之后从<code>maxscore()</code>返回。你知道吗</li>
<li>如果没有找到自由边,我们只返回当前的分数和路径</li>
<li>如果找到自由边,则返回最佳边的分数和路径</li>
</ul>
<p>注:修改代码后,可以缩短一点。<code>best_i</code>不是真正需要的,测试<code>if best_i is None</code>可以被<code>if best_path is None</code>代替。你知道吗</p>
<p>另外,如果需要字符串形式的路径,可以打印(“|”.join(best|path))。你知道吗</p>