如何找到最短的堆栈移动序列以获得目标堆栈?

Question

我的任务是编写一些代码，以找到将给定的起始堆栈带到给定目标堆栈的最短移动序列。我得到了一个原始的书籍列表，描绘了书堆是如何开始的，还有一个目标书籍列表，显示了我需要它们的目标顺序。问题在于标准的排序算法不起作用，因为书籍的排序是基于一个人的偏好，而不是任何特定的逻辑。

问题希望您使用的系统如下：从书堆中的任何位置拉出一本书，一次一本书，然后将其放在书堆的顶部。因此，如果你有X，Y和Z的书，你可以选择拉出Y，使顺序Y，X，Z。

初：

'1984 - George Orwell'
'Moby Dick - Herman Melville'
'To Kill A Mockingbird - Harper Lee'
'Atlas Shrugged - Ayn Rand'
'The Black Cat - Edgar Allen Poe'

目标：

'Atlas Shrugged - Ayn Rand'
'To Kill A Mockingbird - Harper Lee'
'1984 - George Orwell'
'Moby Dick - Herman Melville'
'The Black Cat - Edgar Allen Poe' 

这是家庭作业。但是，我不是在寻找人为我做这件事的人，因为这会破坏任务的目的。我只是在寻找一些想法或技巧来开始，因为我不知道从哪里开始。

注意：我打算将其标记为家庭作业，但是标签明确表示不要，所以我没有。如果这是错误的，请纠正我。

Answer 1

好的，主要问题是你只能放在顶部，但你可以选择任何一本书。你想要提示，而不是方法，所以这里有一些：

1. 因为你只能放在上面，所以总是开始看底部，因为它最难到达
2. 显然，您永远不需要将任何书籍拉到正确的位置
3. 您需要以正确的顺序拉取现在位于书籍上方
的书籍下的所有书籍
4. 如果你把书堆在顶部，你应该把它们按正确的顺序放在那里
5. 要将 A B G F C E D 转换为字母顺序，如果您始终连接到末尾，则最好拉动 E，然后是 F，然后是 G。

我希望这能让你开始，我没有去过明确。

Answer 2

一个非常简单的算法是遍历堆栈，每次都找到并拉出属于底部的下一本书。线性搜索对于一个小堆栈就足够了。

在您的示例中，您将在第一次迭代中拉出'The Black Cat - Edgar Allen Poe'，在第二次迭代中拉出'Moby Dick - Herman Melville'，在第三次迭代中拉出'1984 - George Orwell'，依此类推。

这是一个 O(n^2) 算法。