4551
правка
Поиск предков: различия между версиями
Материал из WEGA
м
→Применение
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) м (→Применение) |
||
| Строка 113: | Строка 113: | ||
== Применение == | == Применение == | ||
Возможно, наиболее важным применением задачи поиска предков является просмотр информации об IP-адресах. Эту задачу решают маршрутизаторы для каждого пакета в Интернете, когда выбирают, в какую подсеть направить пакет. Таким образом, это, вероятно, самая часто выполняемая алгоритмическая задача в мире. Формально это запрос о поиске в интервале, который эквивалентен поиску предка в статическом случае [ ]. Поскольку при решении этой задачи эффективность | Возможно, наиболее важным применением задачи поиска предков является просмотр информации об IP-адресах. Эту задачу решают маршрутизаторы для каждого пакета в Интернете, когда выбирают, в какую подсеть направить пакет. Таким образом, это, вероятно, самая часто выполняемая алгоритмическая задача в мире. Формально это ''запрос о поиске в интервале'', который эквивалентен поиску предка в статическом случае [9]. Поскольку при решении этой задачи эффективность исключительно важна, необходимо отметить, что самые быстро внедряемые программные решения [7] используют стратегии целочисленного поиска (не основанные на сравнении), как и предсказывают теоретические результаты. | ||
Кроме того, поиск предков широко используется в структурах данных при редукции задач к пространству рангов. Пусть имеется множество T. Часто требуется переразметить его в более простое | Кроме того, поиск предков широко используется в структурах данных при редукции задач к ''пространству рангов''. Пусть имеется множество T. Часто требуется переразметить его в более простое {1, ..., n} «пространство рангов», сохранив при этом отношения порядка. Если новые значения представляются динамически, возникает необходимость в запросе на поиск предка. Вот несколько наглядных примеров: | ||
• При запросах в ортогональном диапазоне поддерживается набор точек в | • При запросах в ортогональном диапазоне поддерживается набор точек в <math>U^d</math> и выполняются запросы на точки в некотором прямоугольнике <math>[a_1, b_1] \times \cdot \cdot \cdot \times [a_d, b_d]</math>. Хотя границы обычно растут экспоненциально с увеличением размерности, зависимость от совокупности можно факторизовать. Во время запроса сначала выполняются 2d запросов предков, преобразующих совокупность в <math>\{1, ..., n \}^d</math>. | ||
• Чтобы сделать структуры данных с указателями постоянными [8], исходящая ссылка заменяется вектором указателей, каждый из которых действителен в течение некоторого периода времени. Решение о том, по какой ссылке идти (учитывая время запроса), представляет собой задачу поиска предка. | • Чтобы сделать структуры данных с указателями постоянными [8], исходящая ссылка заменяется вектором указателей, каждый из которых действителен в течение некоторого периода времени. Решение о том, по какой ссылке идти (учитывая время запроса), представляет собой задачу поиска предка. | ||
Наконец, любопытно отметить, что нижние границы в задаче поиска предка оказываются применимы, путем редукции, ко всем описанным выше приложениям. Чтобы сделать такие редукции возможными, нижние границы на самом деле показаны для более слабой задачи поиска цвета предка. В этой задаче значения множества T окрашены в красный или синий цвет, и запрос должен найти только цвет предшественника. | Наконец, любопытно отметить, что нижние границы в задаче поиска предка оказываются применимы, путем редукции, ко всем описанным выше приложениям. Чтобы сделать такие редукции возможными, нижние границы на самом деле показаны для более слабой задачи ''поиска цвета предка''. В этой задаче значения множества T окрашены в красный или синий цвет, и запрос должен найти только цвет предшественника. | ||
== Открытые вопросы == | == Открытые вопросы == | ||
