Нужен алгоритм.
Вход — двухмерный массив точек.
Выход — порядок обхода этих точек, исходя из следующих критериев:
Минимальное расстояние. Под "расстоянием" имеется в виду "манхэттенское расстояние", т.е. dist (x, y, x1, y1) = abs(x — x1) + abs (y — y1). Ещё лучше, если расстояние по у будет в 2 (например) раза больше реального, или, в общем виде, dist (x, y, x1, y1) = M * abs(x — x1) + N * abs (y — y1).
Строго горизонтальное или строго вертикальное направление является приоритетным, сохраняя приоритет M:N.
Стараться избегать возвращения в точку, возле которой уже были после большого кол-ва шагов. (Это требование весьма низкоприоритетно и вытекает из того, что точность девайса не бесконечна и может быть погрешность, которая будет особенно заметна на замкнутых фигурах).
Самое непонятное тут, как изначально организовать точки. Если какой-нибудь алгоритм (Форда, если не ошибаюсь) из теории графов для нахождения минимальных расстояний между всеми точками, то ему нужно O(n^3), а при входе O(10^5) это очень дорого, но в крайнем случае, подойдёт. Кроме того, как эффективно построить граф из массива точек.
Какие-то идеи?
Заранее спасибо,
fAX.
...Complex problems have simple, easy-to-understand wrong answers...
(Grossman's Misquote of H.L.Mencken)
Здравствуйте fAX, Вы писали:
fAX>Нужен алгоритм. fAX>Вход — двухмерный массив точек. fAX>Выход — порядок обхода этих точек, исходя из следующих критериев: fAX>
fAX> Минимальное расстояние. Под "расстоянием" имеется в виду "манхэттенское расстояние", т.е. dist (x, y, x1, y1) = abs(x — x1) + abs (y — y1). Ещё лучше, если расстояние по у будет в 2 (например) раза больше реального, или, в общем виде, dist (x, y, x1, y1) = M * abs(x — x1) + N * abs (y — y1). fAX> Строго горизонтальное или строго вертикальное направление является приоритетным, сохраняя приоритет M:N. fAX> Стараться избегать возвращения в точку, возле которой уже были после большого кол-ва шагов. (Это требование весьма низкоприоритетно и вытекает из того, что точность девайса не бесконечна и может быть погрешность, которая будет особенно заметна на замкнутых фигурах). fAX>
fAX>Самое непонятное тут, как изначально организовать точки. Если какой-нибудь алгоритм (Форда, если не ошибаюсь) из теории графов для нахождения минимальных расстояний между всеми точками, то ему нужно O(n^3), а при входе O(10^5) это очень дорого, но в крайнем случае, подойдёт. Кроме того, как эффективно построить граф из массива точек.
fAX>Какие-то идеи?
fAX>Заранее спасибо, fAX>fAX.
Очень похоже на задачу коммивояжера. Для решения этой задачи используется симплекс-метод.
Алгоритм Форда же предназначен для поиска кратчайших путей между всеми вершинами графа. Причем эти не обязательно проходят через все вершины.
Или я неправильно понял постановку?
Здравствуйте Bell, Вы писали:
fAX>>Самое непонятное тут, как изначально организовать точки. Если какой-нибудь алгоритм (Форда, если не ошибаюсь) из теории графов для нахождения минимальных расстояний между всеми точками, то ему нужно O(n^3), а при входе O(10^5) это очень дорого, но в крайнем случае, подойдёт. Кроме того, как эффективно построить граф из массива точек.
fAX>>Какие-то идеи?
fAX>>Заранее спасибо, fAX>>fAX.
B>Очень похоже на задачу коммивояжера. Для решения этой задачи используется симплекс-метод. B>Алгоритм Форда же предназначен для поиска кратчайших путей между всеми вершинами графа. Причем эти не обязательно проходят через все вершины. B>Или я неправильно понял постановку?
Утешили. . Она-то — NP-полная! Хотя и есть хорошие приближения. Вопрос тут и в том, насколько они хороши на входе 10^5+. Но основная проблема — построить граф, как я уже писал.
...Complex problems have simple, easy-to-understand wrong answers...
(Grossman's Misquote of H.L.Mencken)
Да! Про алгоритм Форда я сказал, т.к. будь в моём распоряжении матрица расстояний — дальше всё просто и понятно — путешествуй себе исходя из критериев. Оптимизация будет локальной — но всё же лучше, чем ничего. Но, к сожалению, такая матрица потребует 10^10 элементов.
...Complex problems have simple, easy-to-understand wrong answers...
(Grossman's Misquote of H.L.Mencken)
Здравствуйте fAX, Вы писали:
fAX>Нужен алгоритм. fAX>Вход — двухмерный массив точек. fAX>Выход — порядок обхода этих точек, исходя из следующих критериев: fAX>
fAX> Минимальное расстояние. Под "расстоянием" имеется в виду "манхэттенское расстояние", т.е. dist (x, y, x1, y1) = abs(x — x1) + abs (y — y1). Ещё лучше, если расстояние по у будет в 2 (например) раза больше реального, или, в общем виде, dist (x, y, x1, y1) = M * abs(x — x1) + N * abs (y — y1). fAX> Строго горизонтальное или строго вертикальное направление является приоритетным, сохраняя приоритет M:N. fAX> Стараться избегать возвращения в точку, возле которой уже были после большого кол-ва шагов. (Это требование весьма низкоприоритетно и вытекает из того, что точность девайса не бесконечна и может быть погрешность, которая будет особенно заметна на замкнутых фигурах). fAX>
fAX>Самое непонятное тут, как изначально организовать точки. Если какой-нибудь алгоритм (Форда, если не ошибаюсь) из теории графов для нахождения минимальных расстояний между всеми точками, то ему нужно O(n^3), а при входе O(10^5) это очень дорого, но в крайнем случае, подойдёт. Кроме того, как эффективно построить граф из массива точек.
fAX>Какие-то идеи?
Точно говорю — должен быть человеческий алгоритим. Уж больно норма красивая. Так сходу в голову ничего не приходит, но попробую покумекать.
Чтобы обнадежить, могу рассказать байку про стандартную задачку, которую дают в НГУ математикам первого курса: дано множество точек на плоскости, надо построить окружность минимального радиуса, которая покрывает их все.
Классический подход: берем тройку точек, проводим окружность через них (очевидно, что искомая окружность будет проходить как минимум через три точки множества), проверяем, все ли внутри. полный перебор. Время работы ~N^4. Решения проверялисm на множествах в ~100 точек.
Мой друг, помогая человеку получить построил алгоритм, время работы которого ~N^N. Проверяли на множестве в 16000 точек.
Мораль: не все печальные теоремы бывают применимы в частном случае.В конкретной задаче могут найтись удачные ограничения, и решение будет намного эффективнее общего. fAX>Заранее спасибо, fAX>fAX.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте Sinclair, Вы писали:
fAX>>Какие-то идеи? S>Точно говорю — должен быть человеческий алгоритим. Уж больно норма красивая. Так сходу в голову ничего не приходит, но попробую покумекать. S>Чтобы обнадежить, могу рассказать байку про стандартную задачку, которую дают в НГУ математикам первого курса: дано множество точек на плоскости, надо построить окружность минимального радиуса, которая покрывает их все. S>Классический подход: берем тройку точек, проводим окружность через них (очевидно, что искомая окружность будет проходить как минимум через три точки множества), проверяем, все ли внутри. полный перебор. Время работы ~N^4. Решения проверялисm на множествах в ~100 точек. S>Мой друг, помогая человеку получить построил алгоритм, время работы которого ~N^N. Проверяли на множестве в 16000 точек. S>Мораль: не все печальные теоремы бывают применимы в частном случае.В конкретной задаче могут найтись удачные ограничения, и решение будет намного эффективнее общего. fAX>>Заранее спасибо, fAX>>fAX.
Дык надежда меня и питает .
А задача твоя, возможно и проще решается, т.к. convex hull (извини, по-русски не знаю) = O (N*LogN) + O(N^2) на нахождение наибольшего диаметра (можно, думается, и за N*LogN).
Hо всё же спасибо.
...Complex problems have simple, easy-to-understand wrong answers...
(Grossman's Misquote of H.L.Mencken)
Здравствуйте fAX, Вы писали:
fAX>Да! Про алгоритм Форда я сказал, т.к. будь в моём распоряжении матрица расстояний — дальше всё просто и понятно — путешествуй себе исходя из критериев. Оптимизация будет локальной — но всё же лучше, чем ничего. Но, к сожалению, такая матрица потребует 10^10 элементов.
Я так понял, требуется программа управления плоттером...
А так ли нужен наилучший способ (который получится решением задачи коммивояжера)?
Для такого большого числа точек можно предположить, что они сгруппированы в некие кластеры (расстояния внутри кластера существенно меньше, чем межкластерные).
В противном случае — когда точки расбросаны более-менее равномерно — сымитируем работу матричного принтера.
1. отсортируем точки по той координате, которая более "накладная" (скажем, по X)
2. нарежем пространство на полосы некоторой ширины по X
3. в пределах каждой полосы отсортируем точки по Y
В пределах полосы движемся от точки к точке. (преимущественное изменение координаты Y, незначительное Y)
Выбор направления ( Y++ | Y-- ) — либо волюнтаристский, либо решается задача динамического программирования.
Итак, вернемся к кластерам.
Сначала строится дерево минимальной длины, соединяющее все точки.
— берем две произвольных точки, соединяем их дугой (это будет зародыш дерева)
— берем очередную точку (A),
— — добавляем дугу к самой ближней из вершин дерева (B),
— — затем находим вторую по близости вершину (C)
— — находим самую длинную дугу на пути, соединяющем вершины B & C
— — если она длиннее, чем |AC|, то удаляем эту дугу и добавляем дуги AB и AC,
— — иначе добавляем только AB.
Далее выявляем кластеры (определяем некоторую критическую длину дуги дерева и считаем, что вершины, связанные дугами меньшей длины, принадлежат одному кластеру, а большей — разным).
Критерий может быть, например, таким: в одном кластере — не более N точек. Или диаметр кластера не более D.
Сгруппировав точки, в каждом кластере решаем задачу коммивояжера, а затем — решаем задачу уже между кластерами как неделимыми образованиями.
Здравствуйте Кодт, Вы писали:
К>Здравствуйте fAX, Вы писали:
fAX>>Да! Про алгоритм Форда я сказал, т.к. будь в моём распоряжении матрица расстояний — дальше всё просто и понятно — путешествуй себе исходя из критериев. Оптимизация будет локальной — но всё же лучше, чем ничего. Но, к сожалению, такая матрица потребует 10^10 элементов.
К>Я так понял, требуется программа управления плоттером...
Близко, очень близко — но с логической точки зрения (а ничего другого меня в данный момент не интересует ;) )
К>А так ли нужен наилучший способ (который получится решением задачи коммивояжера)?
Я и не сказал лучший — но достаточно хорошее приближение.
К>Для такого большого числа точек можно предположить, что они сгруппированы в некие кластеры (расстояния внутри кластера существенно меньше, чем межкластерные).
К>В противном случае — когда точки расбросаны более-менее равномерно — сымитируем работу матричного принтера. К>1. отсортируем точки по той координате, которая более "накладная" (скажем, по X) К>2. нарежем пространство на полосы некоторой ширины по X К>3. в пределах каждой полосы отсортируем точки по Y К>В пределах полосы движемся от точки к точке. (преимущественное изменение координаты Y, незначительное Y)
Это то, что есть сейчас. К сожалению обостряется п.3.
К>Выбор направления ( Y++ | Y-- ) — либо волюнтаристский, либо решается задача динамического программирования.
Извините, не понял...
К>Итак, вернемся к кластерам.
К>Сначала строится дерево минимальной длины, соединяющее все точки. К>- берем две произвольных точки, соединяем их дугой (это будет зародыш дерева) К>- берем очередную точку (A), К>- — добавляем дугу к самой ближней из вершин дерева (B), К>- — затем находим вторую по близости вершину (C) К>- — находим самую длинную дугу на пути, соединяющем вершины B & C К>- — если она длиннее, чем |AC|, то удаляем эту дугу и добавляем дуги AB и AC, К>- — иначе добавляем только AB.
К>Далее выявляем кластеры (определяем некоторую критическую длину дуги дерева и считаем, что вершины, связанные дугами меньшей длины, принадлежат одному кластеру, а большей — разным).
К>Критерий может быть, например, таким: в одном кластере — не более N точек. Или диаметр кластера не более D.
К>Сгруппировав точки, в каждом кластере решаем задачу коммивояжера, а затем — решаем задачу уже между кластерами как неделимыми образованиями.
Спасибо огромное. Это похоже на решение. Тоже склонялся к BSP, но так делить на кластеры я не думал. Ещё раз спасибо.
ЗЫ. А ни у кого нет алгоритма приближения коммивояжёра? Буду очень благодарен за информацию.
...Complex problems have simple, easy-to-understand wrong answers...
(Grossman's Misquote of H.L.Mencken)
К>>В противном случае — когда точки расбросаны более-менее равномерно — сымитируем работу матричного принтера. К>>1. отсортируем точки по той координате, которая более "накладная" (скажем, по X) К>>2. нарежем пространство на полосы некоторой ширины по X К>>3. в пределах каждой полосы отсортируем точки по Y К>>В пределах полосы движемся от точки к точке. (преимущественное изменение координаты Y, незначительное Y) fAX>Это то, что есть сейчас. К сожалению обостряется п.3.
К>>Выбор направления ( Y++ | Y-- ) — либо волюнтаристский, либо решается задача динамического программирования. fAX>Извините, не понял...
Смысл такой. Есть полосы (будем считать их неделимыми). У каждой из них есть два края
(Ymin, Ymax).
Нужно определить направление прохода каждой полосы.
Понятно, что суммарная длина проходов полос — величина постоянная и не зависит от выбора направлений. Следовательно, нужно минимизировать переходы от одной полосы к другой (следующей).
Пусть
Ai,Bi - концевые точки i-й полосы
Vi - направление прохода i-й полосы (от Ai к Bi либо наоборот). Принимает значения a (B->A) | b (A->B)
L[i,i+1] - длина перехода от i к i+1 полосе.
L[i,i+1] = f(Vi,Vi+1) - есть 4 варианта (AiAi+1, AiBi+1, BiAi+1, BiBi+1)
L[0,n] - суммарная длина переходов
L[0,n] = f(V0..Vn) - очевидно, с такой размерностью полный перебор делать бессмысленно.
Динамическое программирование - это принятие наилучшего решения на каждом шаге.
Как это сделать в данном случае?
Пусть мы нашли две последовательности V'0..i и V"0..i такие, что
V'i = "a" и V"i = "b",
а все остальные члены последовательностей дают минимальные L'[0..i] и L"[0..i].
Добавим следующий член (V'i+1, V"i+1).
Всего 4 варианта:
(1) V'0..i "a", L = L'[0..i] + L(AiBi+1) --> V'0..i+1
(2) V' "b", L' L(AiAi+1) V"
(3) V" "a", L" L(BiBi+1) V'
(4) V" "b" L" L(BiAi+1) V"
Из (1) и (3) выберем минимальный и получим новую последовательность V',
из (2) и (4) - получим V".
В конце концов у нас есть два оптимальных варианта, один (V') заканчивается на An, другой(V") - на Bn. Выберем более короткий.
Сложность алгоритма — O(N) (один проход) (не считая предварительной сортировки точек).
Затраты памяти — O(N) — два вектора V', V".
В процессе работы не нужно менять векторы местами — что из них закончилось на "a" — то и есть V'.
Затраты на вычисление длины — O(N) — используем 2 сумматора.
К>>Итак, вернемся к кластерам.
К>>Сначала строится дерево минимальной длины, соединяющее все точки. К>>- берем две произвольных точки, соединяем их дугой (это будет зародыш дерева) К>>- берем очередную точку (A), К>>- — добавляем дугу к самой ближней из вершин дерева (B), К>>- — затем находим вторую по близости вершину (C) К>>- — находим самую длинную дугу на пути, соединяющем вершины B & C К>>- — если она длиннее, чем |AC|, то удаляем эту дугу и добавляем дуги AB и AC, К>>- — иначе добавляем только AB.
К>>Далее выявляем кластеры (определяем некоторую критическую длину дуги дерева и считаем, что вершины, связанные дугами меньшей длины, принадлежат одному кластеру, а большей — разным).
К>>Критерий может быть, например, таким: в одном кластере — не более N точек. Или диаметр кластера не более D.
К>>Сгруппировав точки, в каждом кластере решаем задачу коммивояжера, а затем — решаем задачу уже между кластерами как неделимыми образованиями.
fAX>Спасибо огромное. Это похоже на решение. Тоже склонялся к BSP, но так делить на кластеры я не думал. Ещё раз спасибо.
Дерево здесь нужно только для эффективной группировки точек на кластеры (предполагая, что исходные данные неупорядочены).
Если они уже как-либо сгруппированы, то можно и по-другому.
Например, накладывается сетка с шагом, соизмеримым с ожидаемым диаметром кластера.
Точки группируются по ячейкам сетки.
Затем соседние заполненные ячейки анализируются на предмет объединения точек в кластеры.
Можно укрупнять сетку несколько раз.
fAX>ЗЫ. А ни у кого нет алгоритма приближения коммивояжёра? Буду очень благодарен за информацию.
Здравствуйте Кодт, Вы писали:
fAX>>Извините, не понял...
К>Смысл такой. Есть полосы (будем считать их неделимыми). У каждой из них есть два края К>(Ymin, Ymax). К>Нужно определить направление прохода каждой полосы. К>Понятно, что суммарная длина проходов полос — величина постоянная и не зависит от выбора направлений. Следовательно, нужно минимизировать переходы от одной полосы к другой (следующей).
К>Пусть К>
К>Ai,Bi - концевые точки i-й полосы
К>Vi - направление прохода i-й полосы (от Ai к Bi либо наоборот). Принимает значения a (B->A) | b (A->B)
К>L[i,i+1] - длина перехода от i к i+1 полосе.
К>L[i,i+1] = f(Vi,Vi+1) - есть 4 варианта (AiAi+1, AiBi+1, BiAi+1, BiBi+1)
К>L[0,n] - суммарная длина переходов
К>L[0,n] = f(V0..Vn) - очевидно, с такой размерностью полный перебор делать бессмысленно.
К>Динамическое программирование - это принятие наилучшего решения на каждом шаге.
К>Как это сделать в данном случае?
К>Пусть мы нашли две последовательности V'0..i и V"0..i такие, что
К>V'i = "a" и V"i = "b",
К>а все остальные члены последовательностей дают минимальные L'[0..i] и L"[0..i].
К>Добавим следующий член (V'i+1, V"i+1).
К>Всего 4 варианта:
К>(1) V'0..i "a", L = L'[0..i] + L(AiBi+1) --> V'0..i+1
К>(2) V' "b", L' L(AiAi+1) V"
К>(3) V" "a", L" L(BiBi+1) V'
К>(4) V" "b" L" L(BiAi+1) V"
К>Из (1) и (3) выберем минимальный и получим новую последовательность V',
К>из (2) и (4) - получим V".
К>В конце концов у нас есть два оптимальных варианта, один (V') заканчивается на An, другой(V") - на Bn. Выберем более короткий.
К>
К>Сложность алгоритма — O(N) (один проход) (не считая предварительной сортировки точек). К>Затраты памяти — O(N) — два вектора V', V". К>В процессе работы не нужно менять векторы местами — что из них закончилось на "a" — то и есть V'. К>Затраты на вычисление длины — O(N) — используем 2 сумматора.
Спасибо за разъяснение.
К>Дерево здесь нужно только для эффективной группировки точек на кластеры (предполагая, что исходные данные неупорядочены).
К>Если они уже как-либо сгруппированы, то можно и по-другому.
К>Например, накладывается сетка с шагом, соизмеримым с ожидаемым диаметром кластера. К>Точки группируются по ячейкам сетки. К>Затем соседние заполненные ячейки анализируются на предмет объединения точек в кластеры.
К>Можно укрупнять сетку несколько раз.
Да, но будет ли это эффективней? Ведь этот анализ намного сложнее. Можно, конечно, нечто среднее: в каждой ячейке построить дерево, а потом их смешивать и находить кластеры? (В дереве можно будет и по размеру, и по расстоянию разделять)
fAX>>ЗЫ. А ни у кого нет алгоритма приближения коммивояжёра? Буду очень благодарен за информацию.
...Complex problems have simple, easy-to-understand wrong answers...
(Grossman's Misquote of H.L.Mencken)
Здравствуйте fAX, Вы писали:
fAX>Здравствуйте Sinclair, Вы писали:
fAX>>>Какие-то идеи? fAX>Дык надежда меня и питает . fAX>А задача твоя, возможно и проще решается, т.к. convex hull (извини, по-русски не знаю) = O (N*LogN) + O(N^2) на нахождение наибольшего диаметра (можно, думается, и за N*LogN).
Упс! Сорри, очепятался — конечно N*N fAX>Hо всё же спасибо.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте Sinclair, Вы писали:
S>Упс! Сорри, очепятался — конечно N*N :)
Segodnja videl algoritm (determ N*LogN) i esh,e odin so srednim O(N) i worst case O(N^2). Poslednij pohozh na tvoj.
Sorry za translit
...Complex problems have simple, easy-to-understand wrong answers...
(Grossman's Misquote of H.L.Mencken)
Здравствуйте Sinclair, Вы писали:
S>Здравствуйте fAX, Вы писали:
fAX>>Здравствуйте Sinclair, Вы писали:
fAX>>>>Какие-то идеи? fAX>>Дык надежда меня и питает . fAX>>А задача твоя, возможно и проще решается, т.к. convex hull (извини, по-русски не знаю) = O (N*LogN) + O(N^2) на нахождение наибольшего диаметра (можно, думается, и за N*LogN). S>Упс! Сорри, очепятался — конечно N*N fAX>>Hо всё же спасибо.
convex hull всю жизнь по-русски называлось выпуклой оболочкой
Выражение O(N*LogN) + O(N^2) кажется как минимум странным,
поскольку оно есть просто O(N^2).
Диаметр множества точек несложно ищется за O(N*log N),
если предварительно построить выпуклую оболочку алгоритмом
Грэхема.
Кстати говоря, алгоритм, который в этом треде был жестоко
обозван "алгоритмом Форда", по-настоящему называется
алгоритмом Флойда.
B>Очень похоже на задачу коммивояжера. Для решения этой задачи используется симплекс-метод.
Интересное утверждение, но все же вряд ли коммивояжер решается
симплекс-методом, поскольку последний ничего кроме линейного
программирования не умеет, а последнее решается за
полиномиальное время (методом эллипсоидов, алгоритмом Кармаркара).
Здравствуйте mab, Вы писали:
fAX>>>Здравствуйте Sinclair, Вы писали:
fAX>>>>>Какие-то идеи? fAX>>>Дык надежда меня и питает ;-). fAX>>>А задача твоя, возможно и проще решается, т.к. convex hull (извини, по-русски не знаю) = O (N*LogN) + O(N^2) на нахождение наибольшего диаметра (можно, думается, и за N*LogN). S>>Упс! Сорри, очепятался — конечно N*N :) fAX>>>Hо всё же спасибо.
mab>convex hull всю жизнь по-русски называлось выпуклой оболочкой mab>Выражение O(N*LogN) + O(N^2) кажется как минимум странным, mab>поскольку оно есть просто O(N^2). O (N*LogN) — convex hull (eto ja znaju). A minimal`nyj diametr, kak ja i napisal, ochevidnym sposobom O(N^2), i pripisal "(можно, думается, и за N*LogN)". Takim obrazom "+" byl razdelitelem ;). V lubom sluchaet, mne prosto "ne ponravilos`" n^4, potomu i napisal. (Bol`she vsego mne ponravilos` N^N pri N=16000).
mab>Диаметр множества точек несложно ищется за O(N*log N), mab>если предварительно построить выпуклую оболочку алгоритмом mab>Грэхема.
Da, ja potom poiskal.
mab>Кстати говоря, алгоритм, который в этом треде был жестоко mab>обозван "алгоритмом Форда", по-настоящему называется mab>алгоритмом Флойда. Nadejus`, on ne obiditsja ;). U menja ochen` plohaja pamjat` na imena. Otchego chasto stradaju. :(
Sorry for translit.
...Complex problems have simple, easy-to-understand wrong answers...
(Grossman's Misquote of H.L.Mencken)
Здравствуйте mab, Вы писали:
B>>Очень похоже на задачу коммивояжера. Для решения этой задачи используется симплекс-метод.
mab>Интересное утверждение, но все же вряд ли коммивояжер решается mab>симплекс-методом, поскольку последний ничего кроме линейного mab>программирования не умеет,...
Вы absolutno pravy, t.k. линейное программирование в P, a коммивояжер в NP
mab>...а последнее решается за mab>полиномиальное время (методом эллипсоидов, алгоритмом Кармаркара).
Mozhno i linejno s konstantoj (v d izmerenijah):
1) Cd = 2^(2^d)
2) Cd = 3^(d^2).
...Complex problems have simple, easy-to-understand wrong answers...
(Grossman's Misquote of H.L.Mencken)
fAX>O (N*LogN) — convex hull (eto ja znaju). A minimal`nyj diametr, kak ja i napisal, ochevidnym sposobom O(N^2), i pripisal "(можно, думается, и за N*LogN)". Takim obrazom "+" byl razdelitelem . V lubom sluchaet, mne prosto "ne ponravilos`" n^4, potomu i napisal. (Bol`she vsego mne ponravilos` N^N pri N=16000).fAX>
Да, плюс-разделитель — это прикольно!
fAX>Nadejus`, on ne obiditsja . U menja ochen` plohaja pamjat` na imena. Otchego chasto stradaju.
Ну это, конечно, не важно. Просто есть ведь еще и алгоритм Форда-Беллмана,
только он ищет не попарные расстояния, а от фиксированной вершины.
Зато время его работы не O(N^3), а O(N*M), где M — число ребер, это
позволяет получить неслабый выигрыш на разреженных графах.
Да и вообще раз уж расстояния неотрициательны, то нужно использовать
Дейкстру (например, с фибоначчиевыми кучами, что дает O(M+N*logN))
. Она-то — NP-полная! Хотя и есть хорошие приближения. Вопрос тут и в том, насколько они хороши на входе 10^5+. Но основная проблема — построить граф, как я уже писал.
Перекуём баги на фичи!
