Задача оптимизации (MST?)
Учитывая матрицу из R строк {r0, ..., rn} и C столбцов {c0, ..., cn}, выберите наименьшее количество строк, в которых также выбирается максимальное количество столбцов с наименьшим перекрытием
100% решение не всегда будет доступно. Порядок строк не имеет значения. Решением является набор индексов строк.
c0 c1 c2 c3 c4 c5 c6 c7
r0 0 1 1 0 0 0 0 0
r1 0 0 0 1 1 0 0 1
r2 1 1 0 1 1 1 1 0
r3 0 1 1 0 0 0 0 0
r4 0 0 0 0 0 1 1 1
r5 0 0 1 0 0 0 0 0
r6 0 1 1 0 1 1 0 1
r7 1 0 1 0 1 0 0 1
r8 0 0 0 0 1 0 0 1
r9 0 1 0 0 1 0 0 1
Решение по наблюдению:
r2 & r7 (все столбцы отмечены хотя бы один раз, минимальное перекрытие в тиках)
Большой вопрос
Какой алгоритм, оптимальный, если возможно, грубая сила, если необходимо, можно было бы использовать для решения этой проблемы?
Соображения по шкале ... Количество строк обычно быть в 10 или 100, количество столбцов, как правило, будет в диапазоне от 1000 до 10000 +
То, что я пробовал - процедурное решение
Данные хранятся в паре MySQL таблиц, поэтому я решил попробовать следующее:
- Подсчитать количество попаданий столбцов по строкам, упорядочить по убыванию и выбрать строку с наибольшим количеством - ссылочная строка
c0 c1 c2 c3 c4 c5 c6 c7 count
>r2 1 1 0 1 1 1 1 0 6
r6 0 1 1 0 1 1 0 1 5
r7 1 0 1 0 1 0 0 1 4
r1 0 0 0 1 1 0 0 1 3
r4 0 0 0 0 0 1 1 1 3
r9 0 1 0 0 1 0 0 1 3
r0 0 1 1 0 0 0 0 0 2
r3 0 1 1 0 0 0 0 0 2
r8 0 0 0 0 1 0 0 1 2
r5 0 0 1 0 0 0 0 0 1
Определение отсутствующих столбцов в выбранной строке (r2 отсутствует c2 и c7)
Выберите строки, в которых один или несколько из отсутствующих столбцов и наименьшее количество совпадающих столбцов из контрольной строки, упорядоченной по убыванию отсчета, по возрастанию числа перекрытий - выберите верхнюю (наиболее подходящую) строку
c0 c1 c2 c3 c4 c5 c6 c7 count missing-count overlap-count
>r2 1 1 0 1 1 1 1 0 6 - -
>r7 1 0 1 0 1 0 0 1 4 2 2
r6 0 1 1 0 1 1 0 1 5 2 3
r0 0 1 1 0 0 0 0 0 2 1 1
r3 0 1 1 0 0 0 0 0 2 1 1
r8 0 0 0 0 1 0 0 1 2 1 1
r5 0 0 1 0 0 0 0 0 1 1 1
r1 0 0 0 1 1 0 0 1 3 1 2
r4 0 0 0 0 0 1 1 1 3 1 2
r9 0 1 0 0 1 0 0 1 3 1 2
Повторять до тех пор, пока количество обращений к отдельным столбцам не станет равным количеству столбцов или пока количество выбранных строк не увеличится
Но с большими наборами данных оно стало довольно громоздким довольно быстро