2

这是一道作业题（对不起，我知道这些是不受欢迎的），但我和老师实际上都不知道如何有效地解决它，所以我想把它放在这里，看看SO上的精彩大脑是否可以帮助我们.

给出了一个未指定大小的数组，其中包含随机数。它必须按升序排列。每个元素可以移动到相邻的空白空间，也可以移动到相邻的较大元素的顶部。我需要编写一个方法来返回对给定数组进行排序所需的最小移动次数。

这个问题被标记为“可选”，因为老师意识到这个问题太难了，但我很好奇它是如何解决的。任何大小的数组的任何建议（它可以是长度为 3 的数组，我所关心的）表示赞赏。

编辑：感谢您指出这尚不清楚。我正在使用数组来表示假设的现实世界情况。让我们以硬币为例：它们都排成一排放在桌子上，只能放入指定数量的“空格”。但它们可以放在相邻的较大硬币的顶部，或者滑动到相邻的空白空间（该空间已被一枚可能移动到一堆顶部的硬币腾出）。

4

3 回答 3

1

我决定用一些假设/更改来检查这个问题，因为它让我觉得它成为一个更有趣的问题：

1）您可以从堆的任何部分向左或向右移动元素。

2）你可以将一个元素堆叠成一堆，无论它是更大、更小还是相同的大小。

3）只要您在较小的数字之前从未遇到过较大的数字，无论您如何通过堆栈，该数组都被视为已排序。所以 _ 11 2 3 已排序，但 _ _ 12 3 不是因为您可以将 2 解释为在 1 之前。

这导致了一个非常有趣的问题，尽管有这个公理：

公理A：你下棋的顺序无关紧要，可以以任何方式重新安排，以仍然达到相同的最终结果。

公理 Ab：如果数组中没有重复，则只需将每个元素移向其最终位置。

特别是，我制定了一个策略，希望您可以仅通过局部检查而无需递归/回溯来解决它，但我已经证明这是没有结果的，稍后会展示它。

我的策略是：

1) 从左到右继续寻找以错误方式翻转的对（在较低数字之前的较大数字）。

2a) 当你找到一个时，如果有一个空白点或堆栈，右手值可以立即填充，将它向左移动直到它填充它。

2b) 否则，将左值右移一位。这会造成您有一堆无关紧要的数字的情况 - 首先，在向下比较之前，根据 1) 的逻辑将您向右移动的值与其新右侧的值进行比较。

2bii) 以与对比较相同的方式处理向下比较 - 如果它可以适合空点或堆栈，则将较低的值向左移动，否则将较高的值向右移动并继续。

例子：

1231 -> 我们将 1b 向左移动，因为它可以放入堆栈。11 2 3 _

1321 -> 我们将 3 向右移动，因为 2 不适合空位/堆栈。我们将 1b 向左移动两次，因为它将适合一个空点/适合堆栈，然后我们将 3 向右移动，因为 2 将不适合一个空点/堆栈。1 1 2 3

1132 -> 我们将 3 向右移动，因为 2 不能向左移动。我们将 2 向左移动，因为它将适合一个空的位置。1 1 2 3

2311 -> 我们将 3 向右移动，因为 1a 不能向左移动。我们将 1b 向左移动两次，因为它将适合一个空白点。我们将 1a 向左移动，因为它会堆叠。我们向右移动 2，因为 1a1b 不能向左移动。我们将 1a2b 向左移动，因为它将填充一个空白点。11 2 3 _

但是，我们遇到了这两个起始数组的问题：

23411 10 步最佳，2r 3r 4r 1al*3 1bl*4 使 11 2 3 4 _。

23111 9 招最优，2r*3 3r*3 1bl 1cl*2 使_ _ 111​​ 2 3 - 与23411 策略相反！我们少移动 1，多移动 23，因为有更多的 1，所以我们尽可能少地移动它们。

这表明我们不能只做一个简单的局部比较来解决这个新问题。

我还在思考这个问题，它看起来很有趣，而且我希望你们中的一些人喜欢和我一起思考这个问题:)

于 2013-04-09T07:05:45.673 回答
0

我假设：

  • “排序”意味着剩下一个堆栈
  • 如果源堆栈中的最大数字小于目标堆栈中的最小数字，我们只能将堆栈移动到另一个堆栈（或者等效地：堆栈必须以较小的数字在顶部进行排序，并且将堆栈移动到另一个堆栈移动整个堆叠在另一个之上）

然后，如果数组多次包含一个数字，显然没有解决方案。此外，数字的大小并不重要，只有它们的等级才重要。不失一般性，我们因此可以假设数组包含任意顺序的数字 1..n。此外，要确定可能的移动，只有堆栈底部的顶部很重要。因此，存储以下内容就足够了：

int[] bottom;
int[] top;

由于我们无法将堆栈分开，因此我们只能将堆栈 i 移动到堆栈 j if bottom[i] + 1 == top[j]，否则我们将处于无法解决的状态。但是，如果我们处于可以进行此类移动的游戏状态，则最好立即执行它，因为最终我们将不得不合并这些堆栈，并且移动单个堆栈比移动两个堆栈便宜。

因此，唯一的自由度是如何以最少的移动次数将堆栈移动到适当的位置。目前，我没有看到明显的贪心算法，因此找到最佳解决方案可能需要将游戏的位置编码为图形，并将最短路径算法应用于该图形以找到最短的移动序列。

于 2013-04-09T02:10:51.670 回答
0

编辑：鉴于每个人似乎都在解决不同的问题，我将说明我正在解决的问题（我认为这是正确的问题（不是我们所有人吗？））：（使用磁盘希望让事情变得更容易了解）

给定 n 堆，每堆恰好包含 1 个磁盘，按大小递增的顺序排列这些磁盘。最终结果必须使每个堆包含 1 个磁盘。唯一允许的操作是将单个圆盘从一个堆的顶部移动到相邻堆的顶部，受限于不能将磁盘放置在较小磁盘的顶部。允许将磁盘移动到空堆或从堆中移动最后一个磁盘。总是有 n 个堆，因此： (1) 可能不会创建新堆，因此磁盘可能不会移动到原始序列的范围之外。(2) 空堆仍然存在，因此如果相邻位置是空的，则磁盘可能不会在未首先移动到该位置的情况下移动到该位置。

笔记：

一个直径为 x 的圆盘 = 一个数 x。

这可能不是最有效的解决方案，但它应该可以工作，并且可能会给某人一些可以工作的东西。

这是一个纯粹的迭代过程——在每一步之后，我们以所有大小为 1 的堆栈结束；这可能是这种方法的根本效率低下。

解决方案：

我将使用 1、2 和 5 来说明以下内容，但这只是表示尺寸排序，对于具有相同排序的任何其他数字，它都相同。

  • 重复直到排序：
    • 找到尚未在正确位置的最大元素（5在这种情况下）
      • （实际上它不必是最大的，只要是下面形式的任何东西，但注意不要将元素移动到它们应该在的位置之外）
    • 我们有2个案例：
      • 它在最左边的位置，我们有两种情况：
        • 512...-1向右移动5，向右移动，向左移动12，以152
        • 521...-1向左移动 2，向右移动，2向右移动12，向右移动5，向左移动12，以152
      • 它不在最左边的位置，我们有两种情况：
        • ...251...-1向左移动 2，5向右移动，向右移动1，以215
        • ...152...-2向左移动1，向右移动，1向右移动，2向左移动，以结束251（之后我们从上一个案例开始）

编辑2：

更有效的解决方案：

  1. 找到不在正确位置的最小磁盘
  2. 将其放在右侧的磁盘顶部
  3. 将所有磁盘移到该磁盘的左侧 1 位置右侧
  4. 将最小的磁盘一直向左移动（直到遇到一个已经在正确位置的较小磁盘）

可能的预处理步骤：排序到单独的列表以有效地找到最小元素

优化：如果要将磁盘向右移动超过其目标位置，则不要在上一步中将右侧的磁盘向右移动，而只需将这个磁盘放在那个磁盘上。如何在正确的时间有效地做到这一点可能有点复杂。不执行某些动作以提高效率也可能会有所帮助。

例子：

52413

// put smallest disk (1) on disk to the right
    1
524_3

// shift disks to the left 1 position right (3 moves - moved 4, then 2, then 5)
    1
_5243

// move 1 all the way left (4 moves)
15243

// same as above for 2

   2
15_43

   2
1_543

12543

当最小的磁盘在最右边时（就像现在的情况3），这有点问题。2种解决方法：

  • 交换1并2穿上1（右、左 2 个位置、2左2个位置）。然后你就有了一个可以移动的空地。如果小于 2 个较小的元素，则不是一种选择。在我们对更多元素进行排序之前，不应修复这些元素，以防我们遇到同样的情况。1213

  • 如果我们有12453，我们可以简单地4打开5一个插槽3（哪种延迟问题）。如果第一个未排序的磁盘（5在这种情况下）大于第二个（4），我们可以使用一些策略，就像我在前面的解决方案中描述的那样来移动元素以满足这个条件。

于 2013-04-09T12:59:40.013 回答