Comments 35
UFO just landed and posted this here
UFO just landed and posted this here
Оказалось, что на самом деле очень легко писать Дейкстру за O(n * log(n) + m * log(n))!
Откуда вы взяли лишнее log(n) при m? Стандартная сложность этого алгоритма при использовании кучи — O(m + n* log(n)).
Ну и да, легко это писать, когда за вас куча реализована фреймворком, а вот когда вы эту кучу делаете ручками, все не так радужно.
На интуитивном уровне понятно, что если до какой-то вершины путь сейчас минимальный, то еще меньше сделать его мы не сможем.
А вот и нет, интуитивно понятно, но неверно. Точнее, верно только в том случае, если вы соблюдаете ограничение применимости этого алгоритма, про которое в посте ни слова.
Откуда вы взяли лишнее log(n) при m? Стандартная сложность этого алгоритма при использовании кучи — O(m + n* log(n)).
Если использовать фибоначчиеву кучу, то да. При использовании обычной кучи, асимптотика именно такая, как я показал.
А вот и нет, интуитивно понятно, но неверно. Точнее, верно только в том случае, если вы соблюдаете ограничение применимости этого алгоритма, про которое в посте ни слова.
Согласен, это верно только при не отрицательных весах ребер, сейчас допишу об этом в посте.
Ну и да, легко это писать, когда за вас куча реализована фреймворком, а вот когда вы эту кучу делаете ручками, все не так радужно.
Не согласен. Кучу писать совсем не сложно.
Продемонстрируете?
Вы либо троллите, либо действительно не знаете. Буду исходить из второго и добавлю реализацию кучи в пост.
Собственно, вот полная реализация:
Если не считать 13 строк описаний структур, то вся функция занимает 50 строк, из них 30 — на приоритетную очередь (с обратными ссылками и возможностью замены весов), 20 — на остальной алгоритм. Так что действительно, не так уж сложно. Тем более, что максимальная длина в данном случае заранее известна. Конечно, если new[] считать частью фреймворка, то жизнь будет несколько сложнее, но в ситуациях, когда нет malloc, у нас максимальные размеры структур фиксированы. В крайнем случае, два массива можно будет захватить на стеке.
Код
struct XVert{
int backidx;
int backway;
double dist;
};
struct Edge{
int idx;
double dist;
};
struct Vert{
int NEdges;
Edge *Edges;
};
struct Graph{
int NV;
Vert *Verts;
};
double Dejkstra(Graph *G,int Start,int End){
int NV=G->NV;
int LQ=NV;
XVert *Verts=new XVert[NV];
Edge *Que=new Edge[NV];
for(int i=0;i<NV;i++){
int j=(i==0 || i==Start) ? Start-i : i;
Verts[i].dist=100;
Verts[i].backidx=j;
Verts[i].backway=-1;
Que[i].dist=100;
Que[i].idx=j;
}
Verts[Start].dist=Que[0].dist=0;
Verts[Start].backway=-1;
for(;;){
Edge top=Que[0];
int v0=top.idx;
if(top.idx==End) break;
Edge btm=Que[--LQ];
int a=0,b;
while((b=2*a+2)<=LQ){
if(b==LQ || Que[b].dist>Que[b-1].dist) b--;
if(Que[b].dist>=btm.dist) break;
Que[a]=Que[b];
Verts[Que[a].idx].backidx=a;
a=b;
}
Que[a]=btm;
Verts[btm.idx].backidx=a;
Verts[top.idx].backidx=-1;
for(int k=0;k<G->Verts[v0].NEdges;k++){
Edge *e=G->Verts[v0].Edges+k;
double d=top.dist+e->dist;
int h=Verts[e->idx].backidx;
if(h<0 || d>=Verts[e->idx].dist) continue;
Verts[e->idx].dist=d;
Verts[e->idx].backway=v0;
Edge current=Que[h];
while(h>0){
int h1=(h-1)/2;
if(Que[h1].dist<d) break;
Que[h]=Que[h1];
Verts[Que[h].idx].backidx=h;
h=h1;
}
current.dist=d;
Que[h]=current;
Verts[e->idx].backidx=h;
}
}
double res=Que[0].dist;
delete[] Verts;
delete[] Que;
return res;
}
Если не считать 13 строк описаний структур, то вся функция занимает 50 строк, из них 30 — на приоритетную очередь (с обратными ссылками и возможностью замены весов), 20 — на остальной алгоритм. Так что действительно, не так уж сложно. Тем более, что максимальная длина в данном случае заранее известна. Конечно, если new[] считать частью фреймворка, то жизнь будет несколько сложнее, но в ситуациях, когда нет malloc, у нас максимальные размеры структур фиксированы. В крайнем случае, два массива можно будет захватить на стеке.
Там в двух местах осталось dist=100 (со времени отладки) — заметил слишком поздно, его надо заменить на максимальное значение double.
Пойнт не столько в размере, сколько в «концептуальной сложности». По моему опыту, написать кучу хотя бы на основе бинарного дерева сложнее, чем просто реализовать алгоритм Дийкстры — больше неочевидных мест, где можно ошибиться.
(ну и будем честными, я все-таки не понял из вашего кода, как именно вы делаете замену веса, точнее — поиск элемента для замены, но это сказывается мое неумение читать terse code)
(ну и будем честными, я все-таки не понял из вашего кода, как именно вы делаете замену веса, точнее — поиск элемента для замены, но это сказывается мое неумение читать terse code)
Поле XVert.backidx — текущий индекс данной вершины в массиве, на котором реализована куча (он меняется при каждом перемещении элемента кучи вверх или вниз). Поэтому, при замене веса я сразу беру индекс в массиве кучи, и начинаю двигать элемент с этим индексом вверх (если надо).
Операции добавления вершины в кучу мне не понадобилось вообще — куча сразу создаётся со всеми вершинами, имеющими максимальный вес (кроме стартовой, у которой вес равен нулю — она кладётся в начало массива). Это приведёт к некоторой потере эффективности в ситуации, когда надо найти путь между очень близкими вершинами в очень большом графе (на первый вход в вершины потратится k*log(V) операций вместо k*log(k), где k — число вершин, которые нужно просмотреть), но код получается компактнее.
Операции добавления вершины в кучу мне не понадобилось вообще — куча сразу создаётся со всеми вершинами, имеющими максимальный вес (кроме стартовой, у которой вес равен нулю — она кладётся в начало массива). Это приведёт к некоторой потере эффективности в ситуации, когда надо найти путь между очень близкими вершинами в очень большом графе (на первый вход в вершины потратится k*log(V) операций вместо k*log(k), где k — число вершин, которые нужно просмотреть), но код получается компактнее.
Ну и да, легко это писать, когда за вас куча реализована фреймворком, а вот когда вы эту кучу делаете ручками, все не так радужно.
Реализация приоритетной очереди — 25-30 строк, ненамного больше остальной части алгоритма.
Откуда вы взяли лишнее log(n) при m?
Заметим, что в статье ни разу не говорилось, что такое n и m. Можно догадаться, что одно из них — вершины, а другое — рёбра, но что есть что — непонятно.
При данной реализации — когда вершины со старыми весами остаются в куче до тех пор, пока не дойдёт очередь до их старого веса — размер кучи может доходить до O(E), где E — число рёбер. Например, так будет для графа с вершинами 1..V, где d(m,n)=2*abs(m-n)-1, и мы ищем путь от 1 до n. Каждый новый улучшенный экземпляр вершины придётся положить в кучу, на это потребуется до E*log(E) операций.
Кстати, а где в вашем алгоритме замена весов ранее вставленных вершин? Иными словами, если на шаге один в кучу добавлена вершина u с весом 15, а на шаге три в кучу добавлена эта же вершина с весом 3 — сколько записей о вершине u будет в куче?
В посте описано. Нужно не проводить релаксацию, если из кучи достали неактуальный путь.
При такой реализации, как уже написано выше, вы получаете высоту кучи в O(log|E|), что для полного графа равно O(log(|V|2) (это в расчете на то, что дублирующиеся ребра вы оптимизируете на предварительном этапе), против O(log(|V|) в стандартной реализации.
O(log|E|), что для полного графа равно O(log(|V|^2))… против O(log(|V|)
Хорошая попытка :)
К счастью, O(log (|V|^2)) = O(2*log |V|) = O(log |V|), так что мы теряем не более, чем константу (а может быть, и выигрываем — ведь нам не нужно поддерживать функцию уменьшения веса).
Память на кучу проигрываем, причём сильно — это верно. Если граф у нас не хранится в памяти, а как-то вычисляется, то это может быть плохо.
O(log (|V|^2)) = O(2*log |V|) = O(log |V|),
Если так считать, то можно ограничиться стэнфордским определением асимптотики алгоритма в O(|E| log |V|) и не мучиться разницей между разными реализациями кучи.
(собственно, наивная функция уменьшения веса — 2*log(n), потому что сводится к удалению и вставке, оба из которых реализуемы на двоичной куче за log(n)),
1) Между O(2*log(|V|) и O(log(|E|*log(|V|) есть небольшая разница: 2 это константа, а log(|E|) — нет. Определение O(f(x)) даётся так, что изменение f(x) в константу раз на результат не влияет. А если f(x) умножается на величину, зависящую от x, то класс алгоритмов и их асимптотика может измениться.
2) Операции «удаление произвольного элемента» в наивной реализации кучи не предусмотрено — она бы потребовала просмотра всей кучи. А если мы умеем быстро искать элемент, то изменить его вес так же просто, как добавить новый: ведь добавление элемента в кучу фактически реализуется как добавление его в конец массива с бесконечным весом плюс последующее уменьшение веса.
2) Операции «удаление произвольного элемента» в наивной реализации кучи не предусмотрено — она бы потребовала просмотра всей кучи. А если мы умеем быстро искать элемент, то изменить его вес так же просто, как добавить новый: ведь добавление элемента в кучу фактически реализуется как добавление его в конец массива с бесконечным весом плюс последующее уменьшение веса.
Между O(2*log(|V|) и O(log(|E|*log(|V|)
А откуда вы взяли log(|E|*log(|V|))?
А если мы умеем быстро искать элемент, то изменить его вес так же просто, как добавить новый
Не совсем — нам надо не забыть восстановить инварианты по отношению к тому месту, откуда мы «вытаскиваем» элемент. Это не сложно, но тоже требует аккуратности. Собственно, здесь и накапливается сложность (не алгоритмическая) реализации кучи.
Когда мы добавляем новый элемент (или удаляем минимум), то при реализации через массив у нас меняется положение части элементов в массиве. И для них всё равно приходится отслеживать изменение информации для поиска. Если вы знаете способ реализовать кучу с удалением произвольного элемента, в котором добавление операции изменения веса (отличной от удаления+вставки) приводит к заметному усложнению реализации — было бы интересно взглянуть.
Ну, как я это в свое время реализовывал: при вставке мы получаем bubble-up. При снятии верха — bubble-down. При вытаскивании элемента из середины — не важно, для удаления или для перевесовки, — нужно сделать либо то, либо другое, в зависимости от отношения весов элементов. С моей точки зрения (ну и банально по тому, сколько времени я потратил на отлов багов) вот это «то либо другое» и есть усложнение реализации.
Но я, правда, говорю про generic heap, который просто структура данных, отвязанная от алгоритма.
Но я, правда, говорю про generic heap, который просто структура данных, отвязанная от алгоритма.
При вытаскивании элемента из середины — не важно, для удаления или для перевесовки, — нужно сделать либо то, либо другое, в зависимости от отношения весов элементов.
Дешевле всего вызвать и то и другое. По количеству операций получается не больше операций чем если проверять соотношение весов и вычислять направление «всплытия»
«И то и другое» — вы имеете в виду удаление и последующую вставку с новым весом? В случае бинарной кучи это безумно дорого. Обычно при уменьшении веса объект либо не надо двигать вообще (он уже тяжелее своего родителя), либо его надо переставить на 1-2 ступеньки вверх. И сравнивать на каждом этапе только с родителем. А удаление+вставка — это надо сначала утопить самый тяжелый объект, вставленный на место удалённого (2*log(K) сравнений, где K — положение нашего объекта, считая снизу), а потом — всплыть наш объект с самого последнего места (ещё не менее log(K) сравнений). Если мы уменьшаем вес объекта, близкого к вершине, то потребуется до 3*log(N) сравнений (и 2*log(N) перемещений), когда хватило бы совсем маленьких значений.
И то и другое — это вызвать метод всплытия а потом метод утопления. Потому что когда вы удаляете объект из середины, вы меняете удаляемый объект с последним элементом, после этого элемент нужно расположить на нужном уровне. И этот уровень может быть как выше так и ниже. При этом один из вызовов в данном случае делает только проверку что перемещать объект не надо и выходит.
Согласен. Редкая ситуация, но может случиться.
На самом деле эта ситуация не так редка как может показаться. Она может возникнуть, когда последний элемент находится в другой ветке относительно элемента который мы удаляем.
Собственно, когда я реализовывал этот самый алгоритм Дийкстры, я при реализации «кучи» сделал только утопление, считая, что если я поменял с последним элементом, этот элемент должен потонуть обратно вниз. Потом сутки пытался понять почему у меня с вероятностью 70% получается неверный результат.
Собственно, когда я реализовывал этот самый алгоритм Дийкстры, я при реализации «кучи» сделал только утопление, считая, что если я поменял с последним элементом, этот элемент должен потонуть обратно вниз. Потом сутки пытался понять почему у меня с вероятностью 70% получается неверный результат.
Собственно, когда я реализовывал этот самый алгоритм Дийкстры, я при реализации «кучи» сделал только утопление, считая, что если я поменял с последним элементом, этот элемент должен потонуть обратно вниз. Потом сутки пытался понять почему у меня с вероятностью 70% получается неверный результат.
+1
Собственно, именно поэтому я говорю, что в реализации алгоритма Дийкстры с кучей куча — самое сложное место.
Я просто оставлю это здесь: e-maxx.ru/algo/dijkstra_sparse.
Вообще e-maxx.ru — замечательный сайт по алгоритмам, автор которого даже присутствует на хабре.
Вообще e-maxx.ru — замечательный сайт по алгоритмам, автор которого даже присутствует на хабре.
Sign up to leave a comment.
От обхода в ширину к алгоритму Дейкстры