http://neerc.ifmo.ru/wiki/api.php?action=feedcontributions&user=93.175.2.28&feedformat=atomВикиконспекты - Вклад участника [ru]2024-03-29T12:46:46ZВклад участникаMediaWiki 1.30.0http://neerc.ifmo.ru/wiki/index.php?title=%D0%AD%D0%B2%D1%80%D0%B8%D1%81%D1%82%D0%B8%D0%BA%D0%B8_%D0%B4%D0%BB%D1%8F_%D0%BF%D0%BE%D0%B8%D1%81%D0%BA%D0%B0_%D0%BA%D1%80%D0%B0%D1%82%D1%87%D0%B0%D0%B9%D1%88%D0%B8%D1%85_%D0%BF%D1%83%D1%82%D0%B5%D0%B9&diff=66136Эвристики для поиска кратчайших путей2018-06-23T15:47:25Z<p>93.175.2.28: /* Двунаправленный поиск */</p>
<hr />
<div>== Проблема поиска кратчайшего пути ==<br />
{{Задача<br />
|definition = <br />
Дана сеть автомобильных дорог:<br />
* ориентированный граф <tex>G=(V,E)</tex>, где<br />
** <tex>V</tex> — множество перекрёстков,<br />
** <tex>E</tex> — множество дорог;<br />
* <tex>l(u,v) \geqslant 0</tex> — среднее время, которое занимает проезд по дороге,<br />
* <tex>|V|=n, |E|=m</tex>,<br />
* отправная точка — вершина <tex>s</tex>, пункт назначения — вершина <tex>t</tex><br />
Цель: найти кратчайший путь <tex> s \rightsquigarrow t</tex><br />
}}<br />
Количество перекрёстков и дорог может быть очень большим, тогда обычные алгоритмы поиска пути будут работать очень долго, поэтому попытаемся оптимизировать их для более быстрой работы.<br />
<br />
==Алгоритм Дейкстры==<br />
[[Алгоритм Дейкстры]]:<br />
* На каждом шаге выбирает из множества непросмотренных вершин вершину с наименьшим расстоянием до старта и релаксирует рёбра, исходящие из неё,<br />
* завершает свою работу, когда цель достигнута (или просмотрены все вершины).<br />
<br />
Скорость работы алгоритма Дейкстры сильно зависит от скорости операций с приоритетной очередью.<br />
<br />
Поскольку мы рассматриваем сеть автомобильных дорог, то <tex>m = O(n)</tex> (граф планарен почти везде).<br />
<br />
Для фибоначчиевых куч время работы алгоритма составляет <tex>O(n\log{n}+n)</tex>, для двоичных куч: <tex>O(n\log{n})</tex><br />
<br />
Но на практике чаще используются 2-, 4- и 8-ичные кучи: они более простые, оценка времени работы содержит меньшее количество скрытых констант.<br />
<br />
===Улучшения алгоритма Дейкстры===<br />
====Многоуровневые корзины (англ. ''multi-level buckets, MLB'')====<br />
<div >[[Файл:multilevel_buckets.jpg ]]</div><br />
<br />
{| class="wikitable" style="width:7cm; text-align: center" border=1 align="right"<br />
|+ Сравнение различных структур данных для поиска кратчайшего пути на карте Европы (CPU 2,4GHz, 16MB RAM)<br />
! Структура данных !! Время работы (сек)<br />
|- <br />
| Двоичная куча || 12,38<br />
|-<br />
| 4-куча || 11,53<br />
|-<br />
| 8-куча || 11,52<br />
|-<br />
| MLB || 9,36<br />
|-<br />
| MLB + калибровка || 8,04<br />
|-<br />
|}<br />
Подходит только графов с целочисленными рёбрами.<br />
* Будем складывать вершины в "корзины" <tex>B[i] = \{u \in B[i] : d(u)=i\}</tex>,<br />
* наша структура данных будет поддерживать индекс <tex>L = \{\forall i : i<L \Rightarrow B[i] = \emptyset\}</tex><br />
* на каждом шаге алгоритма, если <tex>B[L]</tex> пусто, то увеличим <tex>L</tex>, а иначе достанем одну вершину из <tex>B[L]</tex>,<br />
* при релаксации будем убирать вершину из исходной корзины и класть в корзину, соответствующую новому значению <tex>d(u)</tex>.<br />
<br />
Можно заметить, что при такой реализации, все операции с приоритетной очередью будут выполняться за <tex>O(1)</tex>. Тогда, для одноуровневой реализации время работы алгоритма Дейкстры можно оценить как <tex>O(m+nC)</tex>, где <tex>C</tex> — максимальная длина ребра в графе.<br />
<br />
При двухуровневой реализации будем поддерживать два уровня корзин: первый уровень будет соответствовать одноуровневой реализации, а корзины второго уровня будут содержать диапазон значений корзин первого уровня, которые в них входят. В этом случае, нам нужно поддерживать два индекса <tex>L_{top}</tex> и <tex>L_{bottom}</tex> для каждого из уровней соответственно.<br />
<br />
При такой реализации, время работы алгоритма Дейкстры можно оценить как <tex>O(m+n(1+ \sqrt{C}))</tex><br />
<br />
====Калибровка (англ. ''caliber'')====<br />
Введём величину <b>''калибр''</b> вершины <tex>c(v)</tex> — вес минимального ребра, входящего в <tex>v</tex> , или <tex>\infty</tex>, если в вершину не входит ни одно ребро. Будем говорить, что текущее значение <tex>d(v)</tex> точно, если оно равно длине пути <tex>s \rightsquigarrow v</tex>. <br />
{{Лемма<br />
|about = 1<br />
|statement = <br />
Предположим, что длины рёбер неотрицательны. Пусть <tex>\mu</tex> — минимальное из текущих значений <tex>d(v):v \in V</tex>. Тогда, если существует такая вершина <tex>u</tex>, что <tex>\mu + c(u) \geqslant d(u)</tex>, то текущее значение <tex>d(u)</tex> точно.<br />
}}<br />
Эта лемма позволяет нам смягчить правило выбора текущей вершины в алгоритме Дейкстры, при этом сохраняя инвариант (почти все вершины обрабатываются единожды).<br />
Калибровка использует Лемму 1 чтобы находить и обрабатывать вершины с точными текущими значениями расстояния до них.<br />
<br />
Модифицируем нашу MLB — структуру: будем хранить помеченные вершины в двух структурах: дерево поиска <tex>F</tex> и приоритетная очередь <tex>B</tex>, реализованная на MLB.<br />
Алгоритм, приведённый ниже, называется <b>''алгоритмом умной очереди''</b> (англ. ''smart queue''). <br />
<br />
Вершины в <tex>F</tex> будут иметь точные метки <tex>d(u)</tex>. Если <tex>F</tex> непусто, мы удалим оттуда вершину и прорелаксируем всех её соседей. Если же <tex>F</tex> пусто, мы достанем из<br />
<tex>B</tex> вершину с минимальной меткой и прорелаксируем всех её соседей.<br />
<br />
Рассмотрим механизм релаксации: пусть мы уменьшаем <tex>d(u)</tex>. Заметим, что в этом случае <tex>u</tex> не могло лежать в <tex>F</tex> (иначе <tex>d(u)</tex> было не точно). Если <tex>u \in B</tex> — применим <tex>\mathtt{decrease — key}</tex> к <tex>u</tex>. Эта операция либо переместила <tex>u</tex> внутри <tex>B</tex>, либо определила, что метка <tex>d(u)</tex> точна и переместила <tex>u</tex> в <tex>F</tex>.<br />
Если же <tex>u \notin F </tex> и <tex>u \notin B</tex>, мы применим операцию <tex>\mathtt{insert}</tex>, и <tex>u</tex> запишется в<br />
<tex>F</tex> или <tex>B</tex>, в зависимости от того, выполняется ли условие леммы.<br />
<br />
====Двунаправленный поиск====<br />
Мы можем уменьшить количество посещённых вершин в алгоритме Дейкстры, просто запустив его и из начальной и из конечной вершины. Такая эвристика не испортит скорость работы в худшем случае.<br />
<br />
Создадим две приоритетных очереди и запустим на одной из них алгоритм Дейкстры, ищущий <tex>d_{forward}(v)</tex> из <tex>s</tex>, а на другой — ищущий <tex>d_{reverse}(v)</tex> из <tex>t</tex>. Алгоритм завершит свою работу, когда какая-нибудь вершина <tex>z</tex> будет удалена из обеих очередей. <br />
<br />
Тонкость этого алгоритма заключается в том, что кратчайший путь <tex>s \rightsquigarrow t</tex> не обязательно пройдёт через вершину <tex>z</tex>. Поэтому после остановки двунаправленного поиска, нам необходимо перебрать все рёбра из вершин, имеющих <tex>d_{forward}(u)</tex> в <br />
вершины с <tex>d_{reverse}(v)</tex> и найти ребро <tex>uv</tex> с минимальным <tex>d_{forward}(u)+\ell(uv)+ d_{reverse}(v) </tex>. Если эта величина меньше, чем длина первоначально найденного пути — то это и есть результат работы алгоритма.<br />
<br />
На практике, такой двунаправленный поиск быстрее обычного алгоритма Дейкстры примерно в два раза.<br />
<br />
==Алгоритм A*==<br />
Приведём немного изменённую версию [[Алгоритм A*|этого алгоритма]].<br />
<br />
Возьмём функцию <tex>h(v): V \rightarrow \mathbb{R} </tex> — <b>''потенциал''</b> (aнгл. ''potential'') вершины. Тогда, с её помощью можно определить <b>''потенциальную стоимость''</b> (англ. ''reduced cost'') каждого ребра как <tex>\ell_{h}(v,w) = \ell(v,w)-h(v)+h(w)</tex><br />
<br />
Заметим, что замена <tex>\ell</tex> на <tex>\ell_{h}</tex> не изменит кратчайших путей: возьмём любой путь <tex>P = (s=v_{0},v_{1},...,v_{k},v_{k+1}=t)</tex>. Тогда <tex>\ell_{h}(P) = \ell_{h}(s,v_{1}), \ell_{h}(s,v_{w})</tex>. Тогда <tex>\ell_{h}(P) = \ell_{h}(s,v_{1})+\ell_{h}(v_{1},v_{2})+...+\ell_{h}(v_{k},t) =</tex> <tex> \ell(s,v_{1})-h(s)+h(v_{1})+\ell(v_{1},v_{2})-h(v_1)+h(v_{2})+...+\ell(v_{k},t)-h(v_k)+h(t) = </tex> <tex>\ell(P)-h(s)+h(t)</tex>. <br />
<br />
Таким образом длины все путей <tex>s \rightsquigarrow t</tex> изменятся на одну и ту же величину <tex>h(t)-h(s)</tex> <br />
<br />
В нашем случае, алгоритм A* будет эквивалентен алгоритму Дейкстры, на графе <tex>G_{h}</tex>, у которого стоимости рёбер заменили на их потенциальные стоимости. На каждом шаге необходимо будет выбирать из очереди вершину <tex>v</tex> с минимальным значением <tex>\ell(P_{s \rightsquigarrow v})-h(s)+h(v)</tex>. Очевидно, <tex>h(s)</tex> будет одинаковым для любой вершины <tex>v</tex>.<br />
<br />
Назовём функцию <tex>h</tex> <b>правдоподобной</b> (англ. ''feasible''), если <tex>\forall (u,v): \ell_{h}(u,v) \geqslant 0</tex>. Известно, что, если <tex>h(t)\leqslant 0</tex> и <tex>h</tex> правдоподобна, то для любого <tex>v</tex>, <tex>h(v)</tex> — нижняя граница <tex>d(v,t)</tex> <br />
<br />
Главное отличие от алгоритма Дейкстры в том, что A* является <b>информированным</b> алгоритмом — он обрабатывает в первую очередь те вершины, которые находятся ближе к результату. <br />
<br />
Скорость работы алгоритма A*:<br />
* в худшем случае — <tex>h(v)=0</tex> — вырождается в алгоритм Дейкстры<br />
* в лучшем случае — <tex>\forall v: h(v)=d(v,t)</tex> <br />
**<tex>\ell_{h}(v,w)=0</tex>, если ребро <tex>(v,w)</tex> лежит на кратчайшем пути, иначе потенциальная стоимость положительна<br />
**все посещённые вершины будут лежать на кратчайшем пути<br />
===Двунаправленный A*===<br />
<br />
Для двунаправленной версии алгоритма нам нужны две потенциальные функции:<br />
* <tex>p_{f}(v)</tex>, оценивающая <tex>d(v,t)</tex><br />
* <tex>p_{r}(v)</tex>, оценивающая <tex>d(s,v)</tex><br />
<br />
В этом случае появляется дополнительная проблема: различные потенциальные стоимости у рёбер для различных обходов:<br />
*<tex>\ell_{p_{f}}(v,w) = \ell(v,w)-p_{f}(v)+p_{f}(w)</tex> — если ребро обрабатывается в обходе, начатом в <tex>s</tex><br />
*<tex>\ell_{p_{r}}(v,w) = \ell(v,w)-p_{r}(w)+p_{r}(v)</tex> — если ребро обрабатывается в обходе, начатом в <tex>t</tex><br />
<br />
Чтобы избежать этой проблемы, необходимо, чтобы <tex>\ell_{p_{f}}(v,w) = \ell_{p_{r}}(v,w) \Leftrightarrow p_{f}(v) + p_{r}(v) = p_{f}(w) + p_{r}(w) = const</tex>. Кроме того, функции должны бить монотонными.<br />
<br />
Решение — использовать усреднённые потенциальные функции:<br />
*<tex>h_{f}(v) = \dfrac{p_{f}(v)-p_{r}(v)}{2}</tex><br />
*<tex>h_{r}(v) = \dfrac{p_{r}(v)-p_{f}(v)}{2} = -h_{f}(v)</tex><br />
<br />
При таком выборе потенциальных функций, выполняется <tex>\forall u : h_{f}(u)+h_{r}(u)=0</tex> и тогда двунаправленный A* становится аналогичен двунаправленному алгоритму Дейкстры<br />
<br />
==Двухэтапные алгоритмы==<br />
<br />
К сожалению, двунаправленный алгоритм Дейкстры всего в два раза быстрее обычного, а это слишком медленно. Рассмотрим алгоритм поиска кратчайшего пути, состоящий из двух этапов: <br />
# Препроцессинг:<br />
#* запускается единожды для графа,<br />
#* может занимать много времени,<br />
#* рассчитывает некую вспомогательную информацию.<br />
# Запрос:<br />
#* может использовать данные, полученные во время препроцессинга,<br />
#* запускается по требованию для пары <tex>(s,t)</tex>,<br />
#* должен выполняться очень быстро (в реальном времени).<br />
<br />
Можно рассмотреть в этом ключе два примера: <br />
* Алгоритм Дейкстры: препроцессинг — ничего не делать, запрос — выполнение алгоритма Дейкстры;<br />
* Полный перебор: препроцессинг — посчитать таблицу расстояний размером <tex>n \times n</tex> (займёт порядка 5 лет времени и 1 петабайта памяти для карты Европы), запрос — обратиться к элементу таблицы.<br />
<br />
Оба эти примера — крайние случаи. Нам нужно нечто более гибкое: препроцессинг за часы/минуты, рост количества предпосчитанных данных линейно от размера графа и запросы в реальном времени.<br />
<br />
===ALT===<br />
<br />
Аббревиатура ALT расшифровывается как <b>A</b>* +<b>L</b>andmarks + <b>T</b>riangle inequality : A* + ориентиры + неравенство треугольника.<br />
<br />
#Препроцессинг:<br />
#* взять небольшое количество вершин (например, 16), обозначив их как <b>ориентиры</b> (англ. ''landmarks''),<br />
#* для каждого из ориентиров посчитать кратчайшие пути до <b>всех</b> вершин,<br />
#* сохранить эти пути.<br />
#Запрос:<br />
#* используем A*,<br />
#* если некоторое ребро находится на кратчайшем пути между исходной точкой и ориентиром — по нему идём в первую очередь.<br />
<br />
[[Файл:ALT.jpg|right|frame|рис. 1]]<br />
Будем использовать неравенство треугольника для нижних оценок пути (см. рис. 1). Пусть <tex>A</tex> — один из ориентиров, тогда:<br />
*<tex>dist(v,w)\geqslant dist(A,w)-dist(A,v)</tex>,<br />
*<tex>dist(v,w)\geqslant dist(v,A)-dist(w,A)</tex>,<br />
*<tex>dist(v,w)\geqslant \max\{dist(A,w)-dist(A,v),dist(v,A)-dist(w,A)\}</tex>.<br />
<br />
Эта эвристика хорошо работает, на дорожных графах, для которых верно следующее: как правило, кратчайший путь затрагивает небольшое количество локальных дорог, потом крупную автомагистраль и снова некоторое количество локальных дорог.<br />
<br />
Сложности в выборе ориентиров:<br />
* хороший ориентир для запроса <tex>s \rightsquigarrow t</tex> должен находиться "до" <tex>s</tex> (точно не будет общих рёбер на кратчайшем пути) или "за" <tex>t</tex> (чем острее угол, тем меньше отклонение от предварительно посчитанного кратчайшего пути до искомого),<br />
* нам нужно выбрать такие ориентиры, которые будут неплохими для всех запросов.<br />
<br />
Выглядит логичным выбирать ориентиры на краю дорожной сети, тогда будет больше острых углов и ориентиры будут лучше.<br />
<br />
Существуют различные алгоритмы выбора ориентиров:<br />
====Случайный выбор (random)====<br />
[[Файл:planarLandmarks.jpg|right]]<br />
Как следует из названия, ориентиры выбираются случайным образом<br />
<br />
====Плоскостной (planar)====<br />
* Разделим карту на <tex>k</tex> секторов одинаковой площади,<br />
* возьмём ориентиром наиболее удалённую точку от центра в каждом секторе.<br />
<br />
Такой способ подходит, только если граф имеет относительно правильную форму. На практике обычно используется оптимизированная версия этого алгоритма.<br />
<br />
====Избирательный (avoid)====<br />
Этот алгоритм добавляет ориентиры по одному, глядя на вершины, которые плохо покрыты текущим набором ориентиров <tex>S</tex>.<br />
<br />
Построим из случайно выбранной вершины <tex>r</tex> дерево кратчайших путей <tex>T_{r}</tex>. <b>Весом</b> каждой вершины <tex>v</tex> в этом дереве назовём разность между истинной длиной пути <tex>d(v,r)</tex> и нижней оценкой этой длины <tex>\underline{d}(v,r)</tex>, полученной по текущему набору ориентиров. <b>Размером</b> вершины <tex>v</tex> назовём сумму её веса и размеров всех её потомков в <tex>T_{r}</tex>. Если поддерево <tex>T_{r}</tex> с корнем в <tex>v</tex> содержит ориентир, размер <tex>v</tex> равен 0.<br />
<br />
Начиная с максимальной по размеру вершины, пойдём вниз по дереву <tex>T_{r}</tex> и найдём лист с максимальным размером. Примем его за новый ориентир.<br />
<br />
====Поиск максимального покрытия (maxCover)====<br />
Основным минусом избирательного метода является то, что первый ориентир выбирается случайным образом и выбор последующих ориентиров будет сильно зависеть от первоначального. <br />
<br />
Мы можем улучшить найденные ориентиры, если сначала, используя избирательный метод, найдём набор ориентиров в несколько (обычно, 4) раза больше, чем необходимо, а потом отсеем лишние минимизируя время запроса.<br />
<br />
Оценим качество набора ориентиров <tex>S</tex> основываясь на покрытии дуг. Будем говорить, что ориентир <tex>L</tex> покрывает дугу <tex>(v,w)</tex>, если вершина <tex>v</tex> находится на кратчайшем пути <tex>L \rightsquigarrow w</tex>. То есть, <tex>\ell(v,w) = dist(L,w)-dist(L,v)</tex>, тогда такой выбор ориентира даст нам нижнюю границу для всех путей, содержащих <tex>(v,w)</tex>.<br />
<br />
Если хотя бы один ориентир из <tex>S</tex> покрывает дугу <tex>(v,w)</tex>, то и весь <tex>S</tex> покрывает эту дугу. <br />
<br />
Этот метод является наилучшим, но является наиболее медленным. Задача выбора ориентиров в этом случае становится NP-полной.<br />
<br />
===Reach===<br />
Эта эвристика основывается на интуитивном наблюдении: не стоит посещать "локальные" дороги, когда мы находимся достаточно далеко и от <tex>s</tex>, и от <tex>t</tex><br />
<br />
Пусть вершина <tex>v</tex> лежит на кратчайшем пути <tex>P: s \rightsquigarrow t</tex>. Тогда, назовём <b>охватом</b> (англ. ''reach'') вершины <tex>v</tex> относительно <tex>P</tex> величину <tex>r(v,P) = \min\{dist(s,v), dist(v,t)\}</tex>. Охватом вершины относительно всего графа назовём величину <tex>r(v) = \max\limits_{P} r(v,P)</tex> — максимум по всем кратчайшим путям, содержащим <tex>v</tex>.<br />
<br />
Помимо этого, будет полезным ввести понятие охвата ребра. Назовём охватом ребра <tex>(v,w)\in P</tex> относительно <tex>P</tex> величину <tex>\min\{dist(s,v), dist(w,t)\}</tex>. Аналогично, охватом ребра относительно всего графа назовём величину <tex>r(v,w) = \max\limits_{P} r((v,w),P)</tex> — максимум по всем кратчайшим путям, содержащим <tex>(v,w)</tex>.<br />
<br />
[[Файл:reach1.jpg|right]]<br />
Заметим, что вершины с большим охватом находятся вблизи середины некоторого длинного кратчайшего пути, то есть<br />
* на больших автомагистралях вершины имеют большой охват,<br />
* на локальных перекрёстках (внутри населённых пунктов) вершины имеют маленький охват.<br />
<br />
Во время обработки ребра <tex>(v,w)</tex>:<br />
* удалим вершину <tex>w</tex>, если <tex>r(w)<\min\{d(s,v)+\ell(v,w), LB(w,t)\}</tex>,<br />
* оценка <tex>LB(w,t)</tex> должна быть подобрана таким образом, чтобы, если бы <tex>P=(s,..,v,w,...,t)</tex> было кратчайшим путём, <tex>r(w)</tex> было бы больше. <br />
[[Файл:reach2.jpg|right]]<br />
Как искать нижнюю оценку длины пути <tex>LB(w,t)</tex>? <br />
* Явно: Евклидово расстояние, с помощью ориентиров.<br />
* Неявно: сделать поиск двунаправленным.<br />
<br />
Например, радиус <tex>R_{t}</tex> поиска в обратную сторону может быть нижней оценкой, т.к. если вершина <tex>w</tex> не была посещена поиском в обратную сторону, то <tex>d(w,t)\geq R_{t}</tex><br />
<br />
Таким образом, будем удалять <tex>w</tex>, если <tex>r(w)\textless \min\{d(s,v)+\ell(v,w), R_{t}\}</tex><br />
<br />
Для улучшения результата, нам необходимо сбалансировать прямой и обратный поиск.<br />
<br />
Рассмотрим препроцессинг:<br />
<br />
[[Файл:reach3.jpg|right]]<br />
* на начальном этапе <tex>\forall v: r(v)\leftarrow 0</tex>,<br />
* для каждой вершины <tex>s \in V</tex> рассмотрим дерево кратчайших путей до всех других вершин <tex>T_{s}</tex>, <br />
**найдём наиболее длинный путь <tex>P_{s\rightsquigarrow t}</tex>, содержащий <tex>v</tex>, <br />
**Назовём глубиной вершины <tex>d_{s}(v)</tex> расстояние от <tex>s</tex>, высотой вершины <tex>h_{s}(v)</tex> — расстояние до наиболее далёкого потомка вершины,<br />
** Тогда, охватом вершины в этом дереве будет величина <tex>r_{s}(v) = \min\{d_{s}(v),h_{s}(v)\}</tex>,<br />
** Тогда обновим значение охвата <tex>r(v) \leftarrow \max\{r(v),r_{s}(v)\}</tex>.<br />
<br />
Сложность алгоритма: <tex>O(nm)</tex>, поэтому он слишком медленный для больших графов и его нужно улучшить. <br />
<br />
Финальная версия препроцессинга будет иметь две фазы:<br />
*основная фаза (строятся частично обработанные деревья и добавляются сокращающие путь рёбра)<br />
*фаза отладки (вершины с большим охватом обрабатываются указанным выше алгоритмом — их гораздо меньше, поэтому обработка будет быстрой)<br />
<br />
====Сокращение области поиска====<br />
Заметим, что нам нужны только вершины с маленьким охватом <tex>r(v)\textless \varepsilon, \varepsilon=const</tex>. Заметим также, что если <tex>r(v) \geqslant \varepsilon</tex>, то существует такой путь <tex>P</tex>, что на нем лежит вершина <tex>v \in P</tex>, для которой выполняется условие <tex>r(v,P)\geqslant \varepsilon</tex><br />
<br />
Назовём кратчайший путь <tex>P_{s\rightsquigarrow t} = (s, s',...,v,...,t',t)</tex> <tex>\varepsilon</tex>-минимальным, если выполняются условия:<br />
<br />
*<tex>dist(s,v)\geqslant\varepsilon</tex>,<br />
*<tex>dist(s',v)\textless\varepsilon</tex>,<br />
*<tex>dist(v,t)\geqslant\varepsilon</tex>,<br />
*<tex>dist(v,t')\textless\varepsilon</tex>.<br />
<br />
Таким образом, алгоритм будет выглядеть так:<br />
* найдём оценку охвата <tex>r'(v)</tex>, используя только <tex>\varepsilon</tex> — минимальные пути,<br />
* если <tex>r'(v)<\varepsilon</tex>, то оценка корректна: <tex>r(v)=r'(v)</tex>,<br />
* если же <tex>r'(v)\geqslant \varepsilon</tex>, то она нас не интересует: <tex>r(v)\geqslant r'(v)</tex>.<br />
<br />
Полезно будет рассматривать <b>частично обработанные деревья</b> (англ. ''partial trees'') — деревья кратчайших путей, хранящие пути длиной, меньшей определённого порога. Тогда дерево кратчайших путей будет глубиной порядка <tex>2\varepsilon</tex>:<br />
* установим <tex>G'\leftarrow G</tex> и <tex>\varepsilon\leftarrow \varepsilon_{0}</tex> (маленькое число),<br />
* пока <tex>G'</tex> не пусто:<br />
** найдём частично обработанное дерево кратчайших путей из <tex>v</tex>, чтобы найти вершины с охватом <tex>r(v) \geqslant \varepsilon</tex>,<br />
** удалим из <tex>G'</tex> оставшиеся вершины (с охватом <tex>r(v) \textless\varepsilon</tex>, уже обработанные),<br />
** установим <tex>\varepsilon\leftarrow 3\varepsilon</tex>.<br />
[[Файл:reach5.jpg|right]]<br />
[[Файл:reach6.jpg|right]]<br />
<br />
====Пенальти====<br />
Предыдущее улучшение создаёт проблему: мы должны предполагать, что кратчайший путь может начинаться в вершине с маленьким охватом, которые мы отбрасываем на каждой итерации. Для того, чтобы принять их во внимание, мы введём новую величину — <b>пенальти</b>(англ. ''penalty'') — верхнюю оценку на длину кратчайшего пути в "отброшенной" зоне.<br />
<br />
Пусть <tex>G_{i} = (V_{i},A_{i})</tex> — подграф исходного графа, полученный на <tex>i</tex>-й итерации алгоритма, описанного выше. Назовём входящим пенальти (<i>in-penalty</i>) вершины <tex>v\in V_{i}</tex> величину <tex>\max\{ \overline{r}(u,v) : u,v \in A \backslash A_{i}\}</tex>, если у <tex>v</tex> было как минимум одно выброшенное в процессе алгоритма входящее ребро, или ноль в противном случае.<br />
Аналогично определим исходящее пенальти для исходящих из вершины рёбер. <br />
<br />
Изменим алгоритм, чтобы заменить вершины на их пенальти. Для этого переопределим глубину и высоту вершины.<br />
* Глубиной вершины <tex>v\in T_{x}</tex>, где <tex>T_{x}</tex> — частично обработанное дерево с корнем в <tex>x</tex> величину <tex>depth(v)=d(v)+in\textrm{-}penalty(x)</tex> , где <tex>d(v)</tex> — длина пути от корня до вершины в дереве.<br />
* Чтобы определить высоту вершины, нам нужно понятие "ложных листьев". Для каждой вершины <tex>v</tex> в дереве кратчайших путей добавим потомка <tex>v'</tex> — ложный лист, и ребро <tex>(v,v') = out\textrm{-}penalty(v)</tex>. В некотором смысле, <tex>v'</tex> будет выступать в роли всех рёбер, изначально инцидентных вершине <tex>v</tex>, которые мы отсекли. Тогда высотой вершины <tex>v</tex> будет расстояние от неё, до наиболее далёкого ложного листа. Подчеркнём, что в данный момент ложные листья добавляются неявно, и только после того, как дерево будет частично обработано.<br />
<br />
====Сокращение путей====<br />
Представим последовательность вершин степени 2 с большим охватом, идущих подряд. Добавим, <b>сокращающее ребро</b> (англ. ''shortcut'') — ребро, проходящее из начала пути в его конец с длиной, равной длине этого пути. Таким образом мы можем уменьшить охваты вершин на этом пути и ускорить препроцессинг (уменьшив количество проходимых рёбер), но увеличим память, необходимую для хранения нашего графа.<br />
<br />
На этом шаге мы будем искать <b>пропускаемые</b> (англ. ''bypassable'') вершины. Назовём вершину <tex>v</tex> пропускаемой, если выполняется одно из двух условий:<br />
* <tex>v</tex> имеет только одно входящее ребро <tex>(u,v)</tex> и одно исходящее ребро <tex>(v,w)</tex>,<br />
* <tex>v</tex> имеет два входящих ребра <tex>(u,v)</tex>, <tex>(w,v)</tex> и два исходящих ребра <tex>(v,w)</tex> ,<tex>(v,u)</tex>.<br />
В обоих случаях подразумевается, что <tex>u\neq w</tex>, то есть у <tex>v</tex> обязательно есть только два соседа. В первом случае, <tex>v</tex> — кандидат на односторонний пропуск (англ. ''one-way bypass''), во втором — на двухсторонний (англ. ''two-way bypass''). Мы будем использовать сокращающие рёбра, чтобы пропускать такие вершины.<br />
<br />
Линия (line) — путь в графе, содержащий как минимум три вершины, так, что все вершины, кроме начальной и конечной, пропускаемые. Каждая пропускаемая вершина может принадлежать только одной линии. Линии также могут быть односторонне- и двухсторонне- пропускаемыми, в зависимости от типа вершин, которые они содержат. Легко заметить, что на линии могут лежать вершины только одного типа.<br />
<br />
Как только мы нашли линию, самым простым решением будет добавить одно сокращающее ребро из начала в конец. Но практика показывает, что лучше сократить ещё и входящие в её состав линии меньшего размера, это ещё более уменьшит охваты пропускаемых вершин. Для этого перед добавлением сокращающего ребра по линии, рекурсивно найдём вершину, которая находится примерно на её середине и обработаем левый и правый отрезки как полноценные линии.<br />
====Удаление пропущенных вершин====<br />
Представим одностороннюю линию, состоящую из трёх вершин <tex>u</tex>, <tex>v</tex>, <tex>w</tex>. Когда мы добавили сокращающее ребро <tex>(u,w)</tex>, мы знали, что ребро <tex>(u,v)</tex> больше никогда не будет использоваться на кратчайшем пути содержащем подпуть <tex>u\rightsquigarrow w</tex>. Кроме того, любой кратчайший путь, содержащий <tex>(u,v)</tex>, будет оканчиваться либо в <tex>v</tex>, либо в близлежащей вершине с низким охватом.<br />
Тогда, корректной верхней оценкой охвата <tex>(u,v)</tex> является <tex>\overline{r}(u,v)=\ell(u,v)+out\textrm{-}penalty(v)</tex>. Аналогично, <tex>\overline{r}(v,w)=\ell(v,w)+in\textrm{-}penalty(v)</tex>. Зная это, мы можем удалить вершину <tex>v</tex> и смежные ей рёбра из графа и обновить соответствующие значения пенальти для её соседей.<br />
<br />
Такую же процедуру можно проделать с двусторонней линией, т.к. помимо оценок, указанных выше, можно добавить:<br />
* <tex>\overline{r}(w,v)=\ell(w,v)+out\textrm{-}penalty(v)</tex>,<br />
* <tex>\overline{r}(v,u)=\ell(v,u)+in\textrm{-}penalty(v)</tex>.<br />
<br />
====Фаза отладки====<br />
Тот факт, что мы используем пенальти, для ускорения вычисления корректных верхних оценок охвата, приводит к тому, что оценки становятся менее точными в процессе работы алгоритма и с ростом пенальти. Следовательно, для вершин, которые дольше находятся в графе, ошибки накапливаются. Это плохо, потом что такие вершины и являются самыми важными в графе — у них высокий охват, их посещает большое количество кратчайших путей. Если бы мы могли сделать их более точными, во время запроса можно было бы пропустить большее количество вершин.<br />
<br />
В этом и заключается цель фазы отладки. После того, как мы найдём верные значения верхних оценок, используя частично обработанные деревья, во время фазы отладки мы пересчитаем охват <tex>\delta = const</tex> вершин с наибольшими значениями охвата (в них больше всего ошибок).<br />
<br />
Пусть <tex>V_{\delta} \subset G</tex> — множество вершин с высоким охватом мощностью <tex>\delta</tex>. Чтобы пересчитать их охваты, сначала необходимо найти подграф <tex>G_{\delta} = (V_{\delta},A_{\delta})</tex>. Этот граф содержит не только первоначальные рёбра, но и добавленные во время основной фазы сокращающие рёбра. Затем мы запустим поиск точных значений охвата для каждой вершины этого подграфа. Так как деревья кратчайших путей будут содержать только вершины из <tex>G_{\delta}</tex>, то нам всё ещё нужно использовать входящие и исходящие пенальти для остальных вершин. Но, тем не менее, они будут меньше, т.к. для самых больших мы подсчитали точное значение охвата.<br />
<br />
Во время фазы отладки мы заботимся о точности, а не о скорости, поэтому не добавляем новых сокращающих рёбер и используем точный алгоритм. <br />
Поэтому, время работы алгоритма как минимум <tex>\Omega(\delta^{2})</tex><br />
<br />
==Итог==<br />
{| class="wikitable" style="width:17cm; text-align: center" border=1<br />
|+ Сравнение различных эвристик для поиска кратчайшего пути на карте США<br />
! Метод !! Время препроцессинга, м !! Память для препроцессинга, MB !! Сканируемые запросом вершины, шт !! Время запроса, мс<br />
|- <br />
| Алгоритм Дейкстры || - || 536 || 11 808 864 || 5440,5<br />
|-<br />
| ALT(16 ориентиров) || 18 || 2563 || 187 968 || 295,45<br />
|-<br />
| Reach || 28 || 893 || 2 405 || 1,77<br />
|-<br />
|}<br />
<br />
<br />
{| border="0" cellspacing="0" cellpadding="5"<br />
|+ Работа различных алгоритмов на карте севера США<br />
! Алгоритм Дейкстры !!ALT (16 ориентиров) !! Reach<br />
|- <br />
| [[Файл:Ex1.jpg]] || [[Файл:Ex2.jpg]] || [[Файл:Ex3.jpg]]<br />
|-<br />
|}<br />
Условные обозначения:<br />
* зелёный квадрат — начало пути<br />
* синий квадрат — конец пути<br />
* зелёные линии — пути, пройденные прямым обходом<br />
* синие линии — пути, пройденные обратным обходом<br />
* красные ромбы — ориентиры<br />
* жёлтые ромбы — выбранные при поиске пути ориентиры<br />
<br />
==См. также==<br />
*[[Алгоритм Дейкстры]]<br />
*[[Алгоритм A*]]<br />
<br />
==Источники информации==<br />
*[http://logic.pdmi.ras.ru/midas/sites/default/files/midas-werneck.pdf Презентация Renato Werneck c MIDAS 2010 - основа конспекта]<br />
*[http://research.microsoft.com/pubs/64511/tr-2004-24.pdf A* meets graph theory]<br />
*[http://algo2.iti.kit.edu/schultes/hwy/hhStarSubmit.pdf Highway Hierarhies Star*]<br />
*[http://www.ecc.uic.edu/pub/Bits/TransitGenieDocs/tm_thesis.pdf Heuristic Route Search in Public Transportation Networks]<br />
*[http://www.cs.princeton.edu/courses/archive/spr06/cos423/Handouts/GW05.pdf Computing Point-to-Point Shortest Paths from External Memory]<br />
*[http://research.microsoft.com/pubs/60764/tr-2005-132.pdf Reach for A*]<br />
[[Категория: Алгоритмы и структуры данных]]<br />
[[Категория: Кратчайшие пути в графах ]]</div>93.175.2.28http://neerc.ifmo.ru/wiki/index.php?title=%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D1%80%D1%8E%D0%BA%D0%B7%D0%B0%D0%BA%D0%B5&diff=66130Задача о рюкзаке2018-06-22T11:11:46Z<p>93.175.2.28: /* Метод динамического программирования */</p>
<hr />
<div>{{Задача<br />
|definition =<br />
'''Задача о рюкзаке '''(''англ. Knapsack problem'') — дано <tex>N</tex> предметов, <tex>n_i</tex> предмет имеет массу <tex> w_i > 0</tex> и стоимость <tex> p_i > 0</tex>. Необходимо выбрать из этих предметов такой набор, чтобы суммарная масса не превосходила заданной величины <tex>W</tex> (вместимость рюкзака), а суммарная стоимость была максимальна.<br />
}}<br />
<br />
== Формулировка задачи ==<br />
<br />
Дано <tex>N</tex> предметов, <tex>W</tex> — вместимость рюкзака, <tex>w=\{w_{1},w_{2},\dots,w_{N}\}</tex> — соответствующий ему набор положительных целых весов, <tex>p=\{p_{1},p_{2},\dots,p_{N}\}</tex> — соответствующий ему набор положительных целых стоимостей. Нужно найти набор бинарных величин <tex>B=\{b_{1},b_{2},\dots,b_{N}\}</tex>, где <tex>b_{i} = 1 </tex>, если предмет <tex>n_i</tex> включен в набор, <tex> b_{i} = 0 </tex>, если предмет <tex>n_i</tex> не включен, и такой что:<br />
<br />
#<tex>b_{1} w_{1}+ \dots + b_{N} w_{N} \leqslant W</tex><br />
#<tex>b_{1} p_{1}+ \dots + b_{N} p_{N} </tex> максимальна.<br />
<br />
== Варианты решения ==<br />
<br />
Задачу о рюкзаке можно решить несколькими способами:<br />
<br />
* Перебирать все подмножества набора из N предметов. Сложность такого решения <tex>O({2^{N}})</tex>.<br />
<br />
* Методом [[Meet-in-the-middle|Meet-in-the-middle]]. Сложность решения <tex> O({2^{N/2}}{N}) </tex><br />
<br />
* Метод динамического программирования. Сложность — <tex>O(NW)</tex>.<br />
<br />
== Метод динамического программирования ==<br />
<br />
Пусть <tex>A(k, s)</tex> есть максимальная стоимость предметов, которые можно уложить в рюкзак вместимости <tex>s</tex>, если можно использовать только первые <tex>k</tex> предметов, то есть <tex>\{n_1,n_2,\dots,n_k\}</tex>, назовем этот набор допустимых предметов для <tex>A(k,s)</tex>.<br />
<br />
<tex>A(k, 0) = 0</tex><br />
<br />
<tex>A(0, s) = 0</tex><br />
<br />
Найдем <tex>A(k, s)</tex>. Возможны 2 варианта:<br />
<br />
#Если предмет <tex>k</tex> не попал в рюкзак. Тогда <tex>A(k, s)</tex> равно максимальной стоимости рюкзака с такой же вместимостью и набором допустимых предметов <tex>\{n_1,n_2,\dots,n_{k-1}\}</tex>, то есть <tex>A(k,s) = A(k-1, s)</tex><br />
# Если <tex>k</tex> попал в рюкзак. Тогда <tex>A(k, s)</tex> равно максимальной стоимости рюкзака, где вес <tex>s</tex> уменьшаем на вес <tex>k</tex>-ого предмета и набор допустимых предметов <tex>\{n_1,n_2,\dots,n_{k-1}\}</tex> плюс стоимость <tex>k</tex>, то есть <tex>A(k-1, s-w_k) + p_k</tex><br />
<br />
<tex><br />
A(k, s) =<br />
\begin{cases}<br />
A(k-1, s), & b_k = 0 \\<br />
A(k-1, s-w_k) + p_k, & b_k = 1 \\<br />
\end{cases}<br />
</tex><br />
<br />
То есть: <br />
<tex>A(k,s) = \max(A(k-1,s), A(k-1,s-w_{k}) + p_{k})</tex><br />
<br />
Стоимость искомого набора равна <tex>A(N,W)</tex>, так как нужно найти максимальную стоимость рюкзака, где все предметы допустимы и вместимость рюкзака <tex>W</tex>.<br />
<br />
'''Восстановим набор предметов, входящих в рюкзак'''<br />
<br />
Будем определять, входит ли <tex>n_i</tex> предмет в искомый набор. Начинаем с элемента <tex>A(i,w)</tex>, где <tex>i = N</tex>, <tex>w = W</tex>. Для этого сравниваем <tex>A(i,w)</tex> со следующими значениями:<br />
<br />
#Максимальная стоимость рюкзака с такой же вместимостью и набором допустимых предметов <tex>\{n_1,n_2,\dots,n_{i-1}\}</tex>, то есть <tex>A(i-1, w)</tex><br />
#Максимальная стоимость рюкзака с вместимостью на <tex>w_i</tex> меньше и набором допустимых предметов <tex>\{n_1,n_2,\dots,n_{i-1}\}</tex> плюс стоимость <tex>p_i</tex>, то есть <tex>A(i-1, w-w_i)+p_i</tex><br />
<br />
Заметим, что при построении <tex>A</tex> мы выбирали максимум из этих значений и записывали в <tex>A(i, w)</tex>. Тогда будем сравнивать <tex>A(i, w)</tex> c <tex>A(i-1, w)</tex>, если равны, тогда <tex>n_i</tex> не входит в искомый набор, иначе входит.<br />
<br />
Метод динамического программирование всё равно не повзволяет решать задачу за полиномиальное время, потому что задача о ранце (или задача о рюкзаке) — одна из [[Класс NP|NP-полных]] задач комбинаторной оптимизации.<br />
<br />
== Реализация ==<br />
Сначала генерируем <tex>A</tex>. <br />
<br />
'''for''' i = 0 '''to''' w<br />
A[0][i] = 0<br />
'''for''' i = 0 '''to''' n<br />
A[i][0] = 0 ''<font color="green">//Первые элементы приравниваем к 0</font>''<br />
'''for''' k = 1 '''to''' n <br />
'''for''' s = 1 '''to''' w ''<font color="green">//Перебираем для каждого k все вместимости</font>'' <br />
'''if''' s >= w[k] ''<font color="green">//Если текущий предмет вмещается в рюкзак</font>'' <br />
A[k][s] = max(A[k - 1][s], A[k - 1][s - w[k]] + p[k]) ''<font color="green">//Выбираем класть его или нет</font>'' <br />
'''else''' <br />
A[k][s] = A[k - 1][s] ''<font color="green">//Иначе, не кладем</font>'' <br />
<br />
Затем найдем набор <tex>ans</tex> предметов, входящих в рюкзак, рекурсивной функцией:<br />
<br />
'''function''' findAns('''int''' k, '''int''' s)<br />
'''if''' A[k][s] == 0 <br />
'''return'''<br />
'''if''' A[k - 1][s] == A[k][s]<br />
findAns(k - 1, s)<br />
'''else''' <br />
findAns(k - 1, s - w[k])<br />
ans.push(k)<br />
<br />
Сложность алгоритма <tex>O(NW)</tex><br />
<br />
== Пример ==<br />
<br />
<tex>W = 13, N = 5</tex> <br />
<br />
<tex>w_{1} = 3, p_{1} = 1 </tex><br />
<br />
<tex>w_{2} = 4, p_{2} = 6 </tex><br />
<br />
<tex>w_{3} = 5, p_{3} = 4 </tex><br />
<br />
<tex>w_{4} = 8, p_{4} = 7 </tex><br />
<br />
<tex>w_{5} = 9, p_{5} = 6 </tex><br />
<br />
{|border="1" class="wikitable" style="text-align:center" width="75%"<br />
|-<br />
! || 1 || 2 || 3 || 4 || 5 || 6 || 7 || 8 || 9 || 10 || 11 || 12 || 13 <br />
|-<br />
| k = 0 || 0 || 0 || 0 || 0 || 0 || 0 || 0 || 0 || 0 || 0 || 0 || 0 || 0 <br />
|-<br />
| k = 1 || 0 || 0 || 1 || 1 || 1 || 1 || 1 || 1 || 1 || 1 || 1 || 1 || 1 <br />
|-<br />
| k = 2 || 0 || 0 || 1 || 6 || 6 || 6 || 7 || 7 || 7 || 7 || 7 || 7 || 7 <br />
|-<br />
| k = 3 || 0 || 0 || 1 || 6 || 6 || 6 || 7 || 7 || 10 || 10 || 10 || 11 || 11 <br />
|-<br />
| k = 4 || 0 || 0 || 1 || 6 || 6 || 6 || 7 || 7 || 10 || 10 || 10 || 13 || 13 <br />
|-<br />
| k = 5 || 0 || 0 || 1 || 6 || 6 || 6 || 7 || 7 || 10 || 10 || 10 || 13 || 13 <br />
|}<br />
<br />
Числа от 0 до 13 в первой строчке обозначают вместимость рюкзака.<br />
<br />
В первой строке как только вместимость рюкзака <tex>n \geqslant 3</tex>, добавляем в рюкзак 1 предмет.<br />
<br />
Рассмотрим <tex>k = 3</tex>, при каждом <tex>s \geqslant 5 (</tex>так как <tex>w_3 = 5)</tex> сравниваем <tex>A[k-1][s]</tex> и <tex>A[k-1][s-w_3]+p_3</tex> и записываем в <tex>A[k][s]</tex> стоимость либо рюкзака без третьего предмета, но с таким же весом, либо с третьим предметом, тогда стоимость равна стоимости третьего предмета плюс стоимость рюкзака с вместимостью на <tex>w_3</tex> меньше. <br />
<br />
Максимальная стоимость рюкзака находится в <tex>A(5, 13)</tex>.<br />
<br />
'''Восстановление набора предметов, из которых состоит максимально дорогой рюкзак.'''<br />
<br />
Начиная с <tex>A(5, 13)</tex> восстанавливаем ответ. Будем идти в обратном порядке по <tex>k</tex>. ''<font color="000000">Красным фоном обозначим наш путь</font>''<br />
<br />
{|border="1" class="wikitable" style="text-align:center" width="75%"<br />
|-<br />
! || 1 || 2 || 3 || 4 || 5 || 6 || 7 || 8 || 9 || 10 || 11 || 12 || 13 <br />
|-<br />
| k = 0 || 0 || 0 || 0 || 0 || 0 || 0 || 0 || 0 || 0 || 0 || 0 || 0 || 0 <br />
|-<br />
| k = 1 || 0 ||style="background:#FF0000"| 0 || 1 || 1 || 1 || 1 || 1 || 1 || 1 || 1 || 1 || 1 || 1 <br />
|-<br />
| k = 2 || 0 || 0 || 1 || 6 ||style="background:#FF0000"| 6 || 6 || 7 || 7 || 7 || 7 || 7 || 7 || 7 <br />
|-<br />
| k = 3 || 0 || 0 || 1 || 6 ||style="background:#FF0000"| 6 || 6 || 7 || 7 || 10 || 10 || 10 || 11 || 11 <br />
|-<br />
| k = 4 || 0 || 0 || 1 || 6 || 6 || 6 || 7 || 7 || 10 || 10 || 10 || 13 ||style="background:#FF0000"| 13 <br />
|-<br />
| k = 5 || 0 || 0 || 1 || 6 || 6 || 6 || 7 || 7 || 10 || 10 || 10 || 13 ||style="background:#FF0000"| 13 <br />
|}<br />
<br />
Таким образом, в набор входит <tex>2</tex> и <tex>4</tex> предмет.<br />
<br />
Стоимость рюкзака: <tex> 6 + 7 = 13</tex><br />
<br />
Вес рюкзака: <tex> 4 + 8 = 12</tex><br />
<br />
=Другие задачи семейства=<br />
==Ограниченный рюкзак==<br />
{{Задача<br />
|definition =<br />
'''Ограниченный рюкзак''' (англ. ''Bounded Knapsack Problem'') — обобщение классической задачи, когда любой предмет может быть взят некоторое количество раз.<br />
}}<br />
<br />
<br />
===Формулировка Задачи===<br />
Каждый предмет может быть выбран ограниченное <tex>b_i</tex> число раз.<br />
Задача выбрать число <tex>x_i</tex> предметов каждого типа так, чтобы<br />
<br />
* максимизировать общую стоимость: <tex>\sum_{i=1}^N p_ix_i</tex>;<br />
<br />
* выполнялось условие совместности: <tex>\sum_{i=1}^N w_ix_i \leqslant W</tex>;<br />
<br />
где <tex> x_i \in (0,1,\dots,b_i)</tex> для всех <tex> i= 1,2,\dots,N</tex>.<br />
<br />
===Варианты решения===<br />
При небольших <tex>b_i</tex> решается сведением к классической задаче о рюкзаке. В иных случаях:<br />
* Методом ветвей и границ.<br />
* Методом динамического программирования.<br />
<br />
===Метод динамического программирования===<br />
Пусть <tex>d(i,c)</tex> максимальная стоимость любого возможного числа предметов типов от 1 до <tex>i</tex>, суммарным весом до <tex>c</tex>.<br />
<br />
Заполним <tex>d(0,c)</tex> нулями.<br />
<br />
Тогда меняя i от 1 до <tex>N</tex>, рассчитаем на каждом шаге <tex>d(i,c)</tex>, для <tex>c</tex> от 1 до <tex>W</tex>, по рекуррентной формуле:<br />
<br />
<tex>d(i,c) = \max(d(i - 1, c - lw_i) + lp_i) </tex> по всем целым <tex> l </tex> из промежутка <tex> 0 \leqslant l \leqslant min(b_i,\lfloor c/w_i \rfloor)</tex>.<br />
<br />
Если не нужно восстанавливать ответ, то можно использовать одномерный массив <tex>d(c)</tex> вместо двумерного.<br />
<br />
После выполнения в <tex> d(N,W) </tex> будет лежать максимальная стоимость предметов, помещающихся в рюкзак.<br />
<br />
=== Реализация ===<br />
'''for''' i = 0 '''to''' w ''<font color="green">//База</font>''<br />
d[0][i] = 0<br />
'''for''' i = 1 '''to''' n <br />
'''for''' c = 1 '''to''' w ''<font color="green">//Перебираем для каждого i, все вместимости </font>''<br />
d[i][c] = d[i - 1][c]<br />
'''for''' l = min(b[i], c / w[i]) '''downto''' 1 ''<font color="green">//Ищем l для которого выполняется максимум </font>''<br />
d[i][c] = max(d[i][c], d[i - 1][c - l * w[i]] + p[i] * l)<br />
<br />
Сложность алгоритма <tex>O(NW^2)</tex>.<br />
==Неограниченный рюкзак==<br />
{{Задача<br />
|definition =<br />
'''Неограниченный рюкзак''' (англ.''Unbounded Knapsack Problem'') — обобщение ограниченного рюкзака, в котором любой предмет может быть выбран любое количество раз.<br />
}}<br />
<br />
===Формулировка Задачи===<br />
Каждый предмет может быть выбран любое число раз.<br />
Задача выбрать количество <tex>x_i</tex> предметов каждого типа так, чтобы<br />
<br />
*максимизировать общую стоимость: <tex>\sum_{i=1}^N p_ix_i</tex>;<br />
<br />
*выполнялось условие совместности: <tex>\sum_{i=1}^N w_ix_i \leqslant W</tex>;<br />
<br />
где <tex> x_i \geqslant 0 </tex> целое, для всех <tex> i= 1,2,\dots,N</tex>.<br />
<br />
===Варианты решения===<br />
Самые распространенные методы точного решения это:<br />
* Метод ветвей и границ.<br />
* Метод динамического программирования.<br />
<br />
===Метод динамического программирования===<br />
Пусть <tex>d(i,c)</tex> максимальная стоимость любого количества вещей типов от 1 до <tex>i</tex>, суммарным весом до <tex>c</tex> включительно.<br />
<br />
Заполним <tex>d(0,c)</tex> нулями.<br />
<br />
Тогда меняя i от 1 до <tex>N</tex>, рассчитаем на каждом шаге <tex>d(i,c)</tex>, для <tex>c</tex> от 0 до <tex>W</tex>, по рекуррентной формуле:<br />
<br />
<tex><br />
d(i,c) =<br />
\begin{cases}<br />
d(i - 1, c) & for\ c = 0, \dots, w_i - 1; \\<br />
\max(d(i - 1, c), d(i, c - w_i) + p_i) & for\ c = w_i, \dots, W; <br />
\end{cases}<br />
</tex><br />
<br />
После выполнения в <tex> d(N,W) </tex> будет лежать максимальная стоимость предметов, помещающихся в рюкзак.<br />
<br />
Если не нужно восстанавливать ответ, то можно использовать одномерный массив <tex>d(c)</tex> вместо двумерного и использовать формулу:<br />
<br />
<tex> d(c) = \max(d(c), d(c - w_i) + p_i) </tex>;<br />
<br />
Сложность алгоритма <tex>O(NW)</tex>.<br />
<br />
==Непрерывный рюкзак==<br />
{{Задача<br />
|definition =<br />
'''Непрерывный рюкзак''' (англ. ''Continuous knapsack problem'') — вариант задачи, в котором возможно брать любою дробную часть от предмета, при этом удельная стоимость сохраняется.<br />
}}<br />
<br />
===Формулировка Задачи===<br />
Задача выбрать часть <tex>x_i</tex> каждого предмета так, чтобы<br />
<br />
*максимизировать общую стоимость: <tex>\sum_{i=1}^N p_ix_i</tex>;<br />
<br />
*выполнялось условие совместности: <tex>\sum_{i=1}^N w_ix_i \leqslant W</tex>;<br />
<br />
где <tex> 0 \leqslant x_i \leqslant 1</tex> дробное, для всех <tex> i= 1,2,\dots,N</tex>.<br />
<br />
===Варианты решения===<br />
Возможность брать любую часть от предмета сильно упрощает задачу. Жадный алгоритм дает оптимальное решение в данном случае.<br />
<br />
=== Реализация ===<br />
sort() ''<font color="green">//Сортируем в порядке убывания удельной стоимости.</font>''<br />
<br />
'''for''' i = 1 '''to''' n ''<font color="green">//Идем по предметам </font>'' <br />
'''if''' w > w[i] ''<font color="green">//Если помещается — берем</font>''<br />
sum += p[i]<br />
w -= w[i]<br />
'''else'''<br />
sum += w / w[i] * p[i] ''<font color="green">//Иначе берем сколько можно и выходим</font>''<br />
'''break'''<br />
<br />
==Задача о суммах подмножеств==<br />
{{Задача<br />
|definition =<br />
'''Задача о суммах подмножеств''' (англ. ''Subset sum problem, Value Independent Knapsack Problem'') — задача из семейства, в которой стоимость предмета совпадает с его весом.<br />
}}<br />
<br />
===Формулировка Задачи===<br />
Нужно выбрать подмножество так, чтобы сумма ближе всего к <tex>W</tex>, но не превысила его. Формально, нужно найти набор бинарных величин <tex>x_i</tex>, так чтобы<br />
<br />
*максимизировать общую стоимость: <tex>\sum_{i=1}^N w_ix_i</tex>;<br />
<br />
*выполнялось условие совместности: <tex>\sum_{i=1}^N w_ix_i \leqslant W</tex>;<br />
<br />
<tex> x_j = 1 </tex> если <tex> j</tex> предмет назначен рюкзаку, иначе <tex> x_{ij} = 0 </tex>, для всех <tex> i= 1,2,\dots,N</tex>.<br />
<br />
===Варианты решения===<br />
Для решения пригодны любые методы применяемые для классической задачи, однако специализированые алгоритмы обычно более оптимальны по параметрам. Используются:<br />
* Метод динамического программирования.<br />
* Гибридный метод на основе динамического программирования и поиска по дереву. В худшем случае, работает за <tex> O(n) </tex>.<br />
<br />
===Метод динамического программирования===<br />
Пусть <tex>d(i,c)</tex> максимальная сумма <tex>\leqslant c</tex>, подмножества взятого из <tex> 1, \dots,\ i</tex> элементов.<br />
<br />
Заполним <tex>d(0,c)</tex> нулями.<br />
<br />
Тогда меняя i от 1 до <tex>N</tex>, рассчитаем на каждом шаге <tex>d(i,c)</tex>, для <tex>c</tex> от 0 до <tex>W</tex>, по рекуррентной формуле:<br />
<br />
<tex><br />
d(i,c) =<br />
\begin{cases}<br />
d(i - 1, c) & for\ c = 0, \dots, w_i - 1; \\<br />
\max(d(i - 1, c), d(i - 1, c - w_i) + w_i) & for\ c = w_i, \dots, W; <br />
\end{cases}<br />
</tex><br />
<br />
После выполнения в <tex> d(N,W) </tex> будет лежать максимальная сумма подмножества, не превышающая заданное значение.<br />
<br />
Сложность алгоритма <tex>O(NW)</tex>.<br />
<br />
==Задача о размене==<br />
{{Задача<br />
|definition =<br />
'''Задача о размене''' (англ. ''Change-Making problem'') — имеются <tex> N </tex> неисчерпаемых типов предметов с весами <tex>w_i</tex>. Нужно наполнить рюкзак предметами с суммарным весом <tex>W</tex>.<br />
}}<br />
<br />
Часто задачу ставят как, дать сдачу наименьшим количеством монет.<br />
===Формулировка Задачи===<br />
Каждый предмет может быть выбран любое число раз.<br />
Задача выбрать количество <tex>x_i</tex> предметов каждого типа так, чтобы<br />
<br />
*минимизировать количество взятых предметов: <tex>\sum_{i=1}^N x_i</tex>;<br />
<br />
*сумма весов выбранных предметов равнялась вместимости рюкзака: <tex>\sum_{i=1}^N w_ix_i = W</tex>;<br />
<br />
Где <tex> x_i \geqslant 0 </tex> целое, для всех <tex> i= 1,2,\dots,N</tex>.<br />
===Варианты решения===<br />
Самые распространенные методы точного решения это:<br />
* Метод ветвей и границ.<br />
* Метод динамического программирования.<br />
<br />
===Метод динамического программирования===<br />
Пусть <tex>d(i,c)</tex> минимальное число предметов, типов от 1 до <tex>i</tex>, необходимое, чтобы заполнить рюкзак вместимостью <tex>c</tex>.<br />
<br />
Пусть <tex>d(0,0) = 0</tex>, а <tex>d(0,c) = \inf</tex> для всех <tex>c > 0</tex>. <br />
<br />
Тогда меняя i от 1 до <tex>N</tex>, рассчитаем на каждом шаге <tex>d(i,c)</tex>, для <tex>c</tex> от 0 до <tex>W</tex>, по рекуррентной формуле:<br />
<br />
<tex><br />
d(i,c) =<br />
\begin{cases}<br />
d(i - 1, c) & for\ c = 0, \dots, w_i - 1; \\<br />
min(d(i - 1, c), d(i, c - w_i) + 1) & for\ c = w_i, \dots, W; <br />
\end{cases}<br />
</tex><br />
<br />
После выполнения в <tex> d(N,W) </tex> будет лежать максимальная стоимость предметов, помещающихся в рюкзак.<br />
<br />
Если не нужно восстанавливать ответ, то можно использовать одномерный массив <tex>d(c)</tex> вместо двумерного и использовать формулу:<br />
<br />
<tex> d(c) = min(d(c), d(c - w_i) + 1) \qquad for\ c = w_i, \dots, W</tex>.<br />
<br />
Сложность алгоритма <tex>O(NW)</tex>.<br />
<br />
==Задача об упаковке==<br />
{{Задача<br />
|definition =<br />
'''Задача об упаковке''' (англ. ''Bin Packing Problem'') — имеются <tex> N </tex> рюкзаков вместимости <tex> W </tex> и столько же предметов с весами <tex>w_i</tex>. Нужно распределить все предметы, задействовав минимальное количество рюкзаков.<br />
}}<br />
<br />
===Формулировка Задачи===<br />
Математически задачу можно представить так:<br />
<br />
*минимизировать количество рюкзаков: <tex>\sum_{i=1}^N y_i</tex>;<br />
<br />
*так чтобы выполнялось условие на совместность: <tex>\sum_{i=1}^N w_ix_{ij} \leqslant Wy_j \qquad j \in {1, \dots, N}</tex>;<br />
<br />
<tex> x_{ij} = 1 </tex> если <tex> j</tex> предмет назначен <tex>i </tex> рюкзаку. Иначе <tex> x_{ij} = 0 </tex>.<br />
<br />
<tex> y_i = 1 </tex> если <tex> i</tex> рюкзак используется. Иначе <tex> y_i = 0 </tex>.<br />
<br />
===Варианты решения===<br />
Применение динамического программирования нецелесообразно. Обычно применяют аппроксимационные алгоритмы, либо используют метод ветвей и границ.<br />
<br />
==Мультипликативный рюкзак==<br />
{{Задача<br />
|definition =<br />
'''Мультипликативный рюкзак''' (англ. ''Multiple Knapsack Problem'') — есть <tex>N</tex> предметов и <tex>M</tex> рюкзаков (<tex>M\leqslant N</tex>). У каждого рюкзака своя вместимость <tex>W_i</tex>. Задача: выбрать <tex>M</tex> не пересекающихся множеств, назначить соответствие рюкзакам так, чтобы суммарная стоимость была максимальна, а вес предметов в каждом рюкзаке не превышал его вместимость.<br />
}}<br />
<br />
===Формулировка Задачи===<br />
Максимизировать <tex>\sum_{i=1}^M \sum_{j=1}^{N} p_jx_{ij}</tex><br />
<br />
так, чтобы <tex>\sum_{i=1}^N w_jx_{ij} \leqslant W_i</tex> выполнялось для всех <tex> i= 1,2,\dots,N</tex>.<br />
<br />
<tex>\sum_{j=1}^{M}x_{ij}=1</tex> для всех <tex> i= 1,2,\dots,N</tex>.<br />
<br />
<br />
<tex> x_{ij} = 1 </tex> если <tex> j</tex> предмет назначен <tex>i </tex> рюкзаку. Иначе <tex> x_{ij} = 0 </tex>.<br />
<br />
===Варианты решения===<br />
Применение динамического программирования, для задач данного типа нецелесообразно. Используются вариации метода ветвей и границ.<br />
<br />
==Задача о назначении==<br />
{{Задача<br />
|definition =<br />
'''Задача о назначении''' (англ. ''Generalized Assignment Problem'') — Наиболее общая задача семейства. Отличается от мультипликативного рюкзака тем, что каждый предмет имеет различные характеристики в зависимости от рюкзака, куда его помещают. Есть <tex>N</tex> предметов и <tex>M</tex> рюкзаков (<tex>M\leqslant N</tex>). У каждого рюкзака своя вместимость <tex>W_i</tex>, у <tex> j </tex> предмета <tex> p_{ij} </tex> стоимость и вес, при помещении его в <tex> i </tex> рюкзак, равны <tex> p_{ij} </tex> и <tex> w_{ij} </tex> соответственно. <br />
}}<br />
<br />
Весьма важная задача, так как она моделирует оптимальное распределение различных задач между вычислительными блоками.<br />
===Формулировка Задачи===<br />
<br />
Максимизировать стоимость выбранных предметов <tex>\sum_{i=1}^M\sum_{j=1}^N p_{ij} x_{ij}</tex>,<br />
<br />
при выполнении условия совместности <tex>\sum_{j=1}^N w_{ij} x_{ij} \leqslant W_i \qquad i=1, \ldots, M</tex>.<br />
<br />
<tex> \sum_{i=1}^M x_{ij} \leqslant 1 \qquad j=1, \ldots, N</tex>.<br />
<br />
<tex> x_{ij} \in \{0,1\} \qquad i=1, \ldots, N, \quad j=1, \ldots, N</tex>.<br />
<br />
===Варианты решения===<br />
Применение динамического программирования нецелесообразно. Наиболее используем метод ветвей и границ.<br />
<br />
== См. также ==<br />
* [[Класс NP]]<br />
* [[Метод четырех русских для умножения матриц]]<br />
* [[Задача о редакционном расстоянии, алгоритм Вагнера-Фишера]]<br />
* [[Meet-in-the-middle]]<br />
<br />
== Источники информации ==<br />
*[http://informatics.mccme.ru/moodle/mod/book/view.php?id=815&chapterid=60 Дистанционная подготовка по информатике]<br />
*[http://rosettacode.org/wiki/Knapsack_Problem Код для нескольких задач семейства на всевозможных языках]<br />
*[http://www.diku.dk/users/pisinger/95-1.pdf David Pisinger Knapsack problems. — 1995]<br />
*Silvano Martello, Paolo Toth. Knapsack Problems: Algorithms and Computer Implementations — 1990 г. — ISBN 0-471-92420-2<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Динамическое программирование]]</div>93.175.2.28http://neerc.ifmo.ru/wiki/index.php?title=%D0%91%D1%8B%D1%81%D1%82%D1%80%D0%B0%D1%8F_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0&diff=66129Быстрая сортировка2018-06-22T10:24:09Z<p>93.175.2.28: /* Среднее время работы */</p>
<hr />
<div>'''Быстрая сортировка''' (англ. ''quick sort'', сортировка Хоара) {{---}} один из самых известных и широко используемых алгоритмов сортировки. Среднее время работы <Tex>O(n\log{n})</Tex>, что является асимптотически оптимальным временем работы для алгоритма, основанного на сравнении. Хотя время работы алгоритма для массива из <tex>n</tex> элементов в худшем случае может составить <tex>\Theta(n^2)</tex>, на практике этот алгоритм является одним из самых быстрых.<br />
<br />
==Алгоритм==<br />
Быстрый метод сортировки функционирует по принципу "разделяй и властвуй". <br />
* Массив <tex> a[l \ldots r]</tex> типа <tex> T </tex> разбивается на два (возможно пустых) подмассива <tex> a[l \ldots q]</tex> и <tex> a[q+1 \ldots r]</tex>, таких, что каждый элемент <tex> a[l \ldots q]</tex> меньше или равен <tex> a[q]</tex>, который в свою очередь, не превышает любой элемент подмассива <tex> a[q+1 \ldots r]</tex>. Индекс вычисляется в ходе процедуры разбиения.<br />
* Подмассивы <tex> a[l \ldots q]</tex> и <tex> a[q+1 \ldots r]</tex> сортируются с помощью рекурсивного вызова процедуры быстрой сортировки.<br />
* Поскольку подмассивы сортируются на месте, для их объединения не требуются никакие действия: весь массив <tex> a[l \ldots r]</tex> оказывается отсортированным.<br />
<br />
==Псевдокод==<br />
'''void''' quicksort(a: '''T'''[n], '''int''' l, '''int''' r)<br />
'''if''' l < r<br />
'''int''' q = partition(a, l, r)<br />
quicksort(a, l, q)<br />
quicksort(a, q + 1, r)<br />
Для сортировки всего массива необходимо выполнить процедуру <tex>\mathrm{quicksort(a, 0, length[a] - 1)}</tex>.<br />
<br />
===Разбиение массива===<br />
Основной шаг алгоритма сортировки {{---}} процедура <tex>\mathrm{partition}</tex>, которая переставляет элементы массива <tex>a[l \ldots r]</tex> типа <tex> T </tex> нужным образом.<br />
Разбиение осуществляется с использованием следующей стратегии. Прежде всего, в качестве разделяющего элемента произвольно выбирается элемент <br />
<tex> a[(l + r) / 2] </tex>. Далее начинается просмотр с левого конца массива, который продолжается до тех пор, пока не будет найден элемент, превосходящий по значению разделяющий элемент, затем выполняется просмотр, начиная с правого конца массива, который продолжается до тех пор, пока не отыскивается элемент, который по значению меньше разделяющего. Оба элемента, на которых просмотр был прерван, очевидно, находятся не на своих местах в разделенном массиве, и потому они меняются местами. Так продолжаем дальше, пока не убедимся в том, что слева от левого указателя не осталось ни одного элемента, который был бы больше по значению разделяющего, и ни одного элемента справа от правого указателя, которые были бы меньше по значению разделяющего элемента.<br />
<br />
Переменная <tex> v </tex> сохраняет значение разделяющего элемента <tex> a[(l + r) / 2] </tex>, a <tex> i </tex> и <tex> j </tex> представляет собой, соответственно, указатели левого и правого просмотра. Цикл разделения увеличивает значение <tex> i </tex> и уменьшает значение <tex> j </tex> на <tex> 1 </tex>, причем условие, что ни один элемент слева от <tex> i </tex> не больше <tex> v </tex> и ни один элемент справа от <tex> j </tex> не меньше <tex> v </tex>, не нарушается. Как только значения указателей пересекаются, процедура разбиения завершается.<br />
<br />
'''int''' partition(a: '''T'''[n], '''int''' l, '''int''' r)<br />
'''T''' v = a[(l + r) / 2]<br />
'''int''' i = l<br />
'''int''' j = r<br />
'''while''' (i <tex> \leqslant </tex> j) <br />
'''while''' (a[i] < v)<br />
i++<br />
'''while''' (a[j] > v)<br />
j--<br />
'''if''' (i <tex> \geqslant </tex> j) <br />
'''break'''<br />
swap(a[i++], a[j--])<br />
'''return''' j<br />
<br />
==Асимптотика==<br />
===Худшее время работы===<br />
Предположим, что мы разбиваем массив так, что одна часть содержит <tex>n - 1</tex> элементов, а вторая {{---}} <tex>1</tex>. Поскольку процедура разбиения занимает время <tex>\Theta(n)</tex>, для времени работы <tex>T(n)</tex> получаем соотношение:<br />
<br />
<br />
<tex>T(n) = T(n - 1) + \Theta(n) = \sum\limits_{k=1}^{n} \Theta(k) = \Theta(\sum\limits_{k=1}^{n} k) = \Theta(n^2)</tex>.<br />
<br />
Мы видим, что при максимально несбалансированном разбиении время работы составляет <tex>\Theta(n^2)</tex>. В частности, это происходит, если массив изначально отсортирован.<br />
<br />
===Способ построить массив с максимальным количеством сравнений при выборе среднего элемента в качестве опорного===<br />
В некоторых алгоритмах быстрой сортировки в качестве опорного выбирается элемент, который стоит в середине рассматриваемого массива. Рассмотрим массив, на котором быстрая сортировка с выбором среднего элемента в качестве опорного сделает <tex>\Theta(n^2)</tex> сравнений. Очевидно, что это будет достигаться при худшем случае (когда при каждом разбиении в одном массиве будет оказываться <tex>1</tex>, а в другом <tex> n - 1 </tex> элемент).<br />
<br />
Заполним сначала массив <tex>a</tex> длины <tex>n</tex> элементами от <tex>1</tex> до <tex> n </tex>, затем применим следующий алгоритм (нумерация с нуля):<br />
<br />
'''void''' antiQsort(a: '''T'''[n])<br />
'''for''' i = 0 '''to''' n - 1 <br />
swap(a[i], a[i / 2])<br />
Тогда на каждом шаге в качестве среднего элемента будет ставиться самый крупный элемент.<br />
<br />
При выполнении <tex>\mathrm{partition}</tex> делается <tex>\Theta(n)</tex> сравнений из-за того, что с помощью индексов <tex>i</tex> и <tex>j</tex> мы проходим в лучшем случае <tex>\Omega(n)</tex> элементов (если функция прекращает свою работу, как только индексы встречаются), в худшем случае <tex>O(2n)</tex> элементов (если оба индекса полностью проходят массив). При каждом изменении индекса делается сравнение, значит, процедура <tex>\mathrm{partition}</tex> делает <tex>\Theta(n)</tex> сравнений с точностью до константы.<br />
<br />
Рассмотрим, какой элемент будет выбираться опорным на каждом шаге. <tex>\mathrm{antiQsort}</tex> на каждом шаге меняет местами последний и центральный элементы, поэтому в центре оказывается самый крупный элемент. А <tex>\mathrm{partition}</tex> делает абсолютно симметричные этой процедуре операции, но в другую сторону: меняет местами центральный элемент с последним, так что самый крупный элемент становится последним, а затем выполняет на массиве длины на один меньшей ту же операцию. Получается, что опорным всегда будет выбираться самый крупный элемент, так как <tex> \mathrm{antiQsort} </tex> на массиве любой длины будет выполнять операции, обратные <tex>\mathrm{partition}</tex>. Фактически, <tex>\mathrm{partition}</tex> {{---}} это <tex>\mathrm{antiQsort}</tex>, запущенная в другую сторону. Также стоит отметить, что процедура разбиения будет делать на каждом шаге только одну смену элементов местами. Сначала <tex>i</tex> дойдет до середины массива, до опорного элемента, <tex>j</tex> останется равным индексу последнего элемента. Затем произойдет <tex>\mathrm{swap}</tex> и <tex>i</tex> снова начнет увеличиваться, пока не дойдет до последнего элемента, <tex>j</tex> опять не изменит свою позицию. Потом произойдет выход из <tex>\mathrm{while}</tex>.<br />
<br />
Разбиение массива будет произведено <tex>\Theta(n)</tex> раз, потому что разбиение производится на массивы длины <tex>1</tex> и <tex> n - 1 </tex> из-за того, что на каждом шаге разбиения в качестве опорного будет выбираться самый крупный элемент (оценка на худшее время работы доказана выше). Следовательно, на массиве, который строится описанным выше способом, выполняется <tex>\Theta(n)</tex> <tex>\mathrm{partition}</tex> и <tex>\Theta(n)</tex> сравнений для каждого выполнения <tex>\mathrm{partition}</tex>. Тогда быстрая сортировка выполнит <tex>\Theta(n^2)</tex> сравнений для массива, построенного таким способом.<br />
<br />
===Способ построить массив с максимальным количеством сравнений при детерминированном выборе опорного элемента===<br />
<br />
Рассмотрим алгоритм построения массива, на котором быстрая сортировка с детерминированным выбором опорного элемента будет делать максимальное (в данном случае {{---}} <tex>\Theta(n^2)</tex>) количество сравнений. Такое число сравнений достигается при разбиении на массивы длиной <tex>1</tex> и <tex>n-1</tex> на каждой итерации. <br />
Создадим массив <tex>a</tex> длины <tex>n</tex>, заполненный элементами типа <tex>pair</tex>. Такой элемент хранит пару значений <tex>(val, key)</tex>, где <tex>val</tex> {{---}} элемент массива, а <tex>key</tex> {{---}} индекс. Изначально <tex>a[i]</tex> элемент имеет вид <tex>(0, i)</tex>.<br />
<br />
Далее, запустим для данного массива алгоритм быстрой сортировки. Сравниваем два элемента типа <tex>pair</tex> по их значениям <tex>val</tex>. На каждом шаге будем выполнять следующие действия: при обращении к <tex>i</tex>-ому элементу в качестве опорного на шаге под номером <tex>k</tex>, присвоим <tex>val = n-k+1</tex> для элемента <tex>a[i]</tex>. Затем выполним шаг сортировки. После завершения работы алгоритма быстрой сортировки, дополнительно отсортируем получившиеся элементы <tex>pair</tex> по значениям <tex>key</tex>. Искомым будет являться массив элементов <tex>val</tex> в соответствующей последовательности. <br />
<br />
Пример для <tex>n = 4</tex>, при последовательном выборе опорных элементов <tex>2, 2, 1, 1</tex>.<br />
<br />
<center><br />
<br />
<br />
{| class="wikitable"<br />
!colspan="8"| Построение массива<br />
<br />
|-<br />
<br />
! Шаг 1.0 || Шаг 1.1 || Шаг 1.2 || Шаг 2.0 || Шаг 2.1 || Шаг 2.2 || Шаг 3.0<br />
|-align="right"<br />
|style="text-align: center;"|1 2 3 4 <br> 0 '''0''' 0 0<br />
| style="text-align: center;"|1 2 3 4 <br> 0 '''4''' 0 0<br />
|style="text-align: center;"|1 4 3 2 <br> 0 0 0 '''4'''<br />
|style="text-align: center;"|1 4 3 2 <br> 0 '''0''' 0 4<br />
|style="text-align: center;"|1 4 3 2 <br> 0 '''3''' 0 4<br />
|style="text-align: center;"|1 3 4 2 <br> 0 0 '''3''' 4<br />
|style="text-align: center;"|1 3 4 2 <br> '''0''' 0 3 4<br />
|-<br />
! Шаг 3.1 || Шаг 3.2 || Шаг 4.0 || Шаг 4.1 || Шаг 4.2 || colspan="2" style="vertical-align: middle;"| Результат<br />
<br />
|-align="right"<br />
|style="text-align: center;"|1 3 4 2 <br> '''2''' 0 3 4<br />
|style="text-align: center;"|3 1 4 2 <br> 0 '''2''' 3 4<br />
|style="text-align: center;"|3 1 4 2 <br> '''0''' 2 3 4<br />
|style="text-align: center;"|3 1 4 2 <br> '''1''' 2 3 4<br />
|style="text-align: center;"|3 1 4 2 <br> '''1''' 2 3 4<br />
| colspan="2" style="text-align: center;vertical-align: middle;" |'''1 2 3 4''' <br> '''2 4 1 3'''<br />
<br />
|-<br />
<br />
!colspan="8" | Итоговый массив<br />
|-<br />
|align="center" colspan="8"|<br />
<font color="red">2 4 1 3</font><br />
|}<br />
</center><br />
<br />
Покажем, почему на данном массиве будет достигаться максимальное время работы быстрой сортировки. На этапе построения мы каждый раз присваивали опорному элементу минимальное значение. Следовательно, при выполнении <tex>\mathrm{quicksort}</tex> алгоритм в качестве опорного всегда будет выбирать наибольший элемент массива (выборка будет производится в том же порядке ввиду детерминированности определения опорного элемента). <br />
Таким образом, так как каждый раз массив разбивается на две части {{---}} большие или равные опорному элементы и меньшие его {{---}} на каждом шаге имеем разбиение на массивы длины <tex>1</tex> и <tex>n-1</tex>, чего мы, собственно, и добивались. При таком выполнении алгоритма происходит <tex>\Theta(n^2)</tex> разделений на два подмассива, и на каждом разделении выполняется <tex>\Theta(n^2)</tex> сравнений. <br />
Следовательно, на данном массиве быстрая сортировка работает за <tex>\Theta(n^2)</tex>.<br />
<br />
===Среднее время работы===<br />
{{<br />
Лемма<br />
|statement=Время работы алгоритма быстрой сортировки равно <tex>O(n \log n)</tex>.<br />
|proof=Пусть <tex>X</tex> {{---}} полное количество сравнений элементов с опорным за время работы сортировки. Нам необходимо вычислить полное количество сравнений.<br />
Переименуем элементы массива как <tex>z_1 \ldots z_n</tex>, где <tex>z_i</tex> наименьший по порядку элемент.<br />
Также введем множество <tex>Z_{ij} = \{z_i, z_{i+1} \ldots z_j\}</tex>.<br />
<br />
Заметим, что сравнение каждой пары элементов происходит не больше одного раза, так как элемент сравнивается с опорным, а опорный элемент после разбиения больше не будет участвовать в сравнении.<br />
<br />
Поскольку каждая пара элементов сравнивается не более одного раза, полное количество сравнений выражается как<br />
<br />
<tex>X = \sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^{n} X_{ij}</tex>, где <tex>X_{ij} = 1</tex> если произошло сравнение <tex>z_i</tex> и <tex>z_j</tex> и <tex>X_{ij} = 0</tex>, если сравнения не произошло.<br />
<br />
Применим к обеим частям равенства операцию вычисления матожидания и воспользовавшись ее линейностью получим<br />
<br />
<tex>E[X] = E\left[\sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^{n} X_{ij}\right] = \sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^{n} E[X_{ij}] = \sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^{n} Pr\{z_i</tex> сравнивается с <tex>z_j\}</tex><br />
<br />
Осталось вычислить величину <tex>Pr\{z_i</tex> сравнивается с <tex>z_j\}</tex> {{---}} вероятность того, что <tex>z_i</tex> сравнивается с <tex>z_j</tex>. Поскольку предполагается, что все элементы в массиве различны, то при выборе <tex>x</tex> в качестве опорного элемента впоследствии не будут сравниваться никакие <tex>z_i</tex> и <tex>z_j</tex> для которых <tex>z_i < x < z_j</tex>. С другой стороны, если <tex>z_i</tex> выбран в качестве опорного, то он будет сравниваться с каждым элементом <tex>Z_{ij}</tex> кроме себя самого. Таким образом элементы <tex>z_i</tex> и <tex>z_j</tex> сравниваются тогда и только тогда когда первым в множестве <tex>Z_{ij}</tex> опорным элементом был выбран один из них.<br />
<br />
<tex>Pr\{z_i</tex> сравнивается с <tex>z_j\} = <br />
Pr\{</tex>первым опорным элементом был <tex>z_i</tex> или <tex>z_j\} = <br />
Pr\{</tex>первым опорным элементом был <tex>z_i\} +<br />
Pr\{</tex>первым опорным элементом был <tex>z_j\} = </tex><br />
<tex> =\dfrac {1}{j-i+1} + \dfrac {1}{j-i+1} = \dfrac {2}{j-i+1} </tex><br />
<br />
<tex> E[X] = \sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^{n} \dfrac {2}{j-i+1} = \sum\limits_{i=1}^{n-1}\sum\limits_{k=1}^{n-i} \dfrac 2{k+1} < \sum\limits_{i=1}^{n-1}\sum\limits_{k=1}^{n-i} \dfrac 2{k} </tex> <tex>= \sum\limits_{i=1}^{n-1}O(\log n) = O(n \log n) </tex><br />
}}<br />
Mатожидание времени работы быстрой сортировки будет <tex>O(n \log n)</tex>.<br />
<br />
==Модификации==<br />
<br />
===Нерекурсивная реализация быстрой сортировки===<br />
Для выполнения быстрой сортировки можно воспользоваться [[Стек | стеком]], в котором в виде сортируемых подмассивов содержится перечень действий, которые предстоит выполнить. Каждый раз когда возникает необходимость в обработке подмассива, он выталкивается из стека. После разделения массива получаются два подмассива, требующих дальнейшей обработки, которые и заталкиваются в стек.<br />
Представленная ниже нерекурсивная реализация использует стек, заменяя рекурсивные вызовы помещением в стек параметров функции, а вызовы процедур и выходы из них — циклом, который осуществляет выборку параметров из стека и их обработку, пока стек не пуст. Мы помещаем больший из двух подмассивов в стек первым с тем, чтобы максимальная глубина стека при сортировке <tex>N</tex> элементов не превосходила величины <tex>\log n</tex>. <br />
'''void''' quicksort(a: '''T'''[n], '''int''' l, '''int''' r)<br />
'''stack'''< '''pair'''<'''int''','''int'''> > s <br />
s.push(l, r)<br />
'''while''' (s.isNotEmpty)<br />
(l, r) = s.pop()<br />
'''if''' (r <tex> \leqslant </tex> l)<br />
'''continue'''<br />
'''int''' i = partition(a, l, r)<br />
'''if''' (i - l > r - i) <br />
s.push(l, i - 1)<br />
s.push(i + 1, r)<br />
'''else'''<br />
s.push(i + 1, r)<br />
s.push(l, i - 1)<br />
<br />
В качестве альтернативного варианта можно использовать обычную рекурсивную версию, в которой вместо того, чтобы после разделения массива вызывать рекурсивно процедуру разделения для обоих найденных подмассивов, рекурсивный вызов делается только для меньшего подмассива, а больший обрабатывается в цикле в пределах этого же вызова процедуры. С точки зрения эффективности в среднем случае разницы практически нет: накладные расходы на дополнительный рекурсивный вызов и на организацию сравнения длин подмассивов и цикла — примерно одного порядка. Зато глубина рекурсии ни при каких обстоятельствах не превысит <tex>\log n</tex>, а в худшем случае вырожденного разделения она вообще будет не более <tex> n </tex> — вся обработка пройдёт в цикле первого уровня рекурсии.<br />
<br />
===Улучшенная быстрая сортировка===<br />
<br />
Выбор медианы из первого, среднего и последнего элементов в качестве разделяющего элемента и отсечение рекурсии меньших подмассивов может <br />
привести к существенному повышению эффективности быстрой сортировки. Функция <tex>\mathrm{median}</tex> возвращает индекс элемента, являющегося медианой трех элементов. После этого он и средний элемент массива меняются местами, при этом медиана становится разделяющим элементом. Массивы небольшого размера (длиной <tex> M = 11</tex> и меньше) в процессе разделения игнорируются, затем для окончания сортировки используется [[Сортировка вставками | сортировка вставками]]. <br />
<br />
'''const int''' M = 10<br />
'''void''' quicksort(a: '''T'''[n], '''int''' l, '''int''' r)<br />
'''if''' (r - l <tex> \leqslant </tex> M)<br />
insertion(a, l, r)<br />
'''return'''<br />
'''int''' med = median(a[l], a[(l + r) / 2], a[r])<br />
swap(a[med], a[(l + r) / 2])<br />
'''int''' i = partition(a, l, r)<br />
quicksort(a, l, i)<br />
quicksort(a, i + 1, r)<br />
<br />
Вообще, можно применять любые эвристики по выбору опорного элемента. Например, в стандартной реализации в Java в качестве разделяющего выбирается средний из 7 элементов, равномерно распределённых по массиву.<br />
<br />
===Быстрая сортировка с разделением на три части===<br />
<br />
Когда в сортируемом массиве имеется множество повторяющихся ключей предыдущие реализации быстрой сортировки можно существенно улучшить. Например массив, который состоит из равных ключей, вовсе не нуждается в дальнейшей сортировке, однако предыдущие реализации продолжают процесс разделения, подвергая обработке все более мелкие подмассивы, независимо от того, насколько большим является исходный файл. <br />
<br />
В основу программы положено разделение массива на три части: <br />
на элементы,меньшие разделяющего элемента <tex> a[l] \ldots a[i]</tex>, <br />
элементы, равные разделяющему элементу <tex>a[i+1] \ldots a[j-1]</tex>,<br />
и элементы большие разделяющего элемента <tex>a[j] \ldots a[r]</tex>. <br />
После этого сортировка завершается двумя рекурсивными вызовами.<br />
<br />
[[Файл:G3.png |400px|thumb|center| Разделение массива <tex> a </tex>]]<br />
<br />
Элементы массива равные разделяющему элементу находятся между <tex> l </tex> и <tex> p </tex> и между <tex> q </tex> и <tex> r </tex>. В разделяющем цикле, когда указатели просмотра перестают изменяться и выполняется обмен значениями <tex> i </tex> и <tex> j </tex>, каждый из этих элементов проверяется на предмет равенства разделяющему элементу. Если элемент, который сейчас находится слева, равен разделяющему элементу, то при помощи операции обмена он помещается в левую часть массива, если элемент, который сейчас находится справа, равен разделяющему элементу, то в результате операции обмена он помещается в правую часть массива. <br />
После того как указатели пересекутся, элементы, равные разделяющему элементу и находящиеся на разных концах массива, после операции обмена попадают в свои <br />
окончательные позиции. После этого указанные ключи могут быть исключены из подмассивов, для которых выполняются последующие рекурсивные вызовы. <br />
<br />
'''void''' quicksort(a: '''T'''[n], '''int''' l, '''int''' r)<br />
'''T''' v = a[r]<br />
'''if''' (r <tex> \leqslant </tex> l)<br />
'''return'''<br />
'''int''' i = l<br />
'''int''' j = r - 1<br />
'''int''' p = l - 1<br />
'''int''' q = r<br />
'''while''' ''(i <tex> \leqslant </tex> j)'' <br />
'''while''' (a[i] < v) <br />
i++<br />
'''while''' (a[j] > v) <br />
j--<br />
'''if''' (i <tex> \geqslant </tex> j)<br />
'''break'''<br />
swap(a[i], a[j])<br />
'''if''' (a[i] == v)<br />
p++<br />
swap(a[p], a[i])<br />
i++<br />
'''if''' (a[j] == v)<br />
q--<br />
swap(a[q], a[j])<br />
j--<br />
swap(a[i], a[r])<br />
j = i - 1<br />
i++<br />
'''for''' ('''int''' k = l; k <tex> \leqslant </tex> p; k++, j--) <br />
swap(a[k], a[j])<br />
'''for''' ('''int''' k = r - 1; k <tex> \geqslant </tex> q; k--, i++) <br />
swap(a[k], a[i]) <br />
quicksort(a, l, j) <br />
quicksort(a, i, r)<br />
<br />
===Параллельная сортировка===<br />
<br />
Еще одной оптимизацией является [[PSRS-сортировка|параллельная сортировка]] на основе быстрой. <br />
Пусть, исходный набор данных расположен на первом процессоре, с него начинается работа алгоритма. Затем исходный массив окажется разделенным на две части, меньшая из которых передастся другому свободному процессору, большая останется на исходном для дальнейшей обработки. Далее обе части опять будут разделены и опять на двух исходных останутся большие части, а меньшие отправятся другим процессорам. В этом заключается ускорение алгоритма. При задействовании всех процессоров, все части параллельно будут сортироваться последовательным алгоритмом.<br />
<br />
===Introsort===<br />
<br />
Для предотвращения ухудшения времени работы быстрой сортировки до <tex>O(n^2)</tex> при неудачных входных данных, также можно использовать алгоритм сортировки Introsort.<br />
Он использует быструю сортировку и переключается на [[Сортировка кучей|пирамидальную сортировку]], когда глубина рекурсии превысит некоторый заранее установленный уровень (например, логарифм от числа сортируемых элементов). Так как после нескольких итераций быстрой сортировки с применением разных эвристик массив с большей вероятностью окажется «почти отсортированным», то пирамидальная сортировка может довольно быстро закончить дело. Также, пирамидальная сортировка хороша тем, что требует <tex>O(1)</tex> дополнительной памяти, в отличие от, например, сортировки слиянием, где потребуется <tex>O(n)</tex> дополнительной памяти.<br />
<br />
==См. также==<br />
* [[Сортировка Шелла]]<br />
* [[Сортировка кучей]]<br />
* [[Сортировка слиянием]]<br />
* [[Timsort]]<br />
* [[Smoothsort]]<br />
* [[PSRS-сортировка]]<br />
<br />
== Источники информации ==<br />
* [[wikipedia:ru:Быстрая сортировка|Википедия {{---}} Быстрая сортировка]]<br />
* [[wikipedia:en:Quicksort|Wikipedia {{---}} Quicksort]]<br />
* [[wikipedia:en:Introsort|Wikipedia {{---}} Introsort]]<br />
* ''Т. Кормен, Ч. Лейзерсон, Р. Ривест'': Алгоритмы: построение и анализ глава 7<br />
* ''Р. Седжвик'': Фундаментальные алгоритмы на С++ части 1 - 4<br />
<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Сортировка]]<br />
[[Категория: Сортировки на сравнениях]]</div>93.175.2.28