algorithm - 分区彩色网格

Question

我想要一个网格这意味着，给定一个n x m的网格，其中有黄色和红色的正方形，我希望以这样的方式对网格进行分区，即黄色将是尽可能多的分区中的大多数颜色，如下图所示：

所有的分区必须是连续的，相同数量的正方形，所有的正方形都是彩色的（尽管如果一个算法可以推广到一些没有彩色的正方形的网格上，那就太棒了）。
我不知道如何去“算法化”这个问题，过去的暴力迫使每一个可能的分区，这本身就足够困难，是难以置信的低效。
最好的方法是什么？

Answer 1

tl；dr：使用模拟退火，在地区之间交换选民。
底部的演示程序允许您执行交换步骤（随机演化）并优化gerrymandered区域（anneal）
一般优化
我们可以把这个框架化为最优化问题，我们试图最大化地区的数量。
红队获胜，蓝队获胜的地区数量也减少了。
让我们把这个形式化：

function heuristic(state) {
  return state.districts_that_red_wins - state.districts_that_blue_wins;
}

其中 state是选民分配到地区。
这是可行的，但可以改进一点。
让我们引入 wasted votes的概念，将我们的优化推向正确的方向。
我们希望最大限度地浪费蓝色选票和尽量减少浪费的红色选票。
我武断地认为他们是一个地区十分之一的重要，因为每个地区有10个选民。
这给了我们一个最大化的功能：

function heuristic(state) {
  let {red_wins, blue_wins, tied, wasted_red_votes, wasted_blue_votes} = get_winners(state, voters);
  return red_wins - blue_wins - 0.1 * wasted_red_votes + 0.1 * wasted_blue_votes;
}

你可能想优化其他的东西，例如地区的紧凑性。您可以将这些添加到启发函数中。
模拟退火
让我们选择一个优化算法来优化 state。
我们受到一些限制，使得很难生成符合这些条件的随机映射。
我怀疑如果没有暴力，就不可能找到最好的地区分配，这是不可能的。
所以让我们使用一个算法，让我们迭代地改进我们的解决方案。
我喜欢 simulated annealing，因为它易于实现和理解，而且通过防止我们陷入早期的局部最优，它的性能比爬山要好一点。
我的温度函数就是 max(0.8 - iterations/total_iterations, 0)。在开始的时候，20%的时间，我们会采取一个新的状态，如果而且只有当它更好；其他80%的时间，我们会采取新的状态，无论。
慢慢地，这变得更像爬山，直到我们完成了80%的计算预算，然后我们只改变状态，如果它提高了我们的启发式得分选择80%是完全武断的。
要实现sa，我们需要一个初始状态（或生成它的方法）。为了简单起见，我将使用“完美表示”作为初始状态，主要是因为我不知道如何生成随机连接、大小相等的区域。
我们还需要一种对国家做出微小改变的方式我将在下一节讨论这个问题。
最后，我们需要一种给各州打分的方法让我们使用上一节中的函数，因为它的计算成本很低。
如果您感兴趣，可以查看 anneal函数，或者直接阅读wikipedia文章。
状态演化
对于这个问题，给定一个状态，我们需要找到另一个类似的状态，这个状态不会对启发式得分有太大的改变，看看我们是否朝着正确的方向前进。
我选择从两个不同的地区找到一对点并交换它们。
我们需要保持一些不变量：
保持所有地区的连续性
保持所有区域的大小相同
第二个很简单：总是交换点，从不（永久地）从一个地区分配到另一个地区。
第一个是更复杂的，我们需要一个简短的绕道进入图论清晰度点（见图）是一个点，如果不将图形平分，则无法删除该点。
对我们来说，这意味着我们不能删除连接点而不使一个区域不连续。
一旦我们有一个点可以删除，我们需要确保它被添加到一个邻近的地区这很简单。
因为我们在一个网格上，所有的区域必须是连续的，所以我们可以考虑一个点的近邻来确定它是否是一个连接点。
如果你看不到这一点，那就不是特别重要了，你可以在一个图上使用通常有效的 algorithm。
我发现网格版本更容易，因为它不涉及递归。
如果您感兴趣，请参见 is_swappable函数。这就是演示中的“随机进化”按钮所做的。
在高层，我们的国家进化代码应该是这样的：

function evolve_state() {
    randomly pick a source district
    randomly pick a non-articulation point, source_point, from source_district

    for each neighbour of the articulation point
        if the neighbour is in a different district target_district
            temporarily remove source_point from source_district and add it to target_district
            if any articulation point (other than source point), target_point, in target_district is adjacent to source_district
                swap target_point and source_point
                return;
            restore source_point
}

注意：我以一种随机遍历所有 source_district、 source_point、 neighbour、 target_district和 target_point的方式实现了这一点，因为我不确定这会有多稀疏。
如果您准确地实现了这个伪代码，您可能需要比我用于收敛到解决方案的迭代次数更多的迭代。
如果您感兴趣，请参见 evolve_state。
我没有调用的每个函数都是一个实用函数或用于绘图的函数。
演示
现在来演示一下。：）
（将lodash用于实用函数，将mithril用于dom操作）
如果你想玩这个游戏，用我的小东西可能会更容易些。

const RED = 'R';
const BLUE = 'B';
const VOTERS_PER_DISTRICT = 10;
const neighbours = [{x: 1, y: 0}, {x: 0, y: 1}, {x: -1, y: 0}, {x: 0, y: -1}];

/* UTILITY FUNCTIONS */

/**
 Create a generator that starts at a random point p, 0 <= p < max
 The generator will iterate over values p, p+1, ... max, 0, ... p-1
*/
function* cyclic_generator(max) {
    let start = _.random(max);

    for (let i=0; i<max; i++) {
        yield (i + start) % max;
    }
}

/**
  Return grid[x][y] if x and y are within grid. Otherwise return undefined
*/
function grid_get(grid, x, y) {
  if(_.isUndefined(grid[x])) {
    return undefined;
  }
  else {
    return grid[x][y];
  }
}

/** Generates a 2d array red and blue voters */
function generate_voters() {
  return _.times(5, x => _.times(10, () => {return {vote: x > 2 ? RED : BLUE, district_vote: 0xffffff}}))
}

/** Generate an initial state */ 
function generate_initial_state() {
  return _.range(5).map(x => _.range(10).map(y => {return {x, y}}));
}

/**
  Randomly swap two squares in the grid between two districts. 
  The new square to be added must be connected to the district, and the 
  old square must not break another district in two
 */
function evolve_state(state) {
  state = _.cloneDeep(state);
  
  // Create a grid with the district number
  let point_to_district = _.range(5).map(x => _.range(10).map(y => -1));
  state.forEach((district, i) => district.forEach(({x, y}) => point_to_district[x][y] = i));

  // swap a point from source_district to target_district.
  // then swap a point from target_district to source_district. 
  for(let source_district_idx of cyclic_generator(state.length)) {
    let source_articulation_points = state[source_district_idx].filter(point => is_swappable(point_to_district, point, source_district_idx));
    for(let source_point_idx of cyclic_generator(source_articulation_points.length)) {
      let source_point = source_articulation_points[source_point_idx];
      
      for(let neighbour_idx of cyclic_generator(4)) {
        let neighbour = neighbours[neighbour_idx];
        let target_district_idx = grid_get(point_to_district, source_point.x + neighbour.x, source_point.y + neighbour.y);
        if (_.isUndefined(target_district_idx) || target_district_idx == source_district_idx) {
          continue;
        }
        
        // swap the source point
        point_to_district[source_point.x][source_point.y] = target_district_idx;
        _.remove(state[source_district_idx], ({x, y}) => x == source_point.x && y == source_point.y); 
        // we don't add the point the the target array yet because we don't want to swap that point back
        
        // try to find a point in target_district that we can move to source_district
        let target_articulation_points = state[target_district_idx].filter(point => is_swappable(point_to_district, point, target_district_idx));
        for(let target_point_idx of cyclic_generator(target_articulation_points.length)) {
          let target_point = target_articulation_points[target_point_idx];
          for(let n of neighbours) {
            if(grid_get(point_to_district, target_point.x + n.x, target_point.y + n.y) === source_district_idx) {
              
              // found a point that we can swap!
              // console.log('swapping points!', source_point, target_point);
              
              _.remove(state[target_district_idx], ({x, y}) => x == target_point.x && y == target_point.y);
              state[target_district_idx].push(source_point);
              state[source_district_idx].push(target_point);
              return state;
            }
          }
        }
        
        // unswap source point since we were unsuccessful
        point_to_district[source_point.x][source_point.y] = source_district_idx;
        state[source_district_idx].push(source_point);
      }
    }
  }
  throw 'Could not find any states to swap' // this should never happen, since there will always be the option of reversing the previous step
}

/*
  Return whether a point can be removed from a district without creating disjoint districts. 
  In graph theory, points that cannot be removed are articulation points. 
  For a general algorithm, see: https://stackoverflow.com/questions/15873153/explanation-of-algorithm-for-finding-articulation-points-or-cut-vertices-of-a-gr
  
  My version takes advantage of the fact that we're on a grid and that all the districts must be continuous, 
  so we can consider only the immediate neighbours of a point.
*/
function is_swappable(grid, p, district) {
  
  // if the the point is not even in this district, it makes no sense for this to consider this point at all
  if(grid[p.x][p.y] != district) {
    return false;
  }
  
  // if two opposite edges are part of this district, this is an articulation point
  // .x.  x is an articulation point
  // Exception:
  // .x.  x is not an articulation point
  // ...
  if (grid_get(grid, p.x+1, p.y) === district && grid_get(grid, p.x-1, p.y) === district && grid_get(grid, p.x, p.y+1) !== district && grid_get(grid, p.x, p.y-1) !== district) {
    return false;
  }
  if (grid_get(grid, p.x, p.y+1) === district && grid_get(grid, p.x, p.y-1) === district && grid_get(grid, p.x+1, p.y) !== district && grid_get(grid, p.x-1, p.y) !== district) {
    return false;
  }
  
  // check if any corners are missing:
  // .x  x is not an articulation point      .x   x is an articulation point
  // ..                                       .
  for(let i = 0; i < 4; i++) {
    let nx = neighbours[i].x;
    let ny = neighbours[i].y;
    let nx2 = neighbours[(i+1)%4].x;
    let ny2 = neighbours[(i+1)%4].y;
    
    if (grid_get(grid, p.x+nx, p.y+ny) === district && grid_get(grid, p.x+nx2, p.y+ny2) === district && grid_get(grid, p.x+nx+nx2, p.y+ny+ny2) !== district) {
      return false;
    }
  }
  return true;
}

/** Count how many districts each party wins */
function get_winners(state, voters) {
  let red_wins = 0;
  let blue_wins = 0;
  let tied = 0;
  
  let wasted_red_votes= 0; // see https://en.wikipedia.org/wiki/Wasted_vote
  let wasted_blue_votes = 0;
  
  state.forEach(district => {
    let counts = _.countBy(district.map(({x, y}) => voters[x][y].vote))
    
    if ((counts[BLUE] || 0) > (counts[RED] || 0)) {
      blue_wins++;
      wasted_blue_votes += (counts[BLUE] || 0) - VOTERS_PER_DISTRICT / 2 - 1;
      wasted_red_votes += (counts[RED] || 0);
    }
    else if ((counts[RED] || 0) > (counts[BLUE] || 0)) {
      red_wins++;
      wasted_red_votes += (counts[RED] || 0) - VOTERS_PER_DISTRICT / 2 - 1;
      wasted_blue_votes += (counts[BLUE] || 0);
    }
    else {
      tied++;
    }
  });
  return {red_wins, blue_wins, tied, wasted_red_votes, wasted_blue_votes};
}

/* GUI */

/* Display a grid showing which districts each party won */
function render_districts(state, voters) {
  let red_districts = 0;
  let blue_districts = 0;
  let grey_districts = 0;
  
  // Color each district
  state.forEach(district => {
    let counts = _.countBy(district.map(({x, y}) => voters[x][y].vote))

    let district_color;
    if ((counts[BLUE] || 0) > (counts[RED] || 0)) {
      district_color = 'blue' + blue_districts++;
    }
    else if ((counts[RED] || 0) > (counts[BLUE] || 0)) {
      district_color = 'red' + red_districts++;
    }
    else {
      district_color = 'grey' + grey_districts++;
    }
    
    district.map(({x, y}) => voters[x][y].district_color = district_color);
  });
  
  return m('table', [
    m('tbody', voters.map(row => 
      m('tr', row.map(cell => m('td', {'class': cell.district_color}, cell.vote)))
    ))
  ]);
}

/** Score a state with four criteria: 
  - maximize number of red districts
  - minimize number of blue districts
  - minimize number of red voters in districts that red wins
  - maximize number of blue voters in districts that blue wins
  
  The first two criteria are arbitrarily worth 10x more than the latter two
  The latter two are to nudge the final result toward the correct solution
 */
function heuristic(state) {
  let {red_wins, blue_wins, tied, wasted_red_votes, wasted_blue_votes} = get_winners(state, voters);
  return red_wins - blue_wins - 0.1 * wasted_red_votes + 0.1 * wasted_blue_votes;
}

/**
 Optimization routine to find the maximum of prob_fcn.
 prob_fcn: function to maximize. should take state as its argument
 transition: how to generate another state from the previous state
 initialize_state: a function that returns an initial state
 iters: number of iterations to run
 
 Stolen from my repo here: https://github.com/c2huc2hu/automated-cryptanalysis/blob/master/part3.js
*/
function anneal(prob_fcn, transition, initialize_state, seeds=1, iters=1000) {
    let best_result = initialize_state();

    for(let i=0; i<seeds; i++) {
        let curr_state = initialize_state();
        let curr_cost = prob_fcn(curr_state);

        // perform annealing. do a few extra steps with temp=0 to refine the final solution
        for(let j=0; j<iters; j++) {
            let candidate_state = transition(curr_state);
            let candidate_cost = prob_fcn(candidate_state);
            temp = 0.8 - j / iters;

            if(candidate_cost >= curr_cost || Math.random() < temp) {
                curr_state = candidate_state;
                curr_cost = candidate_cost;
            }
        }

        if(prob_fcn(curr_state) > prob_fcn(best_result)) {
            best_result = curr_state;
        }
    }

    return best_result;
}

let voters = generate_voters();
let state = generate_initial_state();

// main rendering code: this code renders the UI
m.mount(document.getElementById('actions'), {view: function() {
  return m('div', [
    m('button', {onclick: () => state = generate_initial_state()}, 'Reset'),
    m('button', {onclick: () => state = evolve_state(state)}, 'Randomly evolve'), // randomly evolves

    m('br'),
    m('label', {'for': 'radio-blue'}, 'Gerrymander for blue'),
    m('input', {type: 'radio', name: 'heuristic', value: 'blue', id: 'radio-blue'}),
    m('label', {'for': 'radio-red'}, 'Gerrymander for red'),
    m('input', {type: 'radio', name: 'heuristic', value: 'red', id: 'radio-red'}),
    m('br'),
    m('label', {'for': 'anneal-steps'}, 'Anneal steps: '),
    m('input', {id: 'anneal-steps', type: 'number', value: '500'}),
    m('button', {onclick: function() {
      let minimize = document.getElementById('radio-red').checked;
      let _heuristic = minimize ? heuristic : state => -heuristic(state)
      
      let new_state = anneal(_heuristic, evolve_state, generate_initial_state, 1, parseInt(document.getElementById('anneal-steps').value));
      if(_heuristic(new_state) > _heuristic(state)) {
        state = new_state;
      }
      else {
        console.log('found no better solutions')
      }
    }}, 'Anneal!'),
  ]);
}});

// This renders the grid
m.mount(document.getElementById('grid'), {
  view: function() {
    return render_districts(state, voters)
  }
});

// state = anneal(heuristic, evolve_state, generate_initial_state, 5, 1000);
document.getElementById('radio-red').checked = true;
m.redraw();

/* Layout */

table {
  border: solid 1px black;
}

td {
  padding: 5px;
  border: solid 1px black;
}

button {
  margin: 10px;
}

p {
  max-width: 500px;
}

/* Colour classes. In hindsight, this wasn't a good idea */
.red0 {
  background-color: red;
}
.red1 {
  background-color: darkred;
}
.red2 {
  background-color: pink;
}
.red3 {
  background-color: deeppink;
}
.red4 {
  background-color: lightsalmon;
}

.blue0 {
  background-color: aqua;
}
.blue1 {
  background-color: cadetblue;
}
.blue2 {
  background-color: steelblue;
}
.blue3 {
  background-color: royalblue;
}
.blue4 {
  background-color: midnightblue;
}

.grey0 {
  background-color: lightgrey;
}
.grey1 {
  background-color: silver;
}
.grey2 {
  background-color: darkgray;
}
.grey3 {
  background-color: gray;
}
.grey4 {
  background-color: dimgray;
}

<!DOCTYPE html>
<html>

  <head>
    <script data-require="lodash.js@4.17.4" data-semver="4.17.4" src="https://cdn.jsdelivr.net/npm/lodash@4.17.4/lodash.min.js"></script>
    <script data-require="mithril@1.0.1" data-semver="1.0.1" src="https://cdnjs.cloudflare.com/ajax/libs/mithril/1.0.1/mithril.js"></script>
    <link rel="stylesheet" href="style.css" />
  </head>

  <body>
    <h1>Gerrymandering simulation</h1>
    
    <p>
      There are two parties, red and blue (chosen because they contrast well).
      Each person will always vote a certain way, and is marked with R or B in the table. 
      People are divided into districts, shown here as groups of people marked in a single colour.
    </p>
    
    <p>
      Use the buttons below to divide up districts.
      The reset button will restore the initial state.
      The randomly-evolve button will swap two people between districts
      The anneal button will optimize for your chosen party. 
      You should limit the number of steps to ~1000 or your browser will appear to hang.
      In general, it is sufficient to run a few seeds for 500 iterations. 
    </p>
    
    <div id="grid"></div>
    
    <div id="actions"></div>
    
    <script src="script.js"></script>
  </body>

</html>