5

这是我遇到的一个有趣的问题：

假设在长度为 的数轴上M，0 < M <= 1,000,000,000您给出了N( 1 < N <= 100,000) 个整数对点。在每一对中，第一个点表示对象当前所在的位置，第二个点表示对象应移动的位置。（请记住，该点second可能小于first）。

现在，假设您从该点开始0并且有一个可以容纳1物体的手推车。您希望将所有对象从它们的初始位置移动到它们各自的最终位置，同时沿着数轴移动最短距离（而不是位移）。你必须结束在点M。

现在，我一直在尝试将这个问题简化为一个更简单的问题。老实说，我什至想不出一个蛮力（可能是贪婪的）解决方案。然而，我的第一个想法是将向后运动退化为两个向前运动，但这似乎并不适用于所有情况。

我3在在此处输入图像描述

第一个测试用例的答案是12。red首先，您在 点拿起物品0。然后移动到点6（距离 = 6），暂时放下red物品，然后拿起green物品。然后您移动到点5(distance = 1) 并放下该green项目。然后你回到点6(distance = 1) 并捡起red你放下的物品，移动到点 9 (distance = 3)，然后移动到点10(distance = 1) 完成序列。

行驶的总距离为6 + 1 + 1 + 3 + 1 = 12，这是可能的最小距离。

12我相信其他两个案例的答案是。但是，我找不到解决它的一般规则。

有人有什么想法吗？

4

3 回答 3

0

这就是不对称旅行商问题。你可以把它想象成一个图表。边将是每个（开始，完成）对，每个（0，开始）和所有其他（完成，开始）对。

假设 NP!=P，它将有一个指数的预期运行时间。

于 2013-02-09T21:36:29.187 回答
0

假设你有这些动作(a, b), (c, d), (e, f), ...，那么你必须走的最小距离是abs(b - a) + abs(d - c) + abs(f - e) + ...，而你实际走的距离是abs(b - a) + abs(c - b) + abs(d - c) + abs(e - d) + ...。
基本上，给定一系列移动，关键是通过交换元素来最小化“旅行距离”功能。如果您将特定组合视为一个节点，并且您可以从它获得的所有组合作为边，您可以使用许多使用启发式的图形搜索算法之一。一个例子是束搜索。

于 2013-02-09T21:05:16.867 回答
0

可能是我误解了这个问题，但以下情况如何：

  1. 按当前位置的对的第一个数字对对进行排序
  2. 沿线将元素交换到正确的位置（您有一个临时变量）

它已排序的事实保证您不会来回移动元素以将它们放置在正确的位置（无论该行是否表示为数组或列表）

@templatetypedef 注释后更新：
使用 aHashTable存储所有对。使用每对的当前位置作为索引键。
在对上使用第二个索引。 

 1. Get next pair according to index from the line.
 2. If current pair exists in hashtable then place element to its target location.  
    2.a Remove pair from hashtable.  
    2.b Make current pair the target location. Then go to step 1  
 ELSE 
        Increment current index until you get a pair present in the hashtable. Go to step 2
于 2013-02-09T20:55:05.330 回答