<p>您正在寻找一个简单的定向图中的最长路径,如下所示:</p>
<pre><code>"Hello" ->\ /->"Beep bop Im a bot"->\
X X >"Okay, what time is it?"
"Good morning"->/ \->"Hello, dear human"->/
</code></pre>
<p>因此,您正在以下位置中寻找替代路径:</p>
<pre><code>given = [ [0, "Hello"], [0, "Good morning"], [1, "Beep bop Im a bot"], [1, "Hello, dear human"], [0, "Okay, what time is it?" ] ]
</code></pre>
<p>这里的递归答案很自然:</p>
<ul>
<li>如果<code>given</code>为空,则只有一个空路径</李>
<li>如果<code>given</code>不是空的,则让<code>head, tail</code>作为<code>given</code>的第一个元素,并分别作为<code>given</code>的其余元素。你有三种可能:
<ol>
<li>如果<code>tail</code>为空,则唯一路径为<code>[head.sentence]</code></李>
<li>否则,如果<code>head.speaker != first element tail.speaker</code>,则为<code>tail</code>中的每个路径生成<code>[head.sentence] + path</code></李>
<li>否则,如果<code>head.speaker == first element tail.speaker</code>,则:
A.在<code>tail</code>中产生路径(递归调用)
B删除<code>tail</code>的第一个元素并循环到3。直到你在案例1中。或2</李>
</ol>
</li>
</ul>
<p>它为什么有效?(演示示意图):</p>
<p>(I)你有:<code>given[0].speaker == path.speaker</code>对于<code>paths(given)</code>中的每一个<code>path</code>。如果<code>given</code>只有一个元素,则为真。否则,您将生成路径<code>head.sentence + <something> == given[0].sentence + <something></code>,或者在<code>paths(tail)</code>中生成一个<code>path</code>,其中<code>tail[0].speaker == head.speaker == given[0].speaker</code></p>
<ul>
<li>旋转:在案例1中,您只直接生成一个元素。或者2,当<code>head.sentence</code>后面跟着<code>paths(tail)</code>并且尾部第一个元素的说话人不同于<code>head</code>的说话人时。假设命题(I),你可以肯定一个人的句子后面总是跟着一个计算机句子,反之亦然</李>
<li>完整性:这对于空路径是正确的,因为您尝试了所有可能的开始,因为您在每个元素上调用<code>paths</code>,直到出现旋转为止</李>
</ul>
<p>在python中:</p>
<pre><code>given = [ [0, "Hello"], [0, "Good morning"], [1, "Beep bop Im a bot"], [1, "Hello, dear human"], [0, "Okay, what time is it?" ] ]
def paths(L):
if L:
head, *tail = L
while tail and tail[0][0] == head[0]:
yield from paths(tail)
_, *tail = tail
for path in paths(tail):
yield [head[1]] + path
else:
yield []
print(list(paths(given)))
</code></pre>
<p>输出:</p>
<pre><code>[['Good morning', 'Hello, dear human', 'Okay, what time is it?'], ['Good morning', 'Beep bop Im a bot', 'Okay, what time is it?'], ['Hello', 'Hello, dear human', 'Okay, what time is it?'], ['Hello', 'Beep bop Im a bot', 'Okay, what time is it?']]
</code></pre>