Параметрический поиск - Parametric search

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

Техника

Основная идея параметрического поиска - моделировать алгоритм тестирования который принимает в качестве входных данных числовой параметр ${\displaystyle X}$, как если бы он запускался с (неизвестным) оптимальным значением решения ${\displaystyle X^{*}}$ как его вход. Предполагается, что этот алгоритм проверки работает прерывисто когда ${\displaystyle X=X^{*}}$, и оперировать его параметром ${\displaystyle X}$ только простым сравнением ${\displaystyle X}$ с другими вычисленными значениями или путем проверки знака низкой степени полиномиальные функции из ${\displaystyle X}$. Чтобы смоделировать алгоритм, необходимо моделировать каждое из этих сравнений или тестов, даже если ${\displaystyle X}$ моделируемого алгоритма неизвестен. Для моделирования каждого сравнения параметрический поиск применяет второй алгоритм алгоритм решения, который принимает на вход еще один числовой параметр ${\displaystyle Y}$, и это определяет, будет ли ${\displaystyle Y}$ выше, ниже или равно оптимальному значению решения ${\displaystyle X^{*}}$.

Поскольку сам алгоритм решения обязательно ведет себя прерывисто при ${\displaystyle X^{*}}$, этот же алгоритм можно использовать и в качестве алгоритма тестирования. Однако многие приложения используют другие алгоритмы тестирования (часто сортировка сравнения алгоритмы). Расширенные версии метода параметрического поиска используют параллельный алгоритм в качестве алгоритма тестирования, и сгруппируйте сравнения, которые должны быть смоделированы, в пакеты, чтобы значительно сократить количество экземпляров алгоритма принятия решения.

Последовательный алгоритм тестирования

В самой базовой форме метода параметрического поиска и алгоритм тестирования, и алгоритмы принятия решений являются последовательными (непараллельными) алгоритмами, возможно, одинаковыми друг с другом. Методика шаг за шагом моделирует алгоритм тестирования, так как он будет работать, когда в качестве параметра задано (неизвестное) оптимальное значение решения. ${\displaystyle X}$. Когда симуляция достигает шага, на котором алгоритм тестирования сравнивает свой параметр ${\displaystyle X}$ на какой-то другой номер ${\displaystyle Y}$, он не может выполнить этот шаг путем численного сравнения, так как не знает, что ${\displaystyle X}$ является. Вместо этого он вызывает алгоритм принятия решения с параметром ${\displaystyle Y}$, и использует результат алгоритма принятия решения для определения результата сравнения. Таким образом, время моделирования в конечном итоге равно произведению времени алгоритмов тестирования и принятия решения. Поскольку предполагается, что алгоритм тестирования ведет себя прерывисто при оптимальном значении решения, его нельзя точно смоделировать, если одно из значений параметра ${\displaystyle Y}$ переданная в алгоритм решения фактически равна значению оптимального решения. Когда это происходит, алгоритм решения может обнаружить равенство и сохранить оптимальное значение решения для последующего вывода. Если алгоритму тестирования необходимо знать знак многочлена в ${\displaystyle X}$, это снова можно смоделировать, передав корни многочлена алгоритму принятия решения, чтобы определить, является ли неизвестное значение решения одним из этих корней, или, если нет, то между какими двумя корнями оно лежит.

Пример, рассмотренный как Мегиддо (1983) и ван Оострум и Вельткамп (2002) касается системы нечетного числа частиц, движущихся вправо с разными постоянными скоростями вдоль одной и той же линии. Медиана частиц также будет иметь правое движение, но оно будет кусочно-линейным, а не иметь постоянную скорость, потому что разные частицы будут медианой в разное время. Первоначально частицы и их медиана находятся слева от происхождение линии, и в конечном итоге они и их медиана будут справа от начала координат. Проблема в том, чтобы вычислить время ${\displaystyle t_{0}}$ при котором медиана лежит точно в начале координат. линейное время алгоритм решения легко определить: на любое время ${\displaystyle t}$, можно вычислить положение каждой частицы в момент времени ${\displaystyle t}$ и посчитаем количество частиц по обе стороны от начала координат. Если слева частиц больше, чем справа, то ${\displaystyle t<t_{0}}$, а если справа частиц больше, чем слева, то ${\displaystyle t>t_{0}}$. На каждом этапе этого алгоритма принятия решения сравнивается входной параметр ${\displaystyle t}$ к моменту, когда одна из частиц пересекает начало координат.

Использование этого решающего алгоритма как в качестве алгоритма тестирования, так и в качестве решающего алгоритма параметрического поиска приводит к алгоритму нахождения оптимального времени ${\displaystyle t_{0}}$ в квадратичном полном времени. Чтобы смоделировать алгоритм решения для параметра ${\displaystyle t_{0}}$, моделирование должно определять для каждой частицы, наступает ли время ее пересечения до или после ${\displaystyle t_{0}}$, и, следовательно, находится ли он слева или справа от начала координат во время ${\displaystyle t_{0}}$. Отвечая на этот вопрос для одной частицы - сравнивая время пересечения частицы с неизвестным оптимальным временем пересечения ${\displaystyle t_{0}}$ - можно выполнить, запустив тот же алгоритм решения со временем пересечения частицы в качестве его параметра. Таким образом, моделирование завершает выполнение алгоритма принятия решения для каждого из моментов пересечения частицы, одно из которых должно быть оптимальным временем пересечения. алгоритм решения один раз занимает линейное время, поэтому его выполнение отдельно для каждого момента пересечения занимает квадратичное время.

Алгоритм параллельного тестирования

Так как Мегиддо (1983) Как уже отмечалось, метод параметрического поиска можно существенно ускорить, заменив смоделированный алгоритм тестирования эффективным параллельный алгоритм, например, в параллельная машина с произвольным доступом (PRAM) модель параллельных вычислений, где набор процессоров работает синхронно на Общая память, все они выполняют одну и ту же последовательность операций с разными адресами памяти. Если алгоритм тестирования является PRAM, алгоритм использует ${\displaystyle P}$ процессоров и требует времени ${\displaystyle T}$ (это, ${\displaystyle T}$ шаги, на которых каждый процессор выполняет одну операцию), то каждый из его шагов может быть смоделирован с использованием алгоритма принятия решения для определения результатов не более чем ${\displaystyle P}$ числовые сравнения. Путем нахождения медианного или почти среднего значения в наборе сравнений, которые необходимо оценить, и передачи этого единственного значения в алгоритм принятия решения, можно исключить половину или почти половину сравнений с помощью только одного вызова решения. алгоритм. Повторно уменьшая вдвое набор сравнений, необходимых для моделирования таким образом, до тех пор, пока не останется ни одного, можно смоделировать результаты ${\displaystyle P}$ численные сравнения с использованием только ${\displaystyle O(\log P)}$ вызывает алгоритм решения. Таким образом, общее время параметрического поиска в этом случае становится равным ${\displaystyle O(PT)}$ (для самой симуляции) плюс время на ${\displaystyle O(T\log P)}$ вызовы алгоритма решения (для ${\displaystyle T}$ партии сравнений, взятие ${\displaystyle O(\log P)}$ звонков за пакет). Часто для проблемы, которая может быть решена таким образом, произведение процессора времени алгоритма PRAM сравнимо со временем для алгоритма последовательного решения, а параллельное время равно полилогарифмический, что приводит к общему времени для параметрического поиска, которое медленнее, чем алгоритм принятия решения, только на полилогарифмический коэффициент.

В случае примера задачи нахождения времени пересечения медианы ${\displaystyle n}$движущихся частиц алгоритм последовательного тестирования можно заменить параллельным сортировка алгоритм, который сортирует положения частиц в момент времени, заданный параметром алгоритма, а затем использует отсортированный порядок для определения медианной частицы и определения знака ее положения. лучший выбор для этого алгоритма (согласно его теоретическому анализу, если не на практике) сортировочная сеть из Аджтай, Komlós, и Семереди  (1983 ). Это можно интерпретировать как алгоритм PRAM, в котором число ${\displaystyle P}$ процессоров пропорционально длине ввода ${\displaystyle n}$, а количество параллельных шагов - логарифмическое. Таким образом, последовательное моделирование этого алгоритма требует времени ${\displaystyle O(n\log n)}$ для самой симуляции вместе с ${\displaystyle O(\log n)}$ пакеты сравнений, каждое из которых может обрабатываться ${\displaystyle O(\log n)}$ вызывает алгоритм принятия решения с линейным временем. Объединение этих временных рамок дает ${\displaystyle O(n\log ^{2}n)}$ общее время параметрического поиска. Это не оптимальное время для этой проблемы - ту же проблему можно решить быстрее, если учесть, что время пересечения медианы равно медиане времен пересечения частиц - но тот же метод можно применить к другой более сложной оптимизации. задач, и во многих случаях предоставляет самый быстрый из известных сильно полиномиальных алгоритмов для этих задач.

Из-за больших постоянных факторов, возникающих при анализе сортировочной сети AKS, параметрический поиск с использованием этой сети в качестве алгоритма тестирования нецелесообразен. Вместо, ван Оострум и Вельткамп (2002) предлагаю использовать параллельную форму быстрая сортировка (алгоритм, который многократно разделяет входные данные на два подмножества, а затем рекурсивно сортирует каждое подмножество). В этом алгоритме этап разделения является массово параллельным (каждый входной элемент следует сравнивать с выбранным опорным элементом), и два рекурсивных вызова могут выполняться параллельно друг другу. Результирующий параметрический алгоритм работает медленнее в худший случай чем алгоритм, основанный на сортировочной сети AKS. Однако ван Оострум и Вельткамп утверждают, что если результаты прошлых алгоритмов принятия решений сохранены (так что только сравнения, не разрешенные этими результатами, приведут к дополнительным вызовам алгоритма принятия решений), и значения сравнения, проверенные алгоритмом моделирования моделирования, будут достаточно равномерными. распределено, то по мере продвижения алгоритма количество неразрешенных сравнений, генерируемых на каждом временном шаге, будет небольшим. Основываясь на этом эвристическом анализе и на экспериментальных результатах с реализацией алгоритма, они утверждают, что алгоритм параметрического поиска, основанный на быстрой сортировке, будет более практичным, чем предполагает его анализ наихудшего случая.

Десинхронизированная сортировка

Коул (1987) дополнительно оптимизировал метод параметрического поиска для случаев (таких как пример), в которых алгоритм тестирования является алгоритмом сортировки сравнения. Для сети сортировки AKS и некоторых других алгоритмов сортировки, которые можно использовать вместо нее, Коул отмечает, что нет необходимости поддерживать синхронизацию моделируемых процессоров друг с другом: вместо этого можно позволить некоторым из них продвинуться дальше через алгоритм сортировки. в то время как другие ждут, пока будут определены результаты своих сравнений. Основываясь на этом принципе, Коул модифицирует моделирование алгоритма сортировки таким образом, что он поддерживает набор неразрешенных имитированных сравнений, которые могут не все происходить из одного и того же параллельного временного шага алгоритма тестирования. Как и в синхронизированной параллельной версии параметрического поиска, половину этих сравнений можно разрешить, найдя среднее значение сравнения и вызвав алгоритм принятия решения по этому значению. Затем, вместо того, чтобы повторять эту процедуру деления пополам до тех пор, пока набор неразрешенных сравнений не станет пустым, Коул позволяет процессорам, которые ожидали разрешенных сравнений, продвигаться по моделированию, пока они не достигнут другого сравнения, которое необходимо разрешить. Используя этот метод, Коул показывает, что алгоритм параметрического поиска, в котором алгоритм тестирования выполняет сортировку, может быть завершен с использованием только логарифмического числа вызовов алгоритма принятия решения вместо ${\displaystyle O(\log ^{2}n)}$ вызовы исходной версии параметрического поиска Megiddo. Вместо использования сортировочной сети AKS можно также комбинировать этот метод с параллельным Сортировка слиянием алгоритм Коул (1988), что приводит к временным рамкам с меньшими постоянными факторами, которые, однако, все еще недостаточно малы, чтобы быть практичными. Подобное ускорение может быть получено для любой задачи, которую можно вычислить в распределенной вычислительной сети с ограниченными возможностями. степень (как и сеть сортировки AKS), либо с помощью техники Коула, либо с помощью связанной техники моделирования нескольких путей вычислений (Фернандес-Бака 2001 ).

Гудрич и Псзона (2013) совместить теоретические усовершенствования Коула с практическими ускорениями ван Оострум и Вельткамп (2002). Вместо использования параллельной быстрой сортировки, как это сделали ван Оострум и Вельткамп, они используют сортировку по бокам, вариант быстрой сортировки, разработанный Рейщук (1985) в котором шаг разбиения разбивает вход случайным образом на ${\displaystyle O({\sqrt {n}})}$ меньшие подзадачи вместо двух подзадач. Как и в методе Коула, они используют десинхронизированный параметрический поиск, в котором каждому отдельному потоку выполнения смоделированного алгоритма параллельной сортировки разрешается прогрессировать до тех пор, пока ему не потребуется определить результат другого сравнения, и в котором количество неразрешенных сравнений уменьшается вдвое. путем нахождения среднего значения сравнения и вызова алгоритма принятия решения с этим значением. Как они показывают, результирующий алгоритм рандомизированного параметрического поиска делает только логарифмическое количество вызовов алгоритма принятия решения с высокой вероятностью, что соответствует теоретическому анализу Коула. Расширенная версия их статьи включает экспериментальные результаты реализации алгоритма, которые показывают, что общее время работы этого метода над несколькими задачами естественной геометрической оптимизации аналогично лучшей реализации синхронизированного параметрического поиска (метод быстрой сортировки van Oostrum и Veltkamp): немного быстрее по некоторым задачам и немного медленнее по другим. Однако количество обращений к алгоритму принятия решения значительно меньше, поэтому этот метод принесет больше преимуществ в приложениях параметрического поиска, где алгоритм принятия решения работает медленнее.

В примере задачи нахождения медианного времени пересечения точки и алгоритм Коула, и алгоритм Гудрича и Псзоны получают время выполнения ${\displaystyle O(n\log n)}$. В случае Goodrich и Pszona алгоритм рандомизирован и с высокой вероятностью получает эту временную границу.

Сравнение с бинарным поиском

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

Вместо этого, когда это применимо, параметрический поиск находит сильно полиномиальные алгоритмы, время работы которых зависит только от размера входных данных и не зависит от числовой точности. Однако параметрический поиск приводит к увеличению временной сложности (по сравнению с алгоритмом принятия решения), которая может быть больше логарифмической. Поскольку они являются скорее сильно, чем слабо полиномиальными, алгоритмы, основанные на параметрическом поиске, более удовлетворительны с теоретической точки зрения. На практике двоичный поиск выполняется быстро и часто намного проще в реализации, поэтому разработка алгоритмов необходимы усилия, чтобы сделать параметрический поиск практичным. Тем не менее, ван Оострум и Вельткамп (2002) напишите, что «хотя простой подход бинарного поиска часто пропагандируется как практическая замена параметрическому поиску, он уступает нашему алгоритму [параметрического поиска]» в проведенных ими экспериментальных сравнениях.

Приложения

В Оценка Тейла – Сена в сравнении с простая линейная регрессия

Параметрический поиск был применен при разработке эффективных алгоритмов для задач оптимизации, в частности, в вычислительная геометрия (Агарвал, Шарир и Толедо 1994 К ним относятся:

• А Центральная точка точки, установленной в Евклидово пространство такая точка, что любой полупространство содержащий центральную точку, также содержит постоянную долю входных точек. Для ${\displaystyle d}$-мерных пространств, оптимальная доля, которая может быть достигнута, всегда не меньше ${\displaystyle 1/(d+1)}$. Алгоритмы на основе параметрического поиска для построения двумерных центральных точек были позже улучшены до линейное время используя другие алгоритмические методы. Однако это улучшение не распространяется на более высокие измерения. В трех измерениях параметрический поиск может использоваться для поиска центральных точек во времени. ${\displaystyle O(n^{2}\log ^{4}n)}$ (Коул 1987 ).
• Параметрический поиск может быть использован как основа для ${\displaystyle O(n\log n)}$ временной алгоритм для Оценка Тейла – Сена, метод в надежная статистика для подгонки линии к набору точек, который гораздо менее чувствителен к выбросы чем простая линейная регрессия (Cole et al. 1989 г. ).
• В компьютерная графика, то луч стрельба Проблема (определение первого объекта в сцене, который пересекается заданной линией обзора или световым лучом) может быть решена путем объединения параметрического поиска со структурой данных для более простой задачи, проверки того, перекрывает ли какой-либо из заданного набора препятствий заданное луч (Агарвал и Матушек 1993 ).
• В самая большая проблема с палкой включает поиск самого длинного отрезка линии, полностью лежащего в заданном многоугольник. Это можно решить вовремя ${\displaystyle O(n^{8/5+\epsilon })}$, для ${\displaystyle n}$-сторонние полигоны и любые ${\displaystyle \epsilon >0}$, используя алгоритм, основанный на параметрическом поиске (Агарвал, Шарир и Толедо 1994 ).
• В кольцо который содержит заданный набор точек и имеет минимально возможную ширину (разницу между внутренним и внешним радиусами), может использоваться как мера округлость набора точек. Опять же, эту проблему можно решить вовремя ${\displaystyle O(n^{8/5+\epsilon })}$, для ${\displaystyle n}$-сторонние многоугольники и любые ${\displaystyle \epsilon >0}$, используя алгоритм, основанный на параметрическом поиске (Агарвал, Шарир и Толедо 1994 ).
• В Расстояние Хаусдорфа между переводит двух многоугольников с выбранным перемещением, чтобы минимизировать расстояние, можно найти с помощью параметрического поиска по времени ${\displaystyle O((mn)^{2}\log ^{3}mn)}$, где ${\displaystyle m}$ и ${\displaystyle n}$ - количество сторон многоугольника (Агарвал, Шарир и Толедо 1994 ).
• В Расстояние Фреше между двумя многоугольные цепи можно вычислить с помощью параметрического поиска по времени ${\displaystyle O(mn\log mn)}$, где ${\displaystyle m}$ и ${\displaystyle n}$ - номера отрезков кривых (Альт и Годау 1995 ).
• Для ${\displaystyle n}$ точки на евклидовой плоскости, движущиеся с постоянной скоростью, время, в которое точки получают наименьшее диаметр (и диаметр в то время) можно найти, используя вариацию техники Коула во времени ${\displaystyle O(n\log ^{2}n)}$. Параметрический поиск также может использоваться для других аналогичных задач по нахождению времени, в которое некоторая мера набора движущихся точек получает свое минимальное значение, для мер, включая размер минимальный закрывающий мяч или вес максимальное остовное дерево (Фернандес-Бака 2001 ).

использованная литература

• Агарвал, Панкадж К.; Матушек, Иржи (1993), «Лучевая съемка и параметрический поиск», SIAM Журнал по вычислениям, 22 (4): 794–806, CiteSeerX  10.1.1.298.6047, Дои:10.1137/0222051, Г-Н  1227762
• Агарвал, Панкадж К.; Шарир, Миха; Толедо, Сиван (1994), "Применение параметрического поиска в геометрической оптимизации", Журнал алгоритмов, 17 (3): 292–318, Дои:10.1006 / jagm.1994.1038, Г-Н  1300253, S2CID  380722.
• Айтай, М.; Комлос, Я.; Семереди, Э. (1983), "An О(п журнал п) сортировочная сеть », Материалы 15-го симпозиума ACM по теории вычислений (STOC '83), стр. 1–9, Дои:10.1145/800061.808726, ISBN  0-89791-099-0, S2CID  15311122.
• Альт, Гельмут; Годау, Майкл (1995), «Вычисление расстояния Фреше между двумя многоугольными кривыми» (PDF), Международный журнал вычислительной геометрии и приложений, 5 (1–2): 75–91, Дои:10.1142 / S0218195995000064, Г-Н  1331177.
• Коул, Ричард (1987), «Замедление сортировочных сетей для получения более быстрых алгоритмов сортировки», Журнал ACM, 34 (1): 200–208, Дои:10.1145/7531.7537, Г-Н  0882669, S2CID  2301419.
• Коул, Ричард (1988), «Сортировка с параллельным слиянием», SIAM Журнал по вычислениям, 17 (4): 770–785, Дои:10.1137/0217049, Г-Н  0953293, S2CID  2416667.
• Коул, Ричард; Salowe, Jeffrey S .; Steiger, W. L .; Семереди, Эндре (1989), "Оптимальный по времени алгоритм выбора уклона", SIAM Журнал по вычислениям, 18 (4): 792–810, Дои:10.1137/0218055, Г-Н  1004799.
• Фернандес-Бака, Д. (2001), "О нелинейном параметрическом поиске", Алгоритмика, 30 (1): 1–11, Дои:10.1007 / s00453-001-0001-2, Г-Н  1816864, S2CID  20320912.
• Гудрич, Майкл Т.; Пшона, Павел (2013), «Практика параметрического поиска Коула» (PDF), Proc. 25-я канадская конференция по вычислительной геометрии (CCCG 2013), arXiv:1306.3000, Bibcode:2013arXiv1306.3000G.
• Мегиддо, Нимрод (1983), «Применение алгоритмов параллельных вычислений при разработке последовательных алгоритмов», Журнал ACM, 30 (4): 852–865, Дои:10.1145/2157.322410, Г-Н  0819134, S2CID  2212007.
• Рейщук, Рюдигер (1985), "Вероятностные параллельные алгоритмы для сортировки и выбора", SIAM Журнал по вычислениям, 14 (2): 396–409, Дои:10.1137/0214030, Г-Н  0784745.
• ван Оострум, Рене; Вельткамп, Ремко К. (2002), «Параметрический поиск стал практичным», Материалы восемнадцатого ежегодного симпозиума по вычислительной геометрии (SoCG '02), Нью-Йорк, Нью-Йорк, США: ACM, стр. 1–9, Дои:10.1145/513400.513401, HDL:1874/18869, ISBN  1-58113-504-1, S2CID  1551019.