ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Oleg Polubasoff                      2:5020/400     26 Nov 2001  02:16:49
 To : Max Alekseyev
 Subject : подматрица?
 -------------------------------------------------------------------------------- 
 

     Привет, Макс!
 
 24.11.01  6:23, Max Alekseyev писал:
 
 MA> Даны квадратные матрицы A размером nxn и B размером mxm. n>m
 MA> Hужно определить можно ли получить матрицу B из матрицы A
 MA> *вычеркиванием* и *перестановкой* строк и столбцов?
 MA> Hасколько быстро это можно сделать?
 
     1. Если под *вычеркиванием* строк и столбцов подразумевается
 одновременное вычёркивание i-й строки и i-го столбца, а под *перестановкой*
 строк и столбцов подразумевается одновременная перестановка строк i и j и
 столбцов i и j, то при n>m задача NP-полна.
     Доказательство просто. С одной стороны, задача не проще задачи поиска в
 одном графе подграфа, изоморфного второму графу (просто в качестве матриц
 рассмотрим матрицы смежности этих графов), а с другой стороны, имеется
 очевидный недетерминированный полиномиальный алгоритм.
     Hесмотря на NP-полноту, на практике задача обычно решается довольно
 быстро, так как перебор имеет очень сильные отсечения.
     При n=m NP-полнота задачи пока не доказана, открытая проблема.
 
     2. Если же под *вычеркиванием* и *перестановкой* строк и столбцов
 подразумевается их независимое вычёркивание и перестановка, то задача,
 по-видимому, гораздо проще и может оказаться полиномиальной.
     Первым делом очень полезно с помощью перестановок строк и столбцов
 привести матрицу В к какому-нибудь стандартному виду - удостоверению.
 Hапример, к минимальному лексикографически, если рассматривать
 последовательность элементов в каком-нибудь порядке. Потом можно искать
 соответствующий блок в матрице A.
     Hасколько я знаю, такая задача в литературе не рассматривалась. Может
 быть, по причине её простоты.
     Так как ты пишешь про квадратные матрицы, то, видимо, имеешь в виду
 первый вариант.
 
     С уважением, Олег Полубасов.
 
 --- ifmail v.2.15dev5
  * Origin: Fidolook Express http://fidolook.da.ru (2:5020/400)
 
 

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

Тема:    Автор:    Дата:    подматрица?   Max Alekseyev   24 Nov 2001 07:23:48   подматрица?   Oleg Polubasoff   26 Nov 2001 02:16:49