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

[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.

               

               

[Меанор›]

Разумеется. Перестановку мы сможем хранить отдельно. Более того, на каждом шаге мы и дальше сможем выбросить половину элементов любой квадратной подматрицы за K*logK, где K её сторона...

               

               

[Арвинд›]

С учетом предложения Меанора не ждать милостей от природы, а сортировать и гарантированно выкидывать половину квадрата (без диагонали), можно предложить второй шаг. Ясно, что на первом мы целиком вычеркнем из матрицы строку, в которой оказался минимум и столбец, в котором оказался максимум. На втором шаге естественно попробовать взять матрицу со стороной N-1, которая остается без указанных строки и столбца. В ней диагональ можно провести перпендикулярно проведенной ранее.
Вот для третьего шага надо будет как-то обобщить перпендикулярность, найти другой критерий максимизации числа невычеркнутых элементов. В частности, там, я думаю, будет уже использоваться не совсем диагональ - ведь мы нигде не использовали то, что эти элементы лежат на прямой. Это просто набор элементов, никакие два из которых не лежат в одной строке и в одном столбце. Такие наборы используются в определителе матрицы, между прочим...

               

               

[Mrrl›]

Есть C*n^{ln 3/ln 2} (для квадратных матриц).

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

При этом нам не нужно сортировать диагональные элементы - достаточно найти их медиану, а потом раскидать на группы "меньше медианы" - "медиана" - "больше медианы". Медиана ищется за гарантированно линейное число операций.

Кажется, число операций можно еще уменьшить, если делить диагональ на 3 неравные части (большую и две маленьких). Но там придется считать.

               

               

[Арвинд›]

Пока не понял деталей, на выходных попробую. Понятен принцип, интересный.

Думаю, желательно в этой теме доводить идеи, претендующие на оптимальность, до программного кода.

Цитата из: Mrrl on 19-12-2005, 14:21:27
Кажется, число операций можно еще уменьшить, если делить диагональ на 3 неравные части (большую и две маленьких). Но там придется считать.

В порядке полуоффтопика: замечательный источник идей - метод Лупанова. Стоит повспоминать...

               

               

[Mrrl›]

Уфф... n*sqrt(2*log₂n)*2^sqrt(2*log₂n)

Пусть матрица квадратная, n*n.
Для простоты введем переменную u=sqrt(2*log₂n), т.е.  n=2^{u^2/2}.
Определим n1=sqrt(2)*n/2^u=2^{(u-1)^2/2}. (округленное до целого).

Разобьем диагональные элементы матрицы на 3 группы - n1 маленьких, n-2*n1 средних, n1 больших. Отсортируем строки-столбцы матрицы, чтобы элементы M[i,n+1-i] для i из [1,n1] были "большими", для i из [n1+1,n-n1] - "средними", а для i из [n-n1+1,n] - "маленькими". Тогда седловая точка, если она есть, будет принадлежать одной из матриц M[1..n1,n-n1+1..n], M[1..n-n1,1..n-n1], M[n-n1+1..n,1..n1]. Размеры двух матриц равны n1, третьей - n-n1. Найдем (рекурсия) седловые точки этих матриц. Проверить, будет ли одна из них (и какая) седловой точкой всей матрицы, можно за 4*n-2*n1 сравнений. Если я нигде не ошибся, то число операций для этого алгоритма не превосходит C*u*2^u*n.

Следующий рубеж обороны - n*log(n)².

Написать код можно, но он уже становится довольно противным.

               

               

[Меанор›]

Как я понимаю, рекурсивный метод проиллюстрирован, собственно, вот этой картинкой:

(http://stratum.ac.ru/textbooks/kgrafic/additional/addit24/img01.gif)

Правда, зачем нужен выбор такого непростого n1? Вообще, мне кажетя при разбивке на неравные квадраты, мы получим только большее количество действий. Ведь мы будем проверять уже проверенные элементы. Сдаётся мне, у вас в счёте что-то неправильно.

               

               

[Арвинд›]

Цитата из: Mrrl on 19-12-2005, 18:31:27
Написать код можно, но он уже становится довольно противным.

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

               

               

[Меанор›]

Правда маленьких треугольничков будет порядка n. Да ещё по 2n действий на каждый, чтобы проверить его на "седловость". Таким образом, опять будет n^2 действий.

               

               

[Mrrl›]

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

               

               

[Меанор›]

Гм... Да? А если окажется, что не удаётся из трех точек выбрать одну, чтобы передать наверх? То есть, допустим, две оказались в текущем квадрате седловыми?

               

               

[Арвинд›]

Да, кстати, в моем изначальном предложении о том, что делать при равенстве элементов в матрице (даже не обязательно седловых), было скромно умолчено. Надо б в этом разобраться.

               

               

[Mrrl›]

При равенстве значений седловых точек проблемы не возникает - достаточно воспользоваться моим алгоритмом проверки значения (описан где-то в начале). Проблема будет, если среди диагональных элементов больше, чем n1 самых маленьких одинаковых. Надо подумать.



               

               

[Mrrl›]

Нет, все просто. Если все диагональные элементы в подматрице одинаковы, то и значение седловой точки в ней такое же, как эти элементы. Достаточно проверить, есть ли в этой подматрице такая седловая точка. Или не проверять - а отложить до проверки на матрице большего размера.

               

               

[Меанор›]

Не понял. Причем здесь равенство значений? Одна точка - седловая в некоторой подматрице. Вторая - тоже седловая. Пусть они в одном ряду находятся. (Иначе, будет уже четыре седовых.) Но одна из них может быть седловой во всей матрице, а вторая может не быть. Естественно могут быть и обе или ни одна из них. Как, простите, мы можем из рекурсии вернуть только одну (не более чем одну) подозрительную на "седловость" точку?

               

               

[Меанор›]

Цитата из: Mrrl on 19-12-2005, 20:11:54
Достаточно проверить, есть ли в этой подматрице такая седловая точка.


Я пока не видел описания алгоритма для этого, работающего быстрее, чем за M*N.

               

               

[Меанор›]

И в-третьих, объясните, что ваша неравноразмерная рекурсия с n1 даёт по сравнению с обычным, равноразмерным методом? Почему она будет работать быстрее? Пояните, пожалуйста, расчёты.

               

               

[Mrrl›]

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


int CheckVal(double [,]M,int m,int n,double a,out int iv,out int jv){
  iv=jv=0;
  int i1=0,j1=0;
  while(i1<m && j1<n){
    if(M[i1,j1]>a) j1++; else i1++;
  }
  if(i1==m) return 1;   // a>val
  int i2=0,j2=0;
  while(i2<m && j2<n){
    if(M[i2,j2]>=a) j2++; else i2++;
  }
  if(j2==n) return -1;   // a<val
  iv=i1; jv=j2;  // some saddle point
  return 0;
}


Алгоритм выдает -1,0 или 1, если a меньше, равно или больше значения седловой точки соответственно. Если выдано 0, то в параметрах iv, jv выдаются координаты потенциальной седловой точки (если хотя бы одна седловая точка со значением a есть, то гарантируется, что (iv,jv) - одна из них).

2. Действительно, можно ничего не проверять. Если в подматрице все диагональные элементы одинаковы, то их значение - единственный кандидат на значение седловой точки. Его и вернем.

3. "Обычный метод" - деление пополам или что-то еще?
Пусть f(n) - число операций, необходимое для поиска седловой точки. Пусть мы умеем искать медиану (и более широко - k-е по порядку значение из массива) + сортировать массив на "большие - меньшие" за C*n операций.
В случае деления пополам получаем:
f(n)=3*f(n/2)+n*(C+4)
(здесь 4*n - наихудшее время работы функции CheckVal).
Очевидно, что f(n)=D*n^(ln(3)/ln(2)), где D - некоторая константа.

Пусть рекурсия неравномерна. Для нее
f(n)=f(n-n1)+2*f(n1)+n*(2*C+4)
2*C понадобилось, поскольку диагональные элементы делятся на части дважды. Можно проверить, что если
n1=n/2^(sqrt(2*log(n)-1/2), то f(n)<D*n*sqrt(2*log(n))*2^sqrt(2*log(n))
(но это примерно страница выкладок). А это функция растет медленнее любой степенной (c показателем, большим 1).

В общем, дело в формуле f(n)=f(n-n1)+2*f(n1)+n*(2*C+4), точнее, в коэффициенте 2 перед f(n1). Поскольку f(n) выпукла вниз, для минимизации этого выражения требуется, чтобы выполнялось условие n1<n-n1. Точнее, f'(n-n1)=2*f'(n), а из-за медленного роста f(n)/n получаем, что n1 гораздо меньше n-n1.






               

               

[Меанор›]

Ну хорошо, а что нам даст поиск предполагаемого значения в седловой точке, если мы даже не будем уверены в том, что такая точка на матрице существует? Допустим, мы поличили: если на матрице есть седловая точка, то значение в ней A. Как нам её найти? Ведь, не любая точка со значением A является седловой.

               

               

[Mrrl›]

Так я же написал: если существует хотя бы одна седловая точка со значением a, то точка (iv,jv), выданная функцией CheckVal, гарантированно является одной из них. Но если мы не уверены в существовании, нам надо потратить еще m+n операций на проверку. Если окажется, что (iv,jv) - не седловая точка, значит, их вообще нет.

               

               

[Bindaree›]

Господа,

я вот это все не читала подробно, но у меня тот же вопрос, что и у Арвинда - есть МОР. Есть Кун с Такером. Есть определители и все прочие прелести.

Я собираюсь эту тему шлепнуть. Не вижу я в ней формата ИР. Можно? Конечно, не сейчас. Но потом,когда она вам всем надоест


С уважением,

Шаси

1. Вопрос решен. Можно писать дальше. Тема стерта в любом случае не будет, в худшем (маловероятном) случае - перенесена.
2. А что такое МОР?
Арвинд.

Эй, я не останавливала тему Я просто плотоядно на нее косилась  Уже больше не кошусь.Вообще в ее сторону не смотрю. 

МОР - метод оптимальных решений  раздел математики, посвященный как раз этой проблеме в частности, поиску эффективных решений для матриц и оптимизиционных задач

С уважением,

Шаси.

               

               

[Mrrl›]

Посмотрел я программу этого курса (МОР). Очень интересно. Но неужели там действительно рассматриваются эффективные (быстрее, чем за N^2) алгоритмы работы с матрицами? Задача ведь совершенно не практическая - какой смысл обрабатывать матрицу быстрее, чем ее можно построить?

               

               

[Bindaree›]

*нервно*

ничего не знаю про программу

               

               

[Арвинд›]

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

               

               

[Mrrl›]

Может быть, и там. Но по-моему, в численных методах дальше быстрого преобразования Фурье не идут. По той же причине - непрактично. Быстрое умножение матриц и полиномов, быстрая и сверхбыстрая длинная арифметика - компьютерная алгебра этим занимается наверняка, а кто еще?

               

               

[Арвинд›]

Да, больше вроде некому.


Вопрос по предложенному алгоритму (я так и не разглядел его в деталях): оценка-то какая в итоге?
Она лучше или хуже, чем сумма (по i от 1 до n)  i*log i ?
Потому что мне (очень смутно) кажется, что с оценкой в виде такой суммы алгоритм можно придумать.
Плюс еще линейная добавка, конечно.

               

               

[Mrrl›]

Оценка такая:

n*sqrt(2*log₂n)*2^sqrt(2*log₂n)

Это лучше, чем n^(1+eps), но хуже, чем n*log(n)^M
(при любых eps>0, M<infinity)

А sum(i*log(i)) - это больше, чем n². Не играет

               

               

[Арвинд›]

Цитата из: Mrrl on 27-12-2005, 20:05:14
А sum(i*log(i)) - это больше, чем n². Не играет
Логично, блин. Что-то я сильно тормознул.

Однако, оценка n*sqrt(2*log2n)*2^sqrt(2*log2n) приводилась вроде бы до того, как алгоритм был дополнен линейным поиском с.т. по значению (CheckVal)? Значит, теперь, если аккуратно считать, должно получиться больше.
Извиняюсь, что задаю вопрос, не разобравшись 

               

               

[Mrrl›]

Нет, CheckVal предусматривался с самого начала. Это не поиск, а проверка одного значения за O(n) операций. У алгоритма изменилась семантика некоторых шагов (работа со значением седловой точки вместо индексов), но сложность осталась той же.