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

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

Техника

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

метод рандомизированной оптимизации ( Chan 1998 Когда речь идет только об ожидаемой производительности, вместо параметрического поиска можно использовать ). Этот метод требует лишь постоянного увеличения временной сложности, но при этом дает строго полиномиальный алгоритм.

Приложения

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

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

Ссылки

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