Господа Математические Мозги!
Уже несколько недель бьюсь над следующей задачкой:
У нас есть матрица. В матрице есть некоторое количество случайных пропусков. Они могут быть подряд, могут быть по одному. Короче, они случайные, их много. Можно вычёркивать столбцы и/или строки. Задача: получить матрицу без пропусков, с максимальным количеством элементов, но количество строк и столбцов должно быть не меньше некоторого заранее заданного значения. По какому алгоритму надо вычёркивать?
Алгоритм «вычёркивать те строки/столбцы, где число ЗАПОЛНЕННЫХ элементов МИНИМАЛЬНО» не является оптимальным: немного от него отступив, можно получитьматрицу с бОльшим числом элементов. Пример здесь: хттп://files.мейл.ру/IFNPKH
Были мысли о том, чтобы «кандидатам на вычёркивание» присвоить веса в зависимости от того, насколько заполнены те строки/столбцы, на пересечении с которыми есть значения в матрице, но доказать его оптимальность я не могу, равно как и понять, как именно присваивать эти веса.
Перебором делать не хочу, т.к. размер матрицы достигает 400 на 400, и таких матриц несколько.
Буду благодарна за идеи 
27 марта 2009 в 18:02
Что делать в случае, если нельзя никак получить матрицу без пропусков в силу ограничения на количество оставляемых строк и столбцов? Или данные таковы, что это всегда возможно?
26 марта 2009 в 13:00
ммм.. вообще говоря, уж больно такая матрица похожа на матрицу описания задачи для DLX-алгоритма (если инвертировать значения – пустое сделать 1, непустое – 0).
возможно, если заюзать DLX – то будет быстро найдено множество решений, из которых можно выбрать подходящее.
25 марта 2009 в 23:02
это жадный алгоритм, не всегда приводящий к оптимальному решению.
25 марта 2009 в 23:01
>но количество строк и столбцов должно быть не меньше некоторого
>заранее заданного значения
Татьяна, а Вы не могли бы описать конкретные данные по ограничению.. Тоесть это ограничение произвольно ? Да и это ограничение распространяется одинаково на строки и на столбцы тоесть NxN или для строк одно, для столбцов другое, тоесть NxM. м ? )
Задачка интересна ) Я кстати пока не понимаю почему
"Алгоритм «вычёркивать те строки/столбцы, где число ЗАПОЛНЕННЫХ элементов МИНИМАЛЬНО» не является оптимальным." Ну я особо не исследовал вообщем-то.. )
25 марта 2009 в 23:00
в виду своего нематематического образования ушла читать про то, что такое теория графов
)
25 марта 2009 в 22:00
Если сделать из матрицы такой граф: вершинами будут строки и столбцы матрицы, а ребрами – пропуски в матрице, то задача превратится в нахождение вершинного покрытия на графе. Это, как известно, NP-полная задача.
То есть, по-видимому, ваша задача также NP-полная (правда, строго доказывать эквивалентность задач мне лень, но так вроде похоже). Следовательно, другого решения, кроме перебора с какими-нибудь оптимизациями и отсечениями придумать не получится
25 марта 2009 в 21:04
Не совсем уверен, что мыслю правильно, но есть такой вариант:
по сути – решение ищется полным перебором, только в тело этого перебора добавляется некоторое условие оптимальности, которое резко сократит количество переборов.
Такой подход часто используется при решении задач в теории графов.
(редактировано)
да и в нем нужно будет использовать рекурсию.
25 марта 2009 в 21:04
Если такой вариант устроит, пишите в личку.