时间戳

首页 > 解决方案 > 最大化最低分数

algorithm - 最大化最低分数

问题描述

A*B给定一个值在 1-9 之间的维度网格，找到一个数字序列，当与行比较时，该序列B使匹配的值的最小数量最大化。A

描述您将采取哪些步骤来最大化最低分数。

示例：

网格尺寸

A= 5 , B= 10

网格值

9 3 9 2 9 9 4 5 7 6
6 3 4 2 8 5 7 5 9 2
4 9 5 8 3 7 3 2 7 6
7 5 8 9 9 4 7 3 3 7
2 6 8 3 2 4 5 4 2 2

可能的答案

6 3 8 2 9 4 7 5 7 4

分数计算

这个答案得分

5 与第 1 行相比

5 与第 2 行相比

1 与第 3 行相比

4 与第 4 行相比

2 与第 5 行相比

因此，这个答案的最低分数是 1。

标签： algorithmmath

解决方案

我会采用局部爬山方法，您可以通过随机化来补充以避免局部最小值。就像是：

1. Generate a random starting solution S
2. Compute its score score(S, row) for each row. We'll call min_score(S) the minimum score among all rows for S.
3. Attempt to improve the solution with:
  For each digit i (1..B) in S:
    If i belongs to a row such that score(S, row) > (min_score(S) + 1) then:
      Change i to be the digit of a row with min_score(S). If there was only one row with min_score(S), then min_score(S) has improved by 1
      Update the scores of all the rows.
  If min_score(S) hasn't improved for more than N iterations of 3, go back to 1 and start with a new random solution.

推荐阅读