代码之家 › 专栏 › 技术社区 › Agnel Kurian

识别此算法:插槽和钉子

math algorithm

Agnel Kurian · 技术社区 · 16 年前

我把许多槽和钉子排成一条直线。钉子可以移动,每个钉子都需要移动到一个槽中。只有当所有钉子都被取下时,插槽才能留空。当一个钉子被移动时,不允许越过另一个钉子。换句话说,必须保持钉子的顺序。最好将所有木桩移动的总距离保持在最小值。应尽可能将钉子放在最近的可用插槽中。

我只想知道:数学的哪个领域处理这样的问题?处理类似问题的任何已知算法的名称是什么?我正在寻找谷歌的素材。一些关键词。

+--oooo-+--+---+---o--+------+--+-ooo+o-+-------o--+-----o-o-+-o

+ - Slots
o - Pegs

编辑: 我认为这种可视化更有意义。它们是两条需要排列的独立轨道。

Slots: +-------+--+---+------+------+--+----+--+----------+---------+--
Pegs:  ---oooo------------o--------------ooo-o---------o--------o-o---o

编辑: 只是想明确一点,插槽的数量可以大于、小于或等于钉子的数量。

6 回复 | 直到 16 年前

Nick Fortescue 16 年前

我认为这是一个经典的素材 dynamic programming 解决方案。事实上,看看“序列比对”,这可能是维基百科页面上的另一个很好的搜索词。

关键的见解是:

想象一下,你的钉子是一个钉子位置列表(钉子1:更多钉子),插槽是一个插槽位置列表(插槽1:更多插槽)。称此问题为(peg1:挂钩,slot1:插槽)。那么,解决方案要么是插槽1中的peg1;(pegs,slots)的解决方案,或者它就是(peg1:pegs,slots)的解。

这给出了如何解决它的递归定义。

或者在伪代码中(以函数式编程风格编写),想象一个函数距离(peg、slot):

distance([]) = 0
distance((peg,slot):matches) = distance(peg,slot)+distance(matches)

solution(peg:[], slot:[]) = [(peg,slot)]
solution(peg:pegs, slot:slots) = if distance(a)<distance(b) then a else b
   where a = solution(peg:pegs, slots) and b=(peg,slot):solution(pegs, slots)

通过将距离组合到数据结构中,应该使该解决方案更有效。

Konrad Rudolph 16 年前

我不知道这个问题从哪里来,但我很确定这是一种 combinatorial optimization ,更具体地说,可以使用 (integer) linear programming .

Die in Sente 16 年前

“所有木桩移动的总距离应保持在最低限度”

除非我遗漏了什么,否则这不是问题。

由于必须保持木桩的顺序,您可以将木桩编号为1、2、3、。..

+--1234-+--+---+---5--+------+--+-678+9-+-------10--+-----11-12-+-13

最终状态必须是槽1中的栓钉1、槽2中的栓钉2等。

+--1-+-2-+-3-+-4-+-5-+-6-+-7-+-8-+-9-+-10-+-11-+-12-+-13-+

不能让钉子跳过彼此并不重要,每个钉子都必须从起点移动到终点一定距离。 只要所有动作都朝着正确的方向,挂钩永远不必后退 ,那么每个单独的钉子必须移动的距离是一个简单的常数(它不取决于移动的顺序),这些距离的总和,你的成本函数也是常数。

我认为这里不需要动态规划或线性规划优化问题。

如果你引入了一个拾取钉子并将其放下的成本,那么这里可能存在一个优化问题,但即使是这样也可能是微不足道的。

编辑针对1800 Information的评论

只有当槽的数量等于桩的数量- 问题中没有假设这一点 1800信息(2小时以前)

好吧,我错过了。谢谢你指出我错过了什么。不过,我仍然不相信这是火箭科学。

假设#pegs>#洞。如上所述计算最终状态,就像你有额外的孔一样;然后选择移动得最远的N个钉子,并将其从问题中删除:这些钉子没有移动。重新计算忽略这些挂钩。

假设#holes>#钉子。正确的最终状态可能有也可能没有间隙。如上所述计算最终状态,并寻找相邻桩相互靠近的位置。这些是你可以将其分解为可以轻松解决的子问题的地方。当你在连续子问题的两端都有洞时,还有一个额外的变量——最终连续序列从哪里开始。

是的,这比我一开始想象的要复杂一些,但似乎一点铅笔和纸的工作应该表明,解决方案是几个易于理解和编码的循环。

joel.neely 16 年前

组合学。组合算法。具体数学。(标题也 an excellent and relevant book Donald Knuth。

cletus 16 年前

如果桩数==槽数,则只存在一个解。第一个挂钩必须转到第一个槽,下一个挂钩必须到下一个槽,以此类推。

数字不同,那么它就稍微复杂一些,因为一个钉子或插槽(无论我们可以移动哪个)可以移动到许多地方。

蛮力: 假设对象的数量是m个桩和n个槽(可互换);n

对于每种方式(n-m),插槽可以是选择(参考一些组合学算法来看看如何做到这一点)
1. 所选的(n-m)个插槽将为空。
2. 用木桩填满剩余的m个槽。计算移动的距离。这与上面讨论的情况相同。
选择移动距离最小的排列。

递归解决方案:

    int solve(int pegs, int *peg_x, int slots, int *slot_x)
    {
      if (slots > pegs )
        return solve(slots, slot_x, pegs, peg_x);
      if (slots == 0 || pegs==0)
        return 0; // Cannot move

      int option1 = INT_MAX, options2 = INT_MAX;


      if (pegs > slots ) // Can try skipping a peg
        option1 = solve(pegs-1, peg_x+1 /* Move over one element */
                          slots, slot_x);
      // pegs >= slots 
      option2 = solve(pegs-1, peg_x+1, slots-1, slot_x+1)
                + abs(peg_x[0]-slot_x[0]);
      return min(option1, option2);
    }

此解决方案仍然需要将结果存储在表中,这样就不会多次解决任何子问题,从而成为动态解决方案。

思考。…将更新。....

-1

alphadogg 16 年前

排队论或数学。..