ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Max Alekseyev                        2:5015/60      23 Oct 2002  13:57:20
 To : Rustam Ramazanov
 Subject : Hайти покрытие столбцов строками
 -------------------------------------------------------------------------------- 
 

 
 Replying to a message of Rustam Ramazanov to Eugeny Tertishny:
 
  ET>> Есть матрица 16х14, несимметричная. Заполненная
  ET>> нулями и единицами. Hеобходимо
  ET>> найти минимальное количество строк, таких чтобы
  ET>> хоть в одном столбце была 1.
  ET>> Считается, что такие строки в любом случае есть
  RR> Упрощает жизнь, но не является решающим фактором.
 
  ET>> Хочется сделать не используя пер**ор. 
  RR> А чем перебор плох? К тому же все перебирать не надо.
  RR> Можно сделать следующее:
  RR> 1. Берем строку в которой максимальное число единиц.
  RR> Запомним столбцы в которых стоят единицы.
  RR> 2. В оставшихся строках в запомненных столбцах ставим 0.
  RR> 3. Переходим в п.1. Работа алгоритма заканчивается либо если во всех 
  RR> строках остаются только нули, либо если перебрали все строки (это тот 
  RR> самый худший вариант).
 
 Эта эвристика не дает минимальное решение. Минимальное решение может не
 содержать строку, с максимальным числом единиц - например:
 
 111100
 000010
 000001
 001110
 110001
 
 Regards,      ш.ш
         Max    ~
 
 --- FleetStreet 1.27.3.8
  * Origin:  (2:5015/60)
 
 

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

Тема:    Автор:    Дата:    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