logo标签列表

算法问题：将棒材排成一行

javascriptalgorithmsortingconstraints
3

好的，这可能是一个棘手的问题。实际上它是我的实际应用程序中另一个类似问题的比喻，但为了清晰起见，我已将其简化为这个假设性问题。以下是：

  1. 我有一排钓竿需要排序。因为是一排，所以只需要考虑一个维度。
  2. 钓竿长度和重量不同。重量和长度之间没有关联。一根小钓竿可能非常重，而一根大钓竿可能非常轻。
  3. 钓竿需要按重量排序。
  4. 真正的难点在于，有些钓竿只能放置在距离起始位置不超过某个距离的地方，无论它们的重量如何。但是，在此之前的任何位置都可以。
  5. 不能保证限制之间的间距足够远，以防止受限制的钓竿被挤入重叠。在这种（希望很少出现的）情况下，需要在限制范围内重新安排钓竿以创建所需的空间，或者需要找到一个理想的妥协解决方案（例如违反最轻的钓竿的限制）。
  6. 未来可能会添加其他约束条件，除了长度约束之外，还可以指示线路中不能重叠的特定（甚至是不妥协的）边界。

我的当前解决方案没有考虑到后一种情况，听起来需要一些复杂的工作来解决它们。

请注意，这是用于客户端Web应用程序，因此使解决方案适用于JavaScript将会很有帮助！

似乎是一个回溯算法的情况。 - Sagar V
这更像是一个装箱问题，而不是排序问题。 - Nabb
“Size”指的是什么？作为一个盒子，我认为大小是体积，因此与重量结合起来，我们通过密度进行评估。话虽如此，您还要求将盒子放在一条线上。因此，有一些缺失的信息。尺寸是三维的，但放置是一维的。您能提供更多详细信息吗？也许可以使用描述盒子的数据结构来说明。 - Enigmativity
是的，我相信如此。我已经将类比从盒子改为杆以进一步简化它。 - Daddy Warbox
1
有多少个棒子？如果只有几个，那么您可以采用暴力方法并尝试每种排列。警告：'few'的定义是“数量足够小，可以使用暴力方法”。 - High Performance Mark
显示剩余3条评论
4个回答
2
如果可能的话，我建议将此公式化为混合整数规划问题。如果您能够以这种方式编码约束条件，您可以使用求解器满足这些约束条件。 请查看此页面以获取有关此类方法的更多信息：

http://en.wikipedia.org/wiki/Linear_programming

如果你能以某种方式将其与Javascript接口，那么它可能会证明是一个优雅的解决方案。
我该如何将我的参数以线性规划问题的形式进行说明？ - Daddy Warbox
1

我不是很擅长解决算法问题，但这是我的尝试：

将其与背包问题相关联

  • 与其返回一个盒子的成本或价值，让它们分配给限制更小、能够走得更远的盒子。
  • 就像你正在努力将所有东西都靠近起点打包，而不是按照背包问题将其放入背包中。
  • 就未来日期和修改而言，我认为使用类似的约束条件仅需要修改盒子的返回价值或成本。
我纠正了约束条件是已知的这一事实。那是基于相互矛盾的信息所导致的错误。 - Daddy Warbox
约束条件并不改变问题。它们仍然保持着盒子的边界。 - loxxy
1

一开始，我尝试将其视为排序问题。但我认为将其视为优化问题更好。让我试着形式化这个问题。给定：

  • wi：杆i的重量
  • li：杆i的长度
  • mi：杆i距离原点的最大距离。如果没有限制，可以将此值设置为sum(i=1,n, li)

问题是找到一个排列ai，使得成本函数：

J=sum(i=1,n, wai*sum(j=1,i-1, laj))

最小化，并满足约束条件：

sum(j=1,i-1, laj) <= mi, 1 <= i<n

。

我不确定这是正确的表述。没有任何限制条件，最优解并不总是按重量排序的杆子。例如，令l={1,4}，w={1,3}。如果a={1,2}，则J为1*0+3*1=3，如果a={2,1}（按重量排序），则J为3*0+1*4=4。显然，未排序的解最小化成本函数，但我不确定这是否符合您的要求。

此外，我还不知道如何解决这个问题。您可以尝试在短期内进行某种启发式搜索。我正在撰写这篇改写，以便其他人可以在我思考更多解决方案的同时提供解决方案。如果它是正确的，当然。

另一个需要注意的事情是，您不必找到完整的解决方案来查看是否有解决方案。您可以忽略没有位置约束的杆子，并尝试仅使用受约束的杆子解决问题。如果存在解决方案，则该问题确实有解决方案（明显的次优解是对无约束杆进行排序，并将其附加到减少问题的解决方案中）。

说了这么多，我认为下面的算法可以解决问题。我会用一些视觉上的描述来使它更容易理解。想法是根据您的问题描述，从左到右（原点是线段的最左端点）在线段上放置杆子。
  1. 将带有位置约束的杆子分开。然后，将它们放置在其约束位置的极限处。
  2. 如果没有重叠的杆子，请转到步骤4
  3. 对于每对重叠的杆子，将较靠近原点的向原点移动，以使它们不再重叠。这一步可能需要将直线上的其他杆子向原点移动以打开一些空间。通过检查移动后的杆子是否与其左侧的杆子重叠来检测此情况。如果您无法创建足够的空间（将最靠近原点的杆子移动到0仍然无法释放足够的空间），则无解决问题的方法。在这里，您有机会通过放松原始重叠对的最右边的杆子的约束来找到解决方案：将其移离原点，直到没有重叠（在执行此操作之前，您可能需要将先导杆向右推，直到解决所有重叠为止）。
  4. 现在，我们已经放置了一些杆子，并且周围有一些空闲空间。开始用最重的杆子（包括那些在空闲空间右侧的约束杆子）填充空闲空间。如果找不到适合的杆子，则只需将空闲空间右侧的下一个杆子移动以关闭间隙。
  5. 重复步骤4，直到达到最右边的约束杆。剩余的线段均为自由空间。
  6. 按重量对所有剩余的杆子进行排序，并将它们放置在剩余的自由空间中。

关于算法的一些注释：

  • 它不能解决我之前提出的问题。它只是尝试根据杆的重量对其进行排序。

  • 我认为有一些失去的机会可以做得更好，因为我们将一些杆向原点滑动以使它们全部适合（在步骤3中），有时从这些“挤入”的地方选择重杆，并将它们靠近原点（在步骤4中）。这释放了一些空间，但我们没有将被推开的杆滑回到其受限制位置的极限。这可能是可能的，但我需要在我的大脑工作得更好时修改算法。

  • 这不是一个非常高效的算法。我有一种感觉它可以在O(n^2)内完成，但任何更好的算法都需要创造性的数据结构。您需要能够更快地找到长度小于给定L的最重的杆，以达到更好的效果。

是的，这个有点棘手。看来我需要找到一种更好地定义和分解问题的方法。嗯，谢谢你的信息。 - Daddy Warbox
1
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接