В процессе разработки и анализе алгоритмов для комбинаторной оптимизации , параметрический поиск представляет собой метод , изобретенный Нимрод Мегиддо ( 1983 ) для преобразования алгоритма решения (делает это задача оптимизации имеет решение с качеством лучше , чем какой - то определенный порог?) В алгоритм оптимизации ( найти лучшее решение). Он часто используется для решения задач оптимизации в вычислительной геометрии .
Техника
Основная идея параметрического поиска состоит в моделировании алгоритма тестирования, который принимает на вход числовой параметр., как если бы он был запущен с (неизвестным) оптимальным значением решения как его вход. Предполагается, что этот алгоритм тестирования работает прерывисто, когда, и оперировать его параметром только путем простых сравнений с другими вычисленными значениями, или путем проверки знака полиномиальных функций низкой степени от. Чтобы смоделировать алгоритм, необходимо моделировать каждое из этих сравнений или тестов, даже еслимоделируемого алгоритма неизвестно. Чтобы моделировать каждое сравнение, параметрический поиск применяет второй алгоритм, алгоритм принятия решения , который принимает в качестве входных данных другой числовой параметр., и это определяет, будет ли выше, ниже или равно оптимальному значению решения .
Поскольку сам алгоритм решения обязательно ведет себя прерывисто при , этот же алгоритм можно использовать и в качестве алгоритма тестирования. Однако многие приложения используют другие алгоритмы тестирования (часто алгоритмы сортировки сравнения ). Расширенные версии метода параметрического поиска используют параллельный алгоритм в качестве алгоритма тестирования и группируют сравнения, которые необходимо моделировать, в пакеты, чтобы значительно сократить количество экземпляров алгоритма принятия решения.
Алгоритм последовательного тестирования
В самой базовой форме методики параметрического поиска и алгоритм тестирования, и алгоритмы принятия решений являются последовательными (непараллельными) алгоритмами, возможно, одними и теми же алгоритмами. Методика шаг за шагом моделирует алгоритм тестирования, так как он будет работать, когда в качестве параметра задано (неизвестное) оптимальное значение решения.. Когда моделирование достигает шага, на котором алгоритм тестирования сравнивает свой параметр на какой-то другой номер , он не может выполнить этот шаг путем численного сравнения, так как не знает, что является. Вместо этого он вызывает алгоритм принятия решения с параметром, и использует результат алгоритма принятия решения для определения результата сравнения. Таким образом, время моделирования в конечном итоге равно произведению времени алгоритмов тестирования и принятия решения. Поскольку предполагается, что алгоритм тестирования ведет себя прерывисто при оптимальном значении решения, его нельзя точно смоделировать, если одно из значений параметрапереданное в алгоритм решения фактически равно оптимальному значению решения. Когда это происходит, алгоритм решения может обнаружить равенство и сохранить оптимальное значение решения для последующего вывода. Если алгоритму тестирования необходимо знать знак многочлена в, это снова можно смоделировать, передав корни полинома алгоритму принятия решения, чтобы определить, является ли неизвестное значение решения одним из этих корней, или, если нет, то между какими двумя корнями оно лежит.
Пример, рассмотренный Мегиддо (1983) и ван Оострумом и Велткампом (2002), касается системы нечетного числа частиц, движущихся вправо с разными постоянными скоростями по одной и той же линии. Медиана частиц также будет иметь правое движение, но оно будет кусочно линейным, а не иметь постоянную скорость, потому что разные частицы будут медианой в разное время. Первоначально частицы и их медиана находятся слева от начала координат линии, а в конечном итоге они и их медиана будут все справа от начала координат. Проблема в том, чтобы вычислить времяпри котором медиана лежит точно в начале координат. Время линейный алгоритм решения легко определить: для любого времени, можно вычислить положение каждой частицы в момент времени и подсчитайте количество частиц по обе стороны от начала координат. Если слева частиц больше, чем справа, то, а если справа частиц больше, чем слева, то . Каждый шаг этого алгоритма принятия решения сравнивает входной параметр к моменту, когда одна из частиц пересекает начало координат.
Использование этого решающего алгоритма как в качестве алгоритма тестирования, так и в качестве решающего алгоритма параметрического поиска приводит к алгоритму нахождения оптимального времени в квадратичном полном времени. Чтобы смоделировать алгоритм принятия решения для параметра, моделирование должно определять для каждой частицы, наступает ли время ее пересечения до или после , и, следовательно, находится ли он слева или справа от начала координат во время . Отвечая на этот вопрос для отдельной частицы - сравнивая время пересечения частицы с неизвестным оптимальным временем пересечения- можно выполнить, запустив тот же алгоритм принятия решения, указав в качестве параметра время пересечения частицы. Таким образом, моделирование завершается запуском алгоритма принятия решения на каждом из моментов пересечения частиц, одно из которых должно быть оптимальным временем пересечения. Однократный запуск алгоритма принятия решения требует линейного времени, поэтому запуск его отдельно для каждого времени пересечения занимает квадратичное время.
Алгоритм параллельного тестирования
Как уже заметил Мегиддо (1983) , метод параметрического поиска можно существенно ускорить, заменив имитируемый алгоритм тестирования эффективным параллельным алгоритмом , например, в модели параллельных вычислений параллельной машины с произвольным доступом (PRAM), где набор процессоры работают синхронно с общей памятью , выполняя одну и ту же последовательность операций с разными адресами памяти. Если алгоритм тестирования представляет собой алгоритм PRAM, он использует процессоров и требует времени (это, шаги, на которых каждый процессор выполняет одну операцию), то каждый из его шагов может быть смоделирован с использованием алгоритма принятия решения для определения результатов не более чем числовые сравнения. Путем нахождения медианного или почти среднего значения в наборе сравнений, которые необходимо оценить, и передачи этого единственного значения в алгоритм принятия решения можно исключить половину или почти половину сравнений с помощью только одного вызова решения. алгоритм. Повторно уменьшая вдвое набор сравнений, требуемых для моделирования таким образом, до тех пор, пока не останется ни одного, можно смоделировать результаты численные сравнения с использованием только вызывает алгоритм решения. Таким образом, общее время параметрического поиска в этом случае становится равным (для самой симуляции) плюс время на вызовы алгоритма решения (для партии сравнений, взятие звонков за пакет). Часто для задачи, которая может быть решена таким образом, произведение процессора времени алгоритма PRAM сравнимо со временем для алгоритма последовательного решения, а параллельное время является полилогарифмическим , что приводит к общему времени для параметрического поиска, которое медленнее алгоритма принятия решения только на полилогарифмический фактор.
В случае примера задачи нахождения времени пересечения медианы При перемещении частиц алгоритм последовательного тестирования может быть заменен алгоритмом параллельной сортировки , который сортирует положения частиц в момент времени, заданный параметром алгоритма, а затем использует отсортированный порядок для определения медианной частицы и определения знака ее положения. Лучший выбор для этого алгоритма ( в соответствии с его теоретическим анализом, если не на практике) является сортировка сеть из Ajtai , Комлоша и Семереди ( 1983 ). Это можно интерпретировать как алгоритм PRAM, в котором число процессоров пропорционально длине ввода , а количество параллельных шагов - логарифмическое. Таким образом, последовательное моделирование этого алгоритма требует времени для самой симуляции вместе с партии сравнений, каждое из которых может обрабатываться вызывает алгоритм решения с линейным временем. Объединение этих временных рамок даетобщее время параметрического поиска. Это не оптимальное время для этой проблемы - ту же проблему можно решить быстрее, если учесть, что время пересечения медианы равно медиане времен пересечения частиц, - но тот же метод можно применить к другой, более сложной оптимизации. задач, и во многих случаях предоставляет самый быстрый из известных сильно полиномиальных алгоритмов для этих задач.
Из-за больших постоянных факторов, возникающих при анализе сети сортировки AKS, параметрический поиск с использованием этой сети в качестве алгоритма тестирования нецелесообразен. Вместо этого van Oostrum & Veltkamp (2002) предлагают использовать параллельную форму быстрой сортировки (алгоритм, который многократно разделяет входные данные на два подмножества, а затем рекурсивно сортирует каждое подмножество). В этом алгоритме этап разделения является массово параллельным (каждый входной элемент должен сравниваться с выбранным опорным элементом), и два рекурсивных вызова могут выполняться параллельно друг с другом. Результирующий параметрический алгоритм в худшем случае работает медленнее, чем алгоритм, основанный на сети сортировки AKS. Однако ван Оострум и Вельткамп утверждают, что если результаты прошлых алгоритмов принятия решений сохранены (так что только сравнения, не разрешенные этими результатами, приведут к дополнительным вызовам алгоритма принятия решений), и сравнительные значения, проверенные алгоритмом моделирования моделирования, будут достаточно равномерными. распределено, то по мере продвижения алгоритма количество неразрешенных сравнений, генерируемых на каждом временном шаге, будет небольшим. Основываясь на этом эвристическом анализе и на экспериментальных результатах с реализацией алгоритма, они утверждают, что алгоритм параметрического поиска на основе быстрой сортировки будет более практичным, чем можно было бы предположить при анализе наихудшего случая.
Десинхронизированная сортировка
Коул (1987) дополнительно оптимизировал метод параметрического поиска для случаев (таких как пример), в которых алгоритм тестирования представляет собой алгоритм сортировки сравнения. Для сети сортировки AKS и некоторых других алгоритмов сортировки, которые можно использовать вместо нее, Коул отмечает, что нет необходимости поддерживать синхронизацию моделируемых процессоров друг с другом: вместо этого можно позволить некоторым из них продвигаться дальше по алгоритму сортировки. в то время как другие ждут результатов своих сравнений. Основываясь на этом принципе, Коул модифицирует моделирование алгоритма сортировки таким образом, чтобы поддерживать набор неразрешенных имитированных сравнений, которые могут не все происходить из одного и того же параллельного временного шага алгоритма тестирования. Как и в синхронизированной параллельной версии параметрического поиска, можно разрешить половину этих сравнений, найдя среднее значение сравнения и вызвав алгоритм принятия решения по этому значению. Затем, вместо того, чтобы повторять эту процедуру деления пополам до тех пор, пока набор неразрешенных сравнений не станет пустым, Коул позволяет процессорам, которые ожидали разрешенных сравнений, продвигаться по моделированию до тех пор, пока они не достигнут другого сравнения, которое необходимо разрешить. Используя этот метод, Коул показывает, что алгоритм параметрического поиска, в котором алгоритм тестирования выполняет сортировку, может быть завершен с использованием только логарифмического числа вызовов алгоритма принятия решения вместовызовы, сделанные исходной версией параметрического поиска Мегиддо. Вместо использования сети сортировки AKS можно также комбинировать этот метод с алгоритмом параллельной сортировки слиянием Коула (1988) , что приводит к временным границам с меньшими постоянными факторами, которые, однако, все еще недостаточно малы, чтобы быть практичным. Подобное ускорение может быть получено для любой задачи, которая может быть вычислена в распределенной вычислительной сети ограниченной степени (как сеть сортировки AKS), либо с помощью техники Коула, либо с помощью связанной техники моделирования множественных вычислительных путей ( Fernández-Baca 2001 ). .
Гудрич и Псона (2013) сочетают теоретические усовершенствования Коула с практическими ускорениями ван Оострума и Вельткампа (2002) . Вместо использования параллельной быстрой сортировки, как это делали ван Оострум и Вельткамп, они используют сортировку по бокам, вариант быстрой сортировки, разработанный Рейщуком (1985), в котором шаг разделения разбивает входные данные случайным образом наменьшие подзадачи вместо двух подзадач. Как и в методе Коула, они используют десинхронизированный параметрический поиск, в котором каждому отдельному потоку выполнения смоделированного алгоритма параллельной сортировки разрешается продвигаться до тех пор, пока ему не потребуется определить результат другого сравнения, и в котором количество неразрешенных сравнений уменьшается вдвое. путем нахождения среднего значения сравнения и вызова алгоритма принятия решения с этим значением. Как они показывают, результирующий алгоритм рандомизированного параметрического поиска делает только логарифмическое количество обращений к алгоритму принятия решения с высокой вероятностью, что соответствует теоретическому анализу Коула. Расширенная версия их статьи включает экспериментальные результаты реализации алгоритма, которые показывают, что общее время работы этого метода на нескольких задачах естественной геометрической оптимизации аналогично лучшей реализации синхронизированного параметрического поиска (метод быстрой сортировки van Oostrum и Veltkamp): немного быстрее по некоторым задачам и немного медленнее по другим. Однако количество обращений к алгоритму принятия решения значительно меньше, поэтому этот метод принесет больше преимуществ в приложениях параметрического поиска, где алгоритм принятия решения работает медленнее.
В примере задачи нахождения медианного времени пересечения точки как алгоритм Коула, так и алгоритм Гудрича и Псзоны получают время выполнения . В случае Goodrich и Pszona алгоритм рандомизирован и с высокой вероятностью получает эту временную границу.
Сравнение с бинарным поиском
Метод деления пополам (бинарный поиск) также может использоваться для преобразования решения в оптимизацию. В этом методе поддерживается интервал чисел, который, как известно, содержит оптимальное значение решения, и многократно сокращается интервал, вызывая алгоритм принятия решения по его медианному значению и сохраняя только половину интервала выше или ниже медианы, в зависимости от результата. звонка. Хотя этот метод может найти только численное приближение к оптимальному значению решения, он делает это в ряде вызовов алгоритма принятия решения, пропорционального количеству битов точности точности для этого приближения, что приводит к слабо полиномиальным алгоритмам.
Вместо этого, когда это применимо, параметрический поиск находит сильно полиномиальные алгоритмы, время работы которых зависит только от размера входных данных и не зависит от числовой точности. Однако параметрический поиск приводит к увеличению временной сложности (по сравнению с алгоритмом принятия решения), которая может быть больше логарифмической. Поскольку они являются скорее сильно, чем слабо полиномиальными, алгоритмы, основанные на параметрическом поиске, более удовлетворительны с теоретической точки зрения. На практике двоичный поиск выполняется быстро и часто намного проще в реализации, поэтому необходимы усилия по разработке алгоритмов , чтобы сделать параметрический поиск практичным. Тем не менее, ван Оострум и Велткамп (2002) пишут, что «хотя простой подход двоичного поиска часто пропагандируется как практическая замена параметрическому поиску, он уступает нашему алгоритму [параметрического поиска]» в экспериментальных сравнениях, которые они выполняли.
Приложения
Параметрический поиск применялся при разработке эффективных алгоритмов для задач оптимизации, особенно в вычислительной геометрии ( Agarwal, Sharir & Toledo, 1994 ). К ним относятся следующие:
- CenterPoint из множества точек в евклидовом пространстве является точка, что любое полупространство , содержащее центральную точку также содержит постоянную часть входных точек. Для-мерных пространств, оптимальная доля, которая может быть достигнута, всегда не меньше . Алгоритмы на основе параметрического поиска для построения двумерных центральных точек были позже улучшены до линейного времени с использованием других алгоритмических методов. Однако это улучшение не распространяется на более высокие измерения. В трех измерениях параметрический поиск можно использовать для поиска центральных точек во времени.( Коул, 1987 ).
- Параметрический поиск может быть использован в качестве основы для временной алгоритм для оценки Тейла – Сена , метод надежной статистики для подгонки линии к набору точек, который гораздо менее чувствителен к выбросам, чем простая линейная регрессия ( Cole et al. 1989 ).
- В компьютерной графике , то луч съемки задача (определение первого объекта в сцене , которая пересекается с заданной прямой видимости или светового луча) может быть решена путем объединения параметрического поиска со структурой данных для более простой задачи, тестирование ли любой из данный набор препятствий перекрывает данный луч ( Agarwal & Matoušek 1993 ).
- Самая большая проблема с палкой заключается в поиске самого длинного отрезка линии, полностью лежащего в пределах данного многоугольника . Это можно решить вовремя, для -сторонние полигоны и любые , используя алгоритм, основанный на параметрическом поиске ( Agarwal, Sharir & Toledo, 1994 ).
- Кольцевое пространство , который содержит заданный набор точек и имеет наималейшую возможную ширину (разница между внутренними и внешними радиусами) может быть использовано в качестве меры округлости множества точек. Опять же, эту проблему можно решить вовремя, для -сторонние полигоны и любые , используя алгоритм, основанный на параметрическом поиске ( Agarwal, Sharir & Toledo, 1994 ).
- Расстояние Хаусдорфа между сдвигами двух многоугольников, с выбранным сдвигом, чтобы минимизировать расстояние, можно найти с помощью параметрического поиска по времени., где а также - это количество сторон многоугольников ( Agarwal, Sharir & Toledo, 1994 ).
- Расстояние Фреше между двумя многоугольными цепями можно вычислить с помощью параметрического поиска по времени., где а также - это количество сегментов кривых ( Alt & Godau, 1995 ).
- Для точки на евклидовой плоскости, движущиеся с постоянной скоростью, время, в которое точки достигают наименьшего диаметра (и диаметр в это время), можно найти, используя вариацию техники Коула во времени.. Параметрический поиск также может использоваться для других аналогичных задач поиска времени, в которое некоторая мера набора движущихся точек получает свое минимальное значение, для мер, включающих размер минимального охватывающего шара или вес максимального остовного дерева ( Fernández- Baca 2001 ).
Рекомендации
- Агарвал, Панкадж К .; Matoušek, Йиржи (1993), "Луч съемки и поиск по параметрам", SIAM журнал по вычислениям , 22 (4): 794-806, CiteSeerX 10.1.1.298.6047 , DOI : 10,1137 / 0222051 , МР 1227762
- Агарвал, Панкадж К .; Шарир, Миха ; Толедо, Сиван (1994), "Применение параметрического поиска в геометрической оптимизации", журнал алгоритмов , 17 (3): 292-318, DOI : 10,1006 / jagm.1994.1038 , MR 1300253 , S2CID 380722.
- Аджтай, М .; Komlós, J .; Семереди, Е. (1983), "О О ( п войти п ) сортировки сеть", Труды 15 - го симпозиума ACM по теории вычислений (STOC '83) , стр 1-9,. DOI : 10.1145 / 800061,808726 , ISBN 0-89791-099-0, S2CID 15311122.
- Альт, Гельмут; Godau, Майкл (1995), "Вычисление расстояния между двумя Фреше ломаных" (PDF) , Международный журнал вычислительной геометрии и приложений , 5 (1-2): 75-91, DOI : 10,1142 / S0218195995000064 , МР 1331177.
- Коул, Ричард (1987), "Замедление сортировки сетей , чтобы получить быстрее , алгоритмы сортировки", Журнал ACM , 34 (1): 200-208, DOI : 10,1145 / 7531,7537 , MR 0882669 , S2CID 2301419.
- Коул, Ричард (1988), "Параллельная сортировка слиянием", SIAM журнал по вычислениям , 17 (4): 770-785, DOI : 10,1137 / 0217049 , MR 0953293 , S2CID 2416667.
- Коул, Ричард; Salowe, Jeffrey S .; Steiger, WL; Семереди, Эндре (1989), "Оптимальное время алгоритм для выбора наклона", SIAM журнал по вычислениям , 18 (4): 792-810, DOI : 10,1137 / 0218055 , МР 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.
- Reischuk, Рюдигер (1985), "Вероятностные параллельные алгоритмы сортировки и выбора", SIAM журнал по вычислениям , 14 (2): 396-409, DOI : 10,1137 / 0214030 , МР 0784745.
- ван Оострум, Рене; Велткамп, Ремко К. (2002), «Параметрический поиск стал практичным», Материалы восемнадцатого ежегодного симпозиума по вычислительной геометрии (SoCG '02) , Нью-Йорк, Нью-Йорк, США: ACM, стр. 1–9, doi : 10.1145 / 513400.513401 , ЛВП : 1874/18869 , ISBN 1-58113-504-1, S2CID 1551019.