Максимизировать минимальный балл

Question

Учитывая сетку измерений 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.

Answer 1

Я бы go предложил местный подход к восхождению на холм, который можно дополнить рандомизацией, чтобы избежать локальных минимумов. Что-то вроде:

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.