algorithm - 您如何找到最佳的堆栈移动集，以对*已知*列表进行排序？

Question

关于未知列表的排序问题，人们已经知道很多了。但是，在堆栈机器中找到已知列表的最佳排序问题呢？也就是说，假设您有以下堆栈计算机：

[4,1,3,2]
[]
[]

也就是说，有3个堆栈的空间，其中1个堆栈充满了数字。此外，假设堆栈计算机可以执行两个移动： move a b（将 a的顶部元素放置到 b）和 join a b（将stack a放置到堆栈的顶部）。在这种情况下，最佳排序是：

move 0 1
move 0 1
move 0 2
join 1 2
move 0 2

它将执行以下顺序：

[4,1,3,2] → [4,1,3] → [4,1] → [4]   → [4]     → []
[]        → [2]     → [2,3] → [2,3] → []      → []
[]        → []      → []    → [1]   → [1,2,3] → [1,2,3,4]

在给定初始堆栈配置的情况下，如何找到这样的最佳移动集来对第一个堆栈上的列表进行排序？

Answer 1

由于这个简单的问题显然没有任何简单的解决办法，我不会试图找到一个完整的解决办法，而是试图向你提供一些可能会引导你走向正确方向（或说服你放弃）的观点。
我看到了解决这个问题的两种不同方法：
分析方法
一个理论家的方法是试图找到一个函数来计算游戏中任何给定位置的复杂度。最理想的情况是，这将是完成游戏所需的步骤数。如果发现这样的复杂性函数，那么在每个位置很容易检查可能的下一个动作，计算它们之后的位置的复杂度，然后选择产生最不复杂位置的运动。
应该通过将完成游戏的复杂度设置为0来开始搜索这样的函数。然后应该为可能的操作定义对称的向后操作。移动操作本身是对称的，因此可以按原样使用。但是join操作必须替换为unjoin，这将剪切中间任意位置的任何堆栈，并将其结尾移动到空堆栈中。之后，通过一个移动或不连接操作可以达到的任何位置都将具有1的复杂度。然后，从这些位置可以达到的任何位置并没有较低的复杂度，将具有2的复杂度。在重复这几个步骤之后，人们应该尝试寻找允许生成能够计算任意位置的复杂性的函数的模式。
这种方法可能提供一个非常优雅和有效的解决方案，可能很容易被证明是最优的。但明显的缺点是，不能保证这样的复杂性函数至少存在于任何实际的形式中。
状态机
一开始我认为更有希望的另一种方法是定义一套规则，规定球员在某些特征的位置上应该采用什么样的计划。在这种情况下，职位将根据其特点进行分类，对于给定类别中的职位，将定义一个特定的计划。然后，position类本质上是状态机中的状态，并且计划在这些状态之间移动。
状态和计划的一个例子是起始位置，其中数字1（最低值）位于堆栈的中间。在这种情况下，一个可行的计划是将1上的所有数字移到一个空堆栈上，当1被显示时，将其移到另一个空堆栈上，作为最终排序堆栈的起点。
这类国家及其相关计划的清单将是一份相当详尽的清单，但也许是可行的。然而，一个更大的问题是证明各州的计划是最优的。例如，我给出的起跑位置的计划当然是合乎逻辑的，但不能保证它是最佳的。
对这种方法持怀疑态度的想法是：特别是在具有长起始堆栈的游戏中，最好的排序策略可能是将长堆栈分成具有特定划分的两个其他堆栈，然后将两个或三个堆栈再次合并为一个长堆栈，再次划分并重复，直到堆栈已排序。在这种情况下，很难预测如何划分两个堆栈，因为明显的计划可能行不通。例如，将数字分成一堆越来越小的数字是没有意义的，因为这种部分排序将在下一轮中被破坏。一个更好的计划可能是创建尽可能多的连续数字对，但也不能说这是最佳的。
最后，我认为，如果搜索到最优结果，这个问题很有可能只有蛮力解。当然，至少在一般的排序科学中，有一些方法可以找到好的结果，但是绝对最优的方法是不可能的。