识别此算法:插槽和桩

我有一些直线排列的插槽和钉子.栓可以移动,需要每个都移动到一个槽.只有在采取所有钉子时,才能将槽留空.移动挂钉时,不允许穿过另一个挂钉.换句话说,必须保持钉的顺序.优选地,所有钉子移动的总距离应保持最小.应尽可能将挂钉置于最近的可用插槽中.

我想知道的是:什么样的数学领域处理这样的问题？处理类似问题的任何众所周知的算法的名称是什么？我正在寻找Google饲料.一些关键字.

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

+ - Slots
o - Pegs

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

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

编辑:只是想明确说明插槽的数量可以大于,小于或等于挂钩的数量.

我认为这是动态编程解决方案的经典素材.事实上,看一下"序列对齐",这可能是该维基百科页面上另一个好的搜索词.

关键的见解是这样的:

想象一下,你有一个挂钉位置列表(peg1:更多挂钩)和插槽作为插槽位置列表(插槽1:更多插槽).调用此问题(peg1:pegs,slot1:slots).然后解决方案是插槽1中的peg1和(插头,插槽)的解决方案,或者它是(peg1:pegs,slot)的解决方案.

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

或者在伪代码中(用函数式编程风格编写),想象一下函数距离(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)

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