singlepost

Хитрый алгоритм (или вопрос оптимизации) << На главную или назад  

Господа Математические Мозги!
Уже несколько недель бьюсь над следующей задачкой:

У нас есть матрица. В матрице есть некоторое количество случайных пропусков. Они могут быть подряд, могут быть по одному. Короче, они случайные, их много. Можно вычёркивать столбцы и/или строки. Задача: получить матрицу без пропусков, с максимальным количеством элементов, но количество строк и столбцов должно быть не меньше некоторого заранее заданного значения. По какому алгоритму надо вычёркивать?

Алгоритм «вычёркивать те строки/столбцы, где число ЗАПОЛНЕННЫХ элементов МИНИМАЛЬНО» не является оптимальным: немного от него отступив, можно получитьматрицу с бОльшим числом элементов. Пример здесь: хттп://files.мейл.ру/IFNPKH

Были мысли о том, чтобы «кандидатам на вычёркивание» присвоить веса в зависимости от того, насколько заполнены те строки/столбцы, на пересечении с которыми есть значения в матрице, но доказать его оптимальность я не могу, равно как и понять, как именно присваивать эти веса.

Перебором делать не хочу, т.к. размер матрицы достигает 400 на 400, и таких матриц несколько.

Буду благодарна за идеи :)

81 ответов в теме “Хитрый алгоритм (или вопрос оптимизации)”

  1. 8
    Ромка Удовиченко ответил:

    Что делать в случае, если нельзя никак получить матрицу без пропусков в силу ограничения на количество оставляемых строк и столбцов? Или данные таковы, что это всегда возможно?

  2. 7
    Константин Смирнов ответил:

    ммм.. вообще говоря, уж больно такая матрица похожа на матрицу описания задачи для DLX-алгоритма (если инвертировать значения – пустое сделать 1, непустое – 0).
    возможно, если заюзать DLX – то будет быстро найдено множество решений, из которых можно выбрать подходящее.

  3. 6
    Леонид Максимов ответил:

    это жадный алгоритм, не всегда приводящий к оптимальному решению.

  4. 5
    Павел Тотолин ответил:

    >но количество строк и столбцов должно быть не меньше некоторого
    >заранее заданного значения

    Татьяна, а Вы не могли бы описать конкретные данные по ограничению.. Тоесть это ограничение произвольно ? Да и это ограничение распространяется одинаково на строки и на столбцы тоесть NxN или для строк одно, для столбцов другое, тоесть NxM. м ? )

    Задачка интересна ) Я кстати пока не понимаю почему
    "Алгоритм «вычёркивать те строки/столбцы, где число ЗАПОЛНЕННЫХ элементов МИНИМАЛЬНО» не является оптимальным." Ну я особо не исследовал вообщем-то.. )

  5. 4
    Татьяна Бойцова ответил:

    в виду своего нематематического образования ушла читать про то, что такое теория графов :) )

  6. 3
    Александр Lert ответил:

    Если сделать из матрицы такой граф: вершинами будут строки и столбцы матрицы, а ребрами – пропуски в матрице, то задача превратится в нахождение вершинного покрытия на графе. Это, как известно, NP-полная задача.

    То есть, по-видимому, ваша задача также NP-полная (правда, строго доказывать эквивалентность задач мне лень, но так вроде похоже). Следовательно, другого решения, кроме перебора с какими-нибудь оптимизациями и отсечениями придумать не получится :(

  7. 2
    Владимир Шакшин ответил:

    Не совсем уверен, что мыслю правильно, но есть такой вариант:
    по сути – решение ищется полным перебором, только в тело этого перебора добавляется некоторое условие оптимальности, которое резко сократит количество переборов.

    Такой подход часто используется при решении задач в теории графов.

    (редактировано)
    да и в нем нужно будет использовать рекурсию.

  8. 1
    Владимир Шакшин ответил:

    Если такой вариант устроит, пишите в личку.

Клуб программистов работает уже ой-ой-ой сколько, а если поточнее, то с 2007 года.