ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Andrew Plyako                        2:5030/922.20  23 Oct 2002  12:57:02
 To : Eugeny Tertishny
 Subject : Hайти покpытие столбцов стpоками
 -------------------------------------------------------------------------------- 
 

 
  ET> Есть матpица 16х14, несимметpичная. Заполненная нyлями и единицами.
  ET> Hеобходимо найти минимальное количество стpок, таких чтобы хоть в
  ET> одном столбце была 1.
 
 Уточни, "хотя бы в одном", или "во всех столбцах"?
 Если "хотя бы в одном", то просто ищем первую не нулевую строчку. Ы?
  ET> Может есть какой-то мат. аппаpат для pешения данной задачи.
 
 Если я правильно понимаю твой вопрос, то это -- поиск минимальной клики в графе.
 NP-полная задача. Так что, формально, только перебор. Хотя, наверняка, есть
 какие-то эзотерические алгоритмы, которые будут хорошо работать на всех
 примерах, за исключением каких-то экзотических случаев.
 
 Andrew
 
 ---
  * Origin: Думать безОбразно -- безобрАзно!!! (2:5030/922.20)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

Тема:    Автор:    Дата:    Hайти покpытие столбцов стpоками   Eugeny Tertishny   23 Oct 2002 00:03:27   Re: Hайти покpытие столбцов стpоками   Rustam Ramazanov   23 Oct 2002 14:48:32   Hайти покрытие столбцов строками   Max Alekseyev   23 Oct 2002 13:57:20   Hайти покpытие столбцов стpоками   Andrew Plyako   23 Oct 2002 12:57:02   Re: Hайти покpытие столбцов стpоками   Vitaly Slobodskoy   24 Oct 2002 21:35:35   Hайти покpытие столбцов стpоками   Andrew Plyako   25 Oct 2002 05:45:42   Hайти покpытие столбцов стpоками   Eugeny Tertishny   24 Oct 2002 22:03:59   Re: Hайти покpытие столбцов стpоками   Igor Bury   25 Oct 2002 21:26:39   Re: Hайти покpытие столбцов стpоками   Igor Bury   26 Oct 2002 09:19:53