algorithm - 从最大化适应度函数的矩阵中选择列表

Question

我正在开发一个音乐应用程序，但我遇到了算法问题。这是问题的玩具版本。假设我们有n要按特定顺序访问的城市。我们得到的是每个“步骤”的可能城市列表：

{{"London","Glasgow"},{"Munich","London"},{"Glasgow","Munich","London"}}

我们必须通过从每个子列表中选择一个城市来将其简化为一个城市列表。我们还给出了每个城市之间的距离列表：

{{"London"->"Glasgow,100},{"London"->"Munich",400},{"Munich"->"London",300},...}

请注意，此列表不是对称的 - 伦敦到慕尼黑可能不同于慕尼黑到伦敦（德国飞机的一些效率）。还假设任何城市到自身的距离为 0。我们希望选择总距离最小的列表。

该列表不必打击每个城市，它可以多次打击同一个城市。对于上面的示例，最有效的解决方案是 {London, London, London}.

到目前为止，我一直在使用贪心算法，但这并不总是能给出最好的结果。我考虑过的唯一其他选择（除了蛮力）是遗传算法，但这也不能保证给出最佳解决方案。

完成此任务的最有效算法是什么？

标签： algorithm

Answer 1

让我们以这种方式简化问题。

将多次发生的城市拆分为不同的城市，并构建层次图。添加两个伪城市作为起点和终点，则成为最短路径问题。

此处了解有关最短路径问题的更多信息。