algorithm - 识别这个算法 : Slots and Pegs

Question

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

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

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

+ - Slots
o - Pegs

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

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

编辑:只是想说明插槽的数量可以大于、小于或等于钉的数量。

Answer 1

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

关键的见解是:

想象一下，您将钉子作为钉子位置列表(peg1:more pegs)，并将插槽作为插槽位置列表(slot1:more 插槽)。称此问题为 (peg1:pegs, slot1:slots)。那么解决方案要么是 slot1 中的 peg1 和 (pegs, slots) 的解决方案，要么是 (peg1:pegs, slots) 的解决方案。

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

或者在伪代码(以函数式编程风格编写)中，想象一个函数 distance(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)

通过将距离组合到数据结构中，应该可以使该解决方案更加高效。