我正在开发一个音乐应用程序，我遇到了一个算法问题。这是问题的玩具版本。假设我们按照一定的顺序拥有我们想要访问的n城市。我们给出的是每个“步骤”的可能城市列表：
{{"London","Glasgow"},{"Munich","London"},{"Glasgow","Munich","London"}}
我们必须通过从每个子列表中选择一个城市，将其简化为城市列表。我们还列出了每个城市之间的距离：
{{"London"->"Glasgow,100},{"London"->"Munich",400},{"Munich"->"London",300},...}
请注意，这个列表并不对称 - 伦敦到慕尼黑可能有所不同，从慕尼黑到伦敦（德国飞机的效率）。还假设从任何城市到自身的距离为0.我们想要选择总距离最小的列表。
该列表不必命中每个城市，它可以多次击中同一个城市。对于上面的例子，最有效的解决方案是{London, London, London}。
到目前为止，我一直在使用贪心算法，但这并不总是能给出最好的结果。我考虑过的唯一另一种选择（除了蛮力）是遗传算法，但这并不能保证给出最佳解决方案。
什么是最有效的算法来实现这一目标？