你怎么找到栈动作，将排序*知*名单的最好的一套？ [英] How do you find the best set of stack movements that will sort a *known* list?

问题描述

其中，对排序未知列出的问题。但是，我们找到最佳的列出已知在堆栈机排序的问题？也就是说，假设你有以下的堆栈机：

Much is known about the problem of sorting unknown lists. But what about the problem of finding the optimal sorting for a known list in a stack machine? That is, suppose you have the following stack machine:

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

即，有余地3堆栈，其中1填充有号码。此外，假设你的堆栈机可以执行2运动：移动AB （宿 A 的顶级元素到 B ）和加入AB （把堆栈 A 顶部堆栈 B ）。在该情况下，最佳的排序是：

That is, there is room for 3 stacks, and 1 of them is filled with numbers. Moreover, suppose that your stack machine can execute 2 movements: move a b (places the top element of the a onto b), and join a b (puts stack a on top of stack b). On that case, the optimal sort is:

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

将执行以下顺序：

Which will execute the following sequence:

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

你如何给定一个初始堆栈配置，发现这样的最佳运动组的第一个堆栈上的列表进行排序？

How do you, given a initial stack configuration, find such optimal set of movements to sort the list on the first stack?

推荐答案

由于这个简单的问题propably没有任何简单的解决办法，我不会试图找到一个完整的解决方案，而是尝试用你提供一些意见，可以引导你正确的方向（或说服你放弃）。

Since this simple question propably does not have any simple solution, I will not attempt to find a complete solution, but instead try to provide with you some points that may lead you to the right direction (or convince you to give up).

我看到两种不同类型的方法，这一问题：

I see two different kind of approaches to this problem:

分析方法

一个理论家的方法是，试图找到这将计算出游戏中的任何给定位置的复杂功能。最佳地，这将是所需要完成比赛的步数。如果这样复杂的功能被发现，那么这将是很容易在每一个位置，以消除可能的下一步行动，计算后，他们的立场的复杂性，然后选择产生最不复杂的位置的移动。

A theoreticians method would be to try to find a function that would calculate the complexity of any given position of the game. Optimally this would be the number of steps that is required to finish the game. If such complexity function is found, then it would be easy in each position to check the possible next moves, calculate the complexities of the positions after them and then choose the movement that produces least complex position.

搜索这样的功能，应通过设置完成游​​戏的复杂性为0，那么应该为可能的操作定义对称的反向操作来启动。移动操作是对称的本身，所以它可被用作是。但加入操作必须以取代非加入，任何地方，任何削减堆在中移动它的结尾到一个空栈。后，可以由一个或MOVE-非加入操作可以接触将有1复杂性。然后，可以从这些位置可以接触到已经没有更低的复杂度的任何位置，将有2复杂重复此之后的任何位置几个步骤之一，应该再尝试搜索模式，让生成，可以计算出的任意位置的复杂功能。

Search for such a function should be started by setting the complexity of the completed game to 0. Then one should define symmetrical backward operations for the possible operations. The move-operation is symmetrical itself, so it can be used as is. But the join-operation must be replaced with unjoin, that cuts any stack anywhere in the middle and moves the ending of it into an empty stack. After that any position that can be reached by one move- or unjoin-operation will have the complexity of 1. Then any position that can be reached from those positions and does not already have lower complexity, will have complexity of 2. After repeating this for a few steps one should then try to search for patterns that would allow generating a function that could calculate the complexity of an arbitrary position.

此方法可能会提供一个非常优雅和有效的解决方案，或许可以很容易地被证明是最优的。但明显的缺点是，但不保证，这样的复杂性函数存在 - 至少在任何实际的形式

This method might provide a very elegant and effective solution that could perhaps be quite easily proven to be optimal. But the obvious downside is that there is no guarantee that such a complexity function exists - at least in any practical form.

状态机

这是我起初以为是更有前途的一种不同的方法可以来定义什么打算玩家在某些特性位置应采取的一套规则。在这种情况下的位置将根据它们的特性和用于在给定的类的特定计划将被确定的位置进行分类。然后位置类将基本上处于一个状态机的状态并计划转移的状态之间。

A different approach that I at first thought to be more promising could be to define a set of rules on what plan the player should adopt in positions of certain characteristics. In this case the positions would be classified based on their characteristics and for a position in a given class a specific plan would be defined. Then the position classes would essentially be states in a state machine and the plans shifts between the states.

的状态的和的一个例子的俯视为这将是一个起始位置，其中，数字1（最低值）是在纸叠的中间的某个地方。在这种情况下，一个可行的计划可能会继续前进1的所有号码，以一个空栈和1时则透露，将其移动到其他空栈是起点，最后的排序堆。

An example of a state and a plan for it would be a starting position, where number 1 (the lowest value) is somewhere in the middle of the stack. In this case a feasible plan could be to move all the numbers on 1 to to one of the empty stacks and when 1 is revealed, move it to the other empty stack to be the starting point for the final sorted stack.

这样的状态及其相关计划的名单将是一个相当extesive，但也许是可行的。然而，更大的问题是，证明在美国的计划是最佳的。比如我给的起始位置的计划肯定是合乎逻辑的，但也不能保证它是最佳的。

The list of such states and their related plans would be a rather extesive, but perhaps doable. However, a bigger problem would be to prove that the plans in the states are optimal. For example the plan I gave for the starting position is surely logical, but there is no guarantee it is optimal.

这让怀疑这个方法的想法是以下理念：尤其是在游戏与长起始筹码，很可能是因为最佳的排序策略是与特定的划分长期堆在其他两个栈师，然后再次加入两三堆到一个长栈，又分为重复，直到堆栈进行排序。在这种情况下，这将是非常困难的predict如何划分到两个栈应，因为明显的计划可能无法正常工作。例如这将是毫无意义的划分数为成堆的更小和更大的数字，因为这部分的排序将在下一回合就完蛋了。一个更好的计划可能是创造尽可能多的对连续的数字作为可能的，但没有说这是最佳的两种。

The thought that made be sceptical about this approach was the following idea: Especially in games with a long starting stack, it may well be that the optimal sorting strategy is to divide the long stack in to the two other stacks with a specific division, then join the two or three stacks again to one long stack, divide again and repeat until the stack is sorted. In this case it would be very difficult to predict how the division to the two stacks should be made, since obvious plans may not work. For example it would be pointless to divide the numbers to stacks of smaller and larger numbers, since this partial sorting would be ruined on the next round. A better plan could be to create as many pairs of consecutive numbers as possible, but there's no saying this is optimal either.

在最后，我认为这是非常可能的，这个问题比蛮力解决方案没有其他的，如果被搜索的最佳结果。可以肯定有寻找至少有良好的效果与一般的分类学方法，但绝对最佳的是超越他们。

In conclusion I think it is very possible that this problem has no other than brute force solutions, if the optimal result is searched. For sure there are methods for finding good results at least from general sorting science, but the absolute optimal is beyond them.

这篇关于你怎么找到栈动作，将排序*知*名单的最好的一套？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！