Тема: Каков оптимальный алгоритм поиска седловой точки в матрице?

[Mrrl›]

Начало тут (http://tolkien.ru/forum/index.php?topic=22481.0).

Интересная задачка. Может ли быть больше одного такого элемента, если все числа в матрице различны? Каково минимальное число сравнений, за которые он находится? Понятно, что можно за O(m*n), но с каким коэффициентом?

               

               

[Арвинд›]

Mrrl, вопрос-то давным-давно изученный. Неужто на мехмате об этом не упоминалось? 

               

               

[Mrrl›]

Нет, в основном курсе этого не изучают. Поэтому и интересно.

Что приходит в голову - во-первых, минимум среди всех максимумов с последующей проверкой (m*(n-1)+2*(m-1) сравнений), но еще надо проверять, работает ли), и во-вторых, итерации - выбрать максимум в строке, минимум в полученном столбце, снова максимум в строке... - и какие возможны исходы? Если цикл - верно ли, что седловой точки нет?

               

               

[Арвинд›]

А, скажем, теорема Куна-Таккера? Тоже не было?

               

               

[Mrrl›]

Не помню. Названия теорем я никогда не запоминал, а поиск экстремума на ограниченной области нам рассказывали в рамках подготовки к ММО. Так что если в каком-нибудь курсе (оптимального управления, например) теорема пробегала, я мог ее не заметить, приняв за очевидный факт.

Итак, предположим, что седловая точка существует. Можно ли ее найти быстрее, чем за m*n операций, т.е. не просматривая всех элементов матрицы?

               

               

[Арвинд›]

Цитата из: Mrrl on 14-12-2005, 23:35:18
Так что если в каком-нибудь курсе (оптимального управления, например) теорема пробегала, я мог ее не заметить, приняв за очевидный факт.

Она, скорее всего, была в том же курсе, в котором было линейное программирование. Теорему о двойственности в ЛП можно получить как следствие из т. Куна-Таккера (последняя формулируется в непрерывных терминах. Возможно, словосочетание "множители Лагранжа" знакомо?). Собственно, к данной задаче это не очень относится, просто более общая теория.

Цитата из: Mrrl on 14-12-2005, 23:35:18
Итак, предположим, что седловая точка существует. Можно ли ее найти быстрее, чем за m*n операций, т.е. не просматривая всех элементов матрицы?

Можно заменить сравнение элементов умножением матрицы на вектора, но это, боюсь, замедление, а не ускорение...

               

               

[Mrrl›]

"Множители Лагранжа" были в матане на первом курсе - но относились к экстремуму на многообразии (т.е. с ограничениями типа равенств). "Условия дополняющей нежесткости" (или что-то в этом роде) - в оптимальном управлении. Линейного программирования запросто могло не быть вообще.

Умножение матрицы на вектор - это уже m*n операций, если ветор не разреженный. Вот только чем оно поможет?

               

               

[Арвинд›]

Цитата из: Mrrl on 15-12-2005, 00:02:51
"Условия дополняющей нежесткости" (или что-то в этом роде) - в оптимальном управлении.

Значит, и указанная теорема у вас была в ОУ. Исследования операций, я так понимаю, не было?
Цитата:
Линейного программирования запросто могло не быть вообще.

Типа, выведем сами, если понадобится? Впрочем, это действительно (мне кажется) не особо ценная теория в плане обогащения идеями других дисциплин. Просто частный случай, в котором найдены эффективные в вычислительном смысле алгоритмы типа симплекс-метода...

Цитата:
Умножение матрицы на вектор - это уже m*n операций, если ветор не разреженный. Вот только чем оно поможет?
Исходя из интерпретации задачи (поиск минимаксной стратегии из рассмотрений выигрышей обоих игроков). Но это, наверное, не дает оптимального по числу операций пути решения.

Попробую вспомнить или придумать, сейчас я не могу сказать, каким должен быть ответ о количестве операций.

               

               

[Mrrl›]

Цитата из: Арвинд on 15-12-2005, 00:14:52
Значит, и указанная теорема у вас была в ОУ.

Вовсе не обязательно. Функциями там не занимались, только функционалами.

Цитата:
Исследования операций, я так понимаю, не было?


Точно. Я и сейчас не знаю, что это такое.

Цитата:
Типа, выведем сами, если понадобится?


Выведем или прочитаем - в зависимости от характера. Мне больше нравится первый путь.



               

               

[Арвинд›]

Цитата из: Mrrl on 14-12-2005, 23:13:33
Может ли быть больше одного такого элемента, если все числа в матрице различны?

Вот это очень простой вопрос, кстати. Матрица может иметь несколько седловых точек, но их значения должны быть одинаковы. Следовательно, если все числа в матрице различны, то и седловой точки не более одной.

Равенство значений двух седловых точек можно доказать и без привлечения теории - просто взглянув на определение. Строчки и столбцы, содержащие эти точки, пересекутся еще в двух элементах. Пойдя от одной седловой точки к другой через первую точку пересечения, получим неравенство в одну сторону, пойдя через вторую - неравенство в другую стороны. Значит, эти точки равны между собой (и еще два элемента в матрице должны принимать то же значение).

               

               

[Mrrl›]

Да, очевидно. Там M[a,b]>=M[a,d]>=M[c,d]>=M[c,b]>=M[a,b], где (a,b) и (c,d) - седловые точки.

               

               

[Mrrl›]

Если значение в седловой точке известно (например, 0), то она ищется за m+n операций. А если значение другое, то можно тем же алгоритмом выяснить его знак. Казалось бы, (m+n)*log(mn) в кармане. Но поиск "делением пополам" сразу не проходит - делить нечего, числа в матрице могут быть распределены неравномерно.

               

               

[Арвинд›]

Цитата из: kidd 79ый on 15-12-2005, 12:12:52
Ребята, может, вас в ИР перенести?

Сумлеваюсь я... Здесь вопрос по определенной области знаний. Вот если на форуме начнут вникать в доказательство в. т. Ферма - это тоже в ИР должно будет пойти?

Цитата из: Mrrl on 14-12-2005, 23:18:29
Что приходит в голову - во-первых, минимум среди всех максимумов с последующей проверкой (m*(n-1)+2*(m-1) сравнений), но еще надо проверять, работает ли

Что-то я вчера это пропустил. Тут ничего проверять не надо - сработает.
Есть такая простая теоремка: седловая точка существует тогда и только тогда, когда минимакс равен максимину, и в этой точке они оба и достигаются (собственно, поэтому я теорию двойственности и упоминал).

Очень легко тем же способом, каким мы доказывали равенство седловых точек, доказать, к примеру, что если есть максимин и седловая точка, то значения их равны.

               

               

[Меанор›]

Цитата из: Mrrl on 15-12-2005, 12:36:26
Если значение в седловой точке известно (например, 0), то она ищется за m+n операций. А если значение другое, то можно тем же алгоритмом выяснить его знак. Казалось бы, (m+n)*log(mn) в кармане. Но поиск "делением пополам" сразу не проходит - делить нечего, числа в матрице могут быть распределены неравномерно.



Не убедительно. Я придумал, как за M+N найти "подозрительную" на седловую точку (если известно её значение). Однако алгоритм, который за это время находит действительно седловую точку или хотя бы проверяет её существование, мне не очевиден. Поделитесь, пожалуйста, если вы его знаете.
Правда, разумеется, если известно, что некоторое значение достигается в единственной точке, и эта точка - седловая, то действительно, её положение ищется за M+N.

               

               

[Арвинд›]

Цитата из: kidd 79ый on 15-12-2005, 14:49:09
киддать
 
Я согласен. Только ссылки надо будет в обеих темах - на начало и на конец.

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

Прежде всего, отметим следующее: в матрице m*n элементов, и в начале работы алгоритма у нас ровно столько претендентов на гордое имя "седловой точки". Алгоритм поиска проводит k сравнений. Можно сказать, что в среднем каждое сравнение будет вычеркивать из списка элементов матрицы mn/k элементов, так что в итоге вычеркнутся все или останутся только те, которые дадут ответ. Мерой хорошести алгоритма, значит, будет то количество элементов, которые можно будет вычеркнуть из избирательного бюллетеня на одном шаге.
Второе: можно попробовать поискать алгоритм, который будет работать не фиксированное число шагов. Оптимальность такого алгоритма будет оцениваться в среднем, на множестве всех матриц данной размерности.

Вот теперь пример: если мы ищем минимум в строке, то мы на каждом шаге вычеркиваем из списка кандидатов только один элемент - тот, который больше текущего минимума. За n-1 шаг мы вычеркнем n-1 элемент. Могу предложить подход (недоведенный еще до ума), который вычеркнет в среднем больше элементов.
Давай искать минимум не в строке, а на диагонали. Что это нам даст? Пусть у нас есть два неравных элемента M(i,k) < M(j,l). Из этого неравенства можно сразу сделать вывод, что строка i не может доминировать над столбцом l (все элементы строки i не могут быть не меньше всех элементов столбца l - у нас есть контрпример).
Значит, по этому сравнению можно вычеркнуть элемент M(i,l) (при обратном знаке неравенства мы вычеркнем элемент M(j,k) ).
Пока что это неинтересно - по одному сравнению вычеркнули один элемент. Рассмотрим, однако, следующий пример:

  о  о  о  о  1
  о  о  о  2  о
  о  о  3  о  о
  о  4  о  о  о
  5  о  о  о  о

Буквой "о" отмечены элементы, которые пока в сравнении не участвуют, отрезанную часть прямоугольной матрицы я не рисовал. Если мы пойдем по этой диагонали справа налево в поисках минимума, то мы будем по очереди сравнивать единицу с остальными элементами и вычеркивать в ее строке позиции, в которых точно нет седловых точек. После четырех шагов получим:

  x  x  x  x  1
  о  о  о  2  о
  о  о  3  о  о
  о  4  о  о  о
  5  о  о  о  о

Как видим, в этой ситуации поиск минимума в такой диагонали дал нам результат ничем не лучше и не хуже поиска минимума в первой строке.
Но! Если мы будм искать минимум в диагонали, начиная с нижнего угла, то, сравнивая 4 и 5 мы вычеркнем элемент в строке с четверкой, сравнивая 3 и 4 - элемент в строке с тройкой и столбце с четверкой плюс (мы ведь помним, что "4" у нас - текущий минимум, значит, все ранее просмотренное было больше, значит, оно больше и трех) элемент в строке с тройкой и столбцом с пятеркой. Дойдя до конца, получим:

  x  x  x  x  1
  x  x  x  2  о
  x  x  3  о  о
  x  4  о  о  о
  5  о  о  о  о

Этот пример показывает, что в хорошем случае за четыре сравнения мы можем вычеркнуть 10 элементов. Это была общая мысль, теперь нужно, во-первых, посчитать средную эффективность этого подхода, во-вторых, довести его до окончательного решения - как конкретно выбирать маршруты обхода матрицы и что сравнивать на последнем шаге (по аналогии с поиском максимума из всех промежуточных минимумов по строкам). Не знаю, получится ли что-то хорошее...

Вдогонку: метод поиска с.т., если известно её значение, попросту лишен смысла. Её и ищут для того, чтобы значение найти, а расположение в матрице - малоинтересно.

               

               

[Mrrl›]

Меанор,
 Если известно, что элемент со значением 0 единственный и является седловой точкой, то все понятно:
"если стоишь на положительном числе - иди вправо, если на отрицательном - вниз, дошел до нуля - стоп".
Или, если по-русски,
for(;; ){
  if(M[a,b]>0) b++;
  else if(M[a,b]<0) a++;
  else break;
}

Если седловая точка единственная (причем "строгая" - элемент меньше остальных в своей строке и больше остальных в столбце), но в матрице есть еще нули, то будем одновременно считать два пути: пара (a1,b1) при значении M[a1,b1]==0 будет сдвигаться вправо, а (a2,b2) (при M[a2,b2]==0) - вниз. Начнем с точки (0,0) и пойдем с одинаковой скоростью (заметим, что  a1+b1==a2+b2). Уткнувшись в очередной нуль, пути разойдутся, потом, возможно, сойдутся снова. Утверждение: в седловой точке пути сойдутся, а потом разойдутся окончательно (один пойдет вправо, другой вниз).
  Вот если в строке или столбце есть еще нули или если седловая точка не единственная - тогда не получается. Но давайте для начала считать, что все элементы матрицы различны и что седловая точка есть.

Арвинд,
смысл есть. Если у с.т. значение другое, то метод дает ее знак (больше она или меньше пробного значения). И анализируя пути для разных "пробных значений", можно попытаться уточнить интервал, в котором с.т. лежит, или выбрать очередное значение для деления этого интервала на две части.

               

               

[Меанор›]

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

По поводу того, что предложил Арвинд, замечу что если отсортировать предварительно столбцы по значениям диагональных элементов, то половина клеток отбросится за N*logN... Сможем ли мы в дальнейшем получить оценку порядка N*P(logN)?



               

               

[Mrrl›]

А "отсортировать предварительно столбцы по значениям диагональных элементов" - это как? Синхронно переставлять столбцы и строки, чтобы элементы оставались диагональными?



               

               

[Меанор›]

Да, кажется, мы можем это сделать.

               

               

[Арвинд›]

Собственно, необходимости реально сортировать столбцы нет. Если мы рассмотрим диагональные элементы
и за N*log(N) шагов выстроим их в возрастающую последовательность, то мы уже будем иметь отброшенной половину клеток (только эта половина будет не сверху диагонали, а разбросана по матрице).
Еще надо не забывать, что удастся убрать все-таки половину квадратной матрицы, а каков там еще прямоугольный кусок - зависит от разницы m и n.