解决这个分布珠子拼图的算法？

Question

假设你有一个圆圈(如下图所示),有N个斑点,你有N个珠子分布在插槽中.

这是一个例子:

每个珠子可以顺时针移动X个槽,成本为X ^ 2美元.你的目标是在每个插槽中最终得到一个珠子.为实现这项任务,您需要花费的最低金额是多少？

这个问题更有趣的变化:分配珠子拼图的算法(2)？

Answer 1

在这个答案中,我认为珠子只能移动一次.否则很明显珠子一次只能移动一个方格,这使得这个问题变得不那么有趣了:方格的总和会降级为一个简单的移动总和.

问题可以在O(n)时间内解决,在第4点我给出一个JavaScript实现.如果您想跳过导致算法的推理,只需滚动到该部分即可.

编辑:我添加了B部分,其中分析了问题的变体.

但是这些观察结果导致了手头问题的建议算法:

1.没有超车

应该观察到,在最佳解决方案中,珠子永远不会移动,使得一个珠子"超过"另一个珠子.这两个珠子交换其目标槽的替代解决方案总是会给出较低的平方和.

为了形式化这一点,让我们说一个珠子从槽号a移动到b,另一个从c移动到d.要求它们不能逆时针移动.我们现在假设第一个超越另一个,然后我们拥有所有这些真理:

1. a < b
2. c < d
3. a < c
4. b > d

然后超车版本的移动方块和替代版本的移动方块(珠子交换目标),比较如下:

(b-a)² + (d-c)² > (d-a)² + (b-c)²

证据是上述不平等分解为:

b²-2ab+a² + d²-2cd+c² > d²-2ad+a² + b²-2bc+c²
-2ab + -2cd > -2ad + -2bc
ab + cd < ad + bc
a(b-d) < c(b-d)
a < c
true

因此,在开始时共享相同槽的珠子将总是在最佳解决方案中的相邻槽中结束.

更普遍:

2.只看珠子保持相同顺序的解决方案

所以 - 如果我们给在同一个槽中开始的珠子赋予(任意)顺序 - 我们可以说可以找到最佳解决方案,其中珠子的顺序与原始输入中的相同(因为排除了超车) ).

这也意味着我们可以很容易地找到一个候选解决方案,我们通过订单号拿起珠子并将它们放在具有相同订货号的槽中.这可能不是最佳解决方案,但也可能是.如果它包含逆时针移动,它甚至可能无效.但它开始时仍然有用.

3.将解决方案循环到最佳方案

通过将所有珠子移动到下一个槽来找到保持相同顺序的任何其他潜在解决方案,直到找到有效且最佳的解决方案.我将这样的举动称为一个循环.

如果第一个候选解决方案由于逆时针移动而无效,则可以直接找到最佳解决方案:采取最大的逆时针移动,并将此移动的相反方向添加到所有移动中,包括该移动.这将使所有违规移动非逆时针(至少一个将是零移动).进一步循环显然会使平方和更大.所以这是最佳解决方案.

另一方面,如果候选溶液有效,但没有珠子保持在适当位置,则可以通过反过来循环,即通过使移动更小来改善溶液,直到至少一个珠子保持在适当位置.

4.算法

综合以上所有信息,我在这里介绍了用JavaScript实现的算法,可以在这个实时片段中进行测试:

function optimalSpread(beadCounts) {
    // Initialisation
    var n = beadCounts.length;
    var solution = {
        // Keep track of sum of squares of moves
        // A move is a number of slots and only be positive (clockwise).
        sumSquares: 0,
        // Keep track of sum of moves.
        sumMoves: 0,
        // Per slot, keep an array with one element per bead, but
        // we start with empty arrays
        movesPerSlotPerBead: [],
    };
    // Build a first a non-optimised solution. 
    // Assign beads in FIFO order to consecutive slots.
    // *move*, when added to the current slot number, identifies the first slot where
    // a bead needs to end up in this solution. Note that this initial solution
    // may do counter-clockwise moves. This will be corrected later.
    // =O(n)
    var move = 0,
        totalBeadCount = 0,
        minMove = 0;
    beadCounts.forEach(function(beadCount, slotId) {
        // check sum
        totalBeadCount += beadCount;
        // See where the next bead would be moved (relative to slot)
        move += beadCount - 1;
        // and keep the minimum value. Can be negative, meaning a 
        // counter clockwise move.
        if (move < minMove) minMove = move;
    });
    // abort if number of beads is not equal to number of slots
    if (totalBeadCount !== n) return {error: "invalid input"}; 
    // Improve solution by making sure there are no counter-clockwise
    // moves, and at least one bead stays unmoved (0).
    // Apply correction we got from previous loop to ensure this.
    // =O(n)
    move = -minMove;
    beadCounts.forEach(function(beadCount, slotId) {
        solution.movesPerSlotPerBead[slotId] = [];
        // Move each bead into next available slot
        for (; beadCount > 0; beadCount--, move++) {
            // Store the move for this bead
            solution.movesPerSlotPerBead[slotId].push(move);
            solution.sumMoves += move;
            solution.sumSquares += move*move;
        }
        // Compensate the increment of slotId
        move--;
    });
    // The solution is now optimal:
    // Cycling counter-clockwise would make at least one bead go that way;
    // Cycling clockwise would increase the sum of squares (as all moves are
    //    non-negative values)
    return solution;
}

function randomInput(n) {
    // Start with slots having all zero beads:
    beadCounts = Array.from({length: n}, x => 0);
    // Randomly assign beads to slots, keeping a count per slot
    for (var i = 0; i < n; i++) {
        beadCounts[Math.floor(Math.random() * n)]++;
    }
    return beadCounts;
}

// Link with I/O
var input = document.getElementById('input');
var randomize = document.getElementById('randomize');
var calculate = document.getElementById('calculate');
var output = document.getElementById('output');

// Capture events
randomize.onclick = function() {
    var n = 5 + Math.floor(Math.random() * 20);
    input.value = randomInput(n).join(',');
    calculate.onclick();
};

calculate.onclick = function() {
    var beadCounts = input.value.split(',').map(Number);
    var solution = optimalSpread(beadCounts);
    if (solution.error) {
        output.textContent = 'Error: ' + solution.error;
        return;
    }
    output.textContent = 
        '\nInput: ' + JSON.stringify(beadCounts) +
        '\nSum of squares of moves: ' + solution.sumSquares +
        '\nSum of moves: ' + solution.sumMoves +
        '\nMoves[slot][bead]: ' + JSON.stringify(solution.movesPerSlotPerBead);
};

Comma-separated list of number of beads per slot:<br/>
<input id="input" size="40" value="3,0,1,0,1,0,2,2,2,1,1,0,1,0">
<button id="randomize">Randomize</button><br/>
<button id="calculate">Find optimal spread</button></br>
<pre id="output"></pre>

此片段采用一个数组,其中每个索引代表一个插槽,该值表示该插槽中的珠子数.它输出原始数组,可选解决方案的平方和,以及珠子的移动列表.

问题中示例问题的输出是:

Input: [3,0,1,0,1,0,2,2,2,1,1,0,1,0]
Sum of squares of moves: 60
Sum of moves: 26
Moves[slot][bead]: [[1,2,3],[],[2],[],[1],[],[0,1],[1,2],[2,3],[3],[3],[],[2],[]]

所以示例配置的答案是:60美元.

B.附录:没有顺时针要求

如果顺时针移动的要求被移除,移动可以在任何方向怎么办？这没有被问到,但我认为这是一个有趣的变种.

以下是适用于该案例的其他观察:

B.1.一个解的平方和可以用于下一个

为了找到新配置的平方和,不需要实际执行循环:

假设我们有三个珠子和三个槽,并且通过分别移动它们的x,y和z槽,每个珠子都被移动到它们的目标槽口.例如,如果它们都在插槽0中,我们可以获得0,1,2的x,y,z值(如果我们想要夸大,也可以得到-1,0,1或甚至5,6,7).

平方和是:

x²+y²+z²

如果现在我们循环这个解决方案,从而为每个珠子的移动增加一个槽,则方块变为:

(x+1)²+(y+1)²+(z+1)²

要么:

x²+y²+z²   +3    +2(x+y+z)

一般来说,循环使用n个珠子的配置会增加这个术语的平方和:

n + 2.sum(moves)

因此,算法可以利用它并快速计算由循环产生的解的平方和.这可以在随后的循环中重复进行.

B.2.只有一个局部最小值的平方和

最后,每个连续循环(解)的平方和将是具有抛物线形状的函数,即一旦找到局部最小值,就不需要寻找另一个; 没有.我们可以从上面的公式中看出增加值sum(moves).对于两个相邻的周期,我们可能具有相等的平方和.

B.3.算法

以下是在JavaScript中实现的算法:

function optimalSpread(beadCounts) {
    // Initialisation
    var n = beadCounts.length;
    var solution = {
        // Keep track of sum of squares of moves
        // A move is a number of slots and can be negative or positive.
        sumSquares: 0,
        // Keep track of sum of moves.
        sumMoves: 0,
        // Per slot, keep an array with one element per bead, but
        // we start with empty arrays
        movesPerSlotPerBead: [],
    };
    // Build a first a non-optimised solution. 
    // Assign beads in FIFO order to consecutive slots.
    // *move*, when added to the current slot number, identifies the first slot where
    // a bead needs to end up in this solution.
    // =O(n)
    var move = 0,
        totalBeadCount = 0;
    beadCounts.forEach(function(beadCount, slotId) {
        solution.movesPerSlotPerBead[slotId] = [];
        // check sum
        totalBeadCount += beadCount;
        // Move each bead into next available slot
        for (; beadCount > 0; beadCount--, move++) {
            // Store the move for this bead
            solution.movesPerSlotPerBead[slotId].push(move);
            solution.sumMoves += move;
            solution.sumSquares += move*move;
        }
        // Compensate the increment of slotId
        move--;
    });
    // abort if number of beads is not equal to number of slots
    if (totalBeadCount !== n) return {error: "invalid input"}; 
    // See if solution can be improved by shifting all beads in one direction.
    // =O(n)
    bestMoveCorrection = 0;
    while (true) {
        // Improvement is only possible in the direction dictated by sumMoves 
        moveCorrection = (solution.sumMoves < 0 ? 1 : -1);
        // Calculate the delta this brings to sumSquares:
        // (a+1)²+(b+1)²+ ... +(x+1)² = a²+b²+...+x² +n  +2(a+b+...+x) 
        sumSquaresChange = n + moveCorrection * 2 * solution.sumMoves;
        // Stop if this brings no improvement anymore
        if (sumSquaresChange >= 0) break;
        // It is an improvement; keep it
        solution.sumMoves += moveCorrection * n;
        solution.sumSquares += sumSquaresChange;
        bestMoveCorrection += moveCorrection;
    }
    // Apply correction to solution, to make it optimal
    // =O(n)
    solution.movesPerSlotPerBead.forEach(function(moves) {
        moves.forEach(function(move, idx) {
            moves[idx] += bestMoveCorrection;
        });
    });
    return solution;
}

function randomInput(n) {
    // Start with slots having all zero beads:
    beadCounts = Array.from({length: n}, x => 0);
    // Randomly assign beads to slots, keeping a count per slot
    for (var i = 0; i < n; i++) {
        beadCounts[Math.floor(Math.random() * n)]++;
    }
    return beadCounts;
}

// Link with I/O
var input = document.getElementById('input');
var randomize = document.getElementById('randomize');
var calculate = document.getElementById('calculate');
var output = document.getElementById('output');

// Capture events
randomize.onclick = function() {
    var n = 5 + Math.floor(Math.random() * 20);
    input.value = randomInput(n).join(',');
    calculate.onclick();
};

calculate.onclick = function() {
    var beadCounts = input.value.split(',').map(Number);
    var solution = optimalSpread(beadCounts);
    if (solution.error) {
        output.textContent = 'Error: ' + solution.error;
        return;
    }
    output.textContent = 
        '\nInput: ' + JSON.stringify(beadCounts) +
        '\nSum of squares of moves: ' + solution.sumSquares +
        '\nSum of moves: ' + solution.sumMoves +
        '\nMoves[slot][bead]: ' + JSON.stringify(solution.movesPerSlotPerBead);
};

Comma-separated list of number of beads per slot:<br/>
<input id="input" size="40" value="3,0,1,0,1,0,2,2,2,1,1,0,1,0">
<button id="randomize">Randomize</button><br/>
<button id="calculate">Find optimal spread</button></br>
<pre id="output"></pre>

此片段采用一个数组,其中每个索引代表一个插槽,该值表示该插槽中的珠子数.它输出原始数组,可选解决方案的平方和,以及珠子的移动列表.

问题中示例问题的输出是:

Input: [3,0,1,0,1,0,2,2,2,1,1,0,1,0]  
Sum of squares of moves: 12  
Sum of moves: -2  
Moves[slot][bead]: [[-1,0,1],[],[0],[],[-1],[],[-2,-1],[-1,0],[0,1],[1],[1],[],[0],[]]

注意:这不是问题的答案,因为它允许逆时针移动.有关答案,请参阅此回复的前半部分.