Гибридный алгоритм - Hybrid algorithm
 | Эта статья не цитировать любой источники. (Май 2014 г.) (Узнайте, как и когда удалить этот шаблон сообщения) |
А гибридный алгоритм является алгоритм который объединяет два или несколько других алгоритмов, решающих одну и ту же проблему, либо выбирая один (в зависимости от данных), либо переключаясь между ними в ходе выполнения алгоритма. Обычно это делается для объединения желаемых функций каждого из них, чтобы общий алгоритм лучше, чем отдельные компоненты.
«Гибридный алгоритм» не относится к простому объединению нескольких алгоритмов для решения другой проблемы - многие алгоритмы можно рассматривать как комбинации более простых частей - а только к объединению алгоритмов, которые решают одну и ту же проблему, но отличаются другими характеристиками, в частности производительностью.
Примеры
В Информатика, гибридные алгоритмы очень распространены в оптимизированных реальных реализациях рекурсивные алгоритмы, особенно реализации из разделяй и властвуй или же уменьшаться и побеждать алгоритмы, в которых размер данных уменьшается по мере продвижения в рекурсии. В этом случае для общего подхода (для больших данных) используется один алгоритм, но в глубине рекурсии он переключается на другой алгоритм, который более эффективен для небольших данных. Типичный пример - в алгоритмы сортировки, где сортировка вставкой, которая неэффективна для больших данных, но очень эффективна для небольших данных (скажем, от пяти до десяти элементов), используется в качестве последнего шага после первичного применения другого алгоритма, такого как Сортировка слиянием или же быстрая сортировка. Сортировка слиянием и быстрая сортировка асимптотически оптимальны для больших данных, но накладные расходы становятся значительными, если применять их к небольшим данным, поэтому в конце рекурсии используется другой алгоритм. Высокооптимизированный гибридный алгоритм сортировки Тимсорт, который объединяет сортировку слиянием, сортировку вставкой, а также дополнительную логику (включая бинарный поиск ) в логике слияния.
Общая процедура для простого гибридного рекурсивного алгоритма: короткое замыкание базового корпуса, также известный как рекурсия на расстоянии вытянутой руки. В этом случае, приведет ли следующий шаг к базовому варианту, проверяется перед вызовом функции, избегая ненужного вызова функции. Например, в дереве вместо рекурсии к дочернему узлу с последующей проверкой, является ли он нулевым, проверяя нулевое значение перед рекурсивным выполнением. Это полезно для повышения эффективности, когда алгоритм обычно встречается с базовым случаем много раз, как во многих древовидных алгоритмах, но в остальном считается плохим стилем, особенно в академических кругах, из-за дополнительной сложности.
Другой пример гибридных алгоритмов по соображениям производительности: интросорт и интроселект, которые комбинируют один алгоритм для быстрой средней производительности и прибегают к другому алгоритму для обеспечения (асимптотически) оптимальной производительности в худшем случае. Introsort начинается с быстрая сортировка, но переключается на куча сортировки если быстрая сортировка не идет хорошо; аналогично интроселект начинается с быстрый выбор, но переключается на медиана медиан если быстрый выбор не работает должным образом.
Централизованный распределенные алгоритмы часто можно рассматривать как гибридные алгоритмы, состоящие из отдельного алгоритма (запускаемого на каждом распределенном процессоре) и алгоритма комбинирования (запускаемого на централизованном распределителе) - они соответствуют соответственно запуску всего алгоритма на одном процессоре или запуску всего вычисления на распределителе, комбинируя тривиальные результаты (одноэлементный набор данных от каждого процессора). Базовый пример этих алгоритмов: виды распределения, особенно используется для внешняя сортировка, которые разделяют данные на отдельные подмножества, сортируют подмножества, а затем объединяют подмножества в полностью отсортированные данные; примеры включают ведро сортировка и flashsort.
Однако в общем случае распределенные алгоритмы не обязательно должны быть гибридными, поскольку отдельные алгоритмы или алгоритмы объединения или связи могут решать разные проблемы. Например, в таких моделях, как Уменьшение карты, шаги Map и Reduce решают разные проблемы и объединяются для решения другой, третьей проблемы.