Найти покpытие столбцов стpоками

From

Andrew Plyako (2:5030/922.20)

To

Eugeny Tertishny

Date

2002-10-23T12:57:02Z

Area

RU.ALGORITHMS

Hello Eugeny.
23 Oct 02 00:03, you wrote to All:

 ET> Есть матpица 16х14, несимметpичная. Заполненная нyлями и единицами.
 ET> Необходимо найти минимальное количество стpок, таких чтобы хоть в
 ET> одном столбце была 1.
Уточни, "хотя бы в одном", или "во всех столбцах"?
Если "хотя бы в одном", то просто ищем первую не нулевую строчку. Ы?


 ET> Может есть какой-то мат. аппаpат для pешения данной задачи.
Если я правильно понимаю твой вопрос, то это -- поиск минимальной клики в графе. NP-полная задача. Так что, формально, только перебор. Хотя, наверняка, есть какие-то эзотерические алгоритмы, которые будут хорошо работать на всех примерах, за исключением каких-то экзотических случаев.

Andrew

---
 * Origin: Думать безОбразно -- безобрАзно!!! (2:5030/922.20)