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

При проектировании и анализе алгоритмов комбинаторной оптимизации параметрический поиск — это метод, изобретенный Нимродом Мегиддо  (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 т}$${\displaystyle т}$${\displaystyle т<т_{0}}$${\displaystyle т>т_{0}}$${\displaystyle т}$

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

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

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

В случае примера задачи нахождения времени пересечения медианы движущихся частиц последовательный тестовый алгоритм может быть заменен параллельным алгоритмом сортировки , который сортирует позиции частиц в момент времени, заданный параметром алгоритма, а затем использует отсортированный порядок для определения медианной частицы и нахождения знака ее позиции. Лучшим выбором для этого алгоритма (согласно его теоретическому анализу, если не на практике) является сортировочная сеть Ajtai , Komlós и Szemerédi  (1983). Это можно интерпретировать как алгоритм PRAM, в котором количество процессоров пропорционально длине входных данных , а количество параллельных шагов является логарифмическим. Таким образом, последовательное моделирование этого алгоритма требует времени для самого моделирования вместе с пакетами сравнений, каждое из которых может быть обработано вызовами алгоритма принятия решений с линейным временем. Объединение этих временных границ дает общее время для параметрического поиска. Это не оптимальное время для этой задачи — ту же задачу можно решить быстрее, заметив, что время пересечения медианы равно медиане времен пересечения частиц — но этот же метод можно применить к другим более сложным задачам оптимизации, и во многих случаях он обеспечивает самый быстрый из известных сильно полиномиальных алгоритмов для этих задач.${\displaystyle n}$${\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 и некоторых других алгоритмов сортировки, которые могут использоваться вместо нее, Коул замечает, что нет необходимости поддерживать синхронизацию моделируемых процессоров друг с другом: вместо этого можно позволить некоторым из них продвигаться дальше по алгоритму сортировки, в то время как другие будут ждать определения результатов их сравнений. Основываясь на этом принципе, Коул модифицирует моделирование алгоритма сортировки так, чтобы он поддерживал набор неразрешенных моделируемых сравнений, которые не все могут исходить из одного и того же параллельного временного шага тестового алгоритма. Как и в синхронизированной параллельной версии параметрического поиска, можно разрешить половину этих сравнений, найдя медианное значение сравнения и вызвав алгоритм принятия решения на этом значении. Затем, вместо того, чтобы повторять эту процедуру деления пополам до тех пор, пока коллекция неразрешенных сравнений не станет пустой, Коул позволяет процессорам, ожидавшим разрешенных сравнений, продвигаться по моделированию, пока они не достигнут другого сравнения, которое должно быть решено. Используя этот метод, Коул показывает, что параметрический алгоритм поиска, в котором тестовый алгоритм сортирует, может быть завершен с использованием только логарифмического числа вызовов алгоритма принятия решений вместо вызовов, сделанных оригинальной версией параметрического поиска Мегиддо. Вместо использования сортировочной сети AKS, также можно объединить эту технику с параллельным алгоритмом сортировки слиянием Коула (1988), что приводит к временным ограничениям с меньшими постоянными множителями, которые, однако, все еще недостаточно малы, чтобы быть практичными. Аналогичное ускорение может быть получено для любой задачи, которая может быть вычислена на распределенной вычислительной сети ограниченной степени (как сортировочная сеть AKS), либо с помощью техники Коула, либо с помощью связанной техники моделирования нескольких путей вычисления (Fernández-Baca 2001).${\displaystyle O(\log ^{2}n)}$

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

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

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

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

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

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

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

• Агарвал, Панкай К.; Матоушек , Йиржи (1993), «Лучевое зондирование и параметрический поиск», SIAM Journal on Computing , 22 (4): 794–806, CiteSeerX  10.1.1.298.6047 , doi :10.1137/0222051, MR  1227762
• Агарвал, Панкадж К.; Шарир , Миха ; Толедо, Сиван (1994), «Применение параметрического поиска в геометрической оптимизации», Журнал алгоритмов , 17 (3): 292–318, doi : 10.1006/jagm.1994.1038 , MR  1300253, S2CID  380722.
• Ajtai, M .; Komlós, J .; Szemerédi, E. (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, ISBN 0-89791-973-4.
• Коул, Ричард (1987), «Замедление сортировочных сетей для получения более быстрых алгоритмов сортировки», Журнал 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.
• Goodrich, Michael T .; Pszona, Paweł (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.