
\Section{Алгоритм Дейкстры, А*}{20 сентября}{Илья Ольховский}
	\Subsection{Анонс}
	
	 Алгоритм Дейкстры ищет расстояния от данной вершины $s$ до всех вершин в графах без отрицательных ребер. Наивная реализация работает за $\mathcal{O}(|V|^2)$, но её очень просто ускорить, используя известные нам структуры данных. В общем-то алгоритм Дейкстры - очень похож на известные нам $bfs$, но вершины просматриваются стого в порядке расстояния от стартовой, и засчёт этого каждая вершина просматривается ровно один раз.
	 
	 Я тут всё расписываю максимально подробно. Если кому-то это не надо - смотрите только код, там есть поясняющие комментарии. Если кому-то надо ещё подробнее - пусть обратится к психиатру.
	 
	\Subsection{Алгоритм Дейкстры, преамбула}
	\begin{itemize}
		\item $d[v]$ - минимальное найденное расстояние от стартовой вершины $s$ до вершины $v$. Изначально  полагаем $d[v]=\infty$ $d[s]=0$. $d[v]$ является верхней оценкой на расстояние, то есть $d[v]$ никогда не меньше истинного расстояния. В конце работы алгоритма все $d[v]$ равны истинным расстояниям.
		\item "Обработать вершину $u$" $\;$ значит для всех вершин $v$, смежных с $u$ положить $d[v]=min(d[v],d[u]+w)$, где $w$ - вес ребра из $u$ в $v$ ($relax$ по всем соседям). \textbf{Мы будем обрабатывать вершину только если расстояние до неё уже посчитано окончательно, т.е. соответствует истинному.}
		\item $used[v]$ - флаг, который говорит, что вершина $v$ уже обработана.
		\item $e[v]$ - множетво ребер, исходящих из вершины $v$. $e[v][i].to$ - конец $i$-го ребра, $e[v][i].weight$ - вес $i$-го ребра.
		\item $A$ - множество обработанных вершин.
	\end{itemize}
	 Предыдущие алгоритмы поиска кратчайших путей обрабатывали каждую вершину много раз и работали в худшем случае $\mathcal{O}(VE)$. Алгоритм Дейксты обрабатывает каждую вершину только один раз и поэтому работает заметно быстрее.

	 Идея алгоритма основана на следующем утверждении:
	 
	 \textbf{Лемма:}
	  Пусть $u \notin A$, $d[u]$ минимально среди всех ещё не обработанных вершин. Тогда расстояние $d[u]$ уже посчитано окончательно, то есть соответствует истинному расстоянию. 
	  
	  В самом деле, рассмотрим любой путь $s \leadsto u$. Пусть $v$ - первая не обработанная вершина на этом пути, $w$ - последняя обработанная вершина на этом пути, а $l$ - длина пути.
	  
	  \begin{enumerate}
	  	\item $v=u$. Так как $w$ уже обработана, $l\ge d[w]+e[w\to v]\ge d[u]$.
	  	\item $v\neq u$. Наш путь состоит из двух частей: $s\leadsto v$ и $v\leadsto u$. Длина первой части пути не меньше $d[u]$ - так как в противном случае $d[v]<d[u]$, что противоречит минимальности $d[u]$. Длина второй части пути неотрицательна, так как все ребра в графе неотрицательны. Значит сумма длин двух частей не меньше $d[u]$.
	  \end{enumerate}
	  
	   Получается длина любого пути не меньше $d[u]$. Это, конечно, значит, что $d[u]$ посчитано окончательно.
	   
	  \Subsection{Алгоритм Дейкстры, алгоритм}
	  
	    Из предыдущей леммы сразу видно алгоритм: на каждом шаге берём ещё не обработанную вершину $u$ с минимальным $d[u]$ и обрабатываем. Вот псевдокод:
	    
	    \begin{verbatim}
	    u = s; //изначально у нас одна вершина с правильно посчитанным расстоянием - s
	    while (u != NIL){
	        for(edge in e[u])          //обрабатываем вершину u
	            relax(edge.to, d[u] + edge.weight); 

	        u = find_min(); //находим новую вершину с минимальным d
    	}
	    \end{verbatim}
	    
	        Время работы алгоритма равно $\mathcal{O}(|V| \cdot find\_min + |E| \cdot relax)$.	        
	       Действительно, циклы $for$ перебирают все исходящие ребра всех вершин, их $\mathcal{O}(E)$. А перед каждым вызовом $find\_min$ количество обработанных вершин увеличивается на один, поэтому всего $\mathcal{O}(|V|)$ $find\_min$.
	       
	     \Subsection{relax и find\_min}
	     
	       Время работы алгоритмы зависит от этих двух функций, посмотрим, что мы можем с ними сделать. $relax$ - это, очевидно, $DecreaseKey$, а $find\_min$ - $ExtractMin$ (на множествах ещё не обработанных вершин).
	       \begin{enumerate}
	       	\item \textbf{Дешево, сердито}. Никаких структур, $relax$ просто обновляем $d$, вершину с минимальным $d$ находим простым циклом:
	       	\begin{verbatim}
	       	void relax(int v, int val){
	       	    d[v] = min(d[v], val);
	       	}
	       	
	       	int find_min(){
	           int res = 0; // 0-я вершина - фиктивная, d[0] - бесконечность
	       	   for(int i = 1; i <= n; i++)
	       	       if (!used[i] && d[i] < d[res]) res = i;
	       	   used[res] = true;
	       	   
	       	   return res;
	       	}
	       	\end{verbatim}
	       	       
	       	Плюсы: ничего сложного, если $|E|\approx |V|^2$, то время работы оптимально
	       	
	       	Минусы: если ребер не слишком много, то, очевидно, это слишком медленно
	   \item \textbf{Двоичная куча}
	     Тут некоторые сложности с $DecreaseKey$. Немного поколдовав над двоичной кучей, можно получить доступ к произвольным элементам, и тогда будет достаточно просто изменить нужный элемент и просеять его вверх. Но, сделав так, мы лишимся огромного плюса двоичной кучи: она есть в STL.
	    
	     Поэтому будем делать по другому. В куче будем хранить пары $(u, d[u])$.
	     Вместо того, чтобы обновлять элемент, будем добавлять новый. То есть $relax$ выглядит так:
	     
	     \begin{verbatim}
	     void relax(int u, int val){	
		         Insert( {u, val} );
		     }
	     \end{verbatim}
	     A $find\_min$ выглядит так:
	     \begin{verbatim}
	     while (used[u]) u = ExtractMin()->first;
	     used[u] = true;
	     \end{verbatim}

		В куче теперь будут находиться лишние элементы. Но их не более чем $\mathcal{O}(|E|)$, потому что общее количесво вызовов $relax$ равно $\mathcal{O}(|E|)$. Действительно, каждая вершина $u$ обрабатывается один раз и порождает $degree(u)$ вызовов $relax$.
		
		 $|E|=\mathcal{O}(|V|^2)$, поэтому все запросы к куче будут по прежнему выполняться за $\mathcal{O}(\log |V|)$.
		
		 Всего запросов будет $\mathcal{O}(|E|)$. Поэтому общее время работы будет $\mathcal{O}(|E|\log |V|)$
	     
	     Плюсы: не надо писать ничего лишнего, относительно хорошее время
	     
	     Минусы: время можно ещё улучшить
	 \item \textbf{k-Heap}
	 
	  Весьма достойный вариант в случае критичности времени. Всё то же, что и в предыдущем пункте. Но раз уж всё равно в STL нет, можно не жульничать и делать $DecreaseKey$ честно, поддерживая доступ к прозвольным элементам. 
	  
	   $DecreaseKey$ - реализуется через $SiftUp$, $ExtractMin$ - через $SiftDown$. Так как 
	  $DecreaseKey$ у нас $\mathcal{O}(|E|)$ штук, а $ExtractMin$ - $\mathcal{O}(|V|)$, то нам как раз выгодно, чтобы $SiftUp$ работал быстро, а $SiftDown$ можно немного замедлить. Поэтому $k-Heap$ выигрывает перед обычной двоичной кучей.
	  
	  Плюсы: хорошее время на практике: $\mathcal{O}(|E|\log_k |V| + k|V|\log_k |V|)$
	  
	  Минусы: нет в STL, теоретически можно ещё быстрее
	  
	  \item \textbf{Фибоначчиева куча}
	   Используя Фибоначчиеву кучу, можно добиться асимптотики $\mathcal{O}(|V|\log |V| + |E|)$. Это в некотором смысле предел для алгоритма Дейкстры. 
	   
	    Мы не можем не просмотреть всех ребер, поэтому время работы не может быть меньше $\mathcal{O}(|E|)$. Кроме того, в алгоритме Дейкстры мы обрабатываем вершины в порядке сортировки по расстоянию. В общем случае отсортировать быстрее, чем за $\mathcal{O}(|V|\log |V|)$ мы не можем.
	    
	    То есть, не пользуясь никакой дополнительной информацией (например, что веса ребер - целые числа от 1 до С), невозможно реализовать алгоритм Дейкстры быстрее.
	    
	    Плюсы: оптимальная асимптотика
	    
	    Минусы: все мы знаем, насколько на самом деле быстры Фибоначчиевы кучи...
	 
	 
	    
	\end{enumerate}
	
	\Subsection{A*, преамбула}
	
	 Модифицируем алгоритм Дейкстры, чтобы он быстро работал на реальных (случайных, с некоторыми дополнительными свойствами) графах. Часто нам нужно найти расстояние только между двумя вершинами, а не от одной до всех остальных.
	 
	  В этом случае можно сделать так, что алгоритм будет не равномерно находить расстояния до всех вершин вокруг стартовой, а как бы двигаться в сторону нужной вершины, не уходя далеко в сторону. Тогда мы сможем найти нужное расстояние раньше.
	  
	   Для этого нам понадобится функция $f$ - оценка расстояния до конечной вершины.
	   
	    То есть пусть мы ищем кратчайший путь от вершины $s$ до вершины $t$. $d(u, v)$ - расстояние между вершинами $u$ и $v$ Тогда $f(v)$ - оценка на $d(v, s)$, которая обладает следующими свойствами:
	    \begin{enumerate}
	    	\item \textbf{Неотрицательность} $f(v)\ge 0$
	    	\item \textbf{Оценка снизу} $f(v)\le d(v, t)$
	    	\item \textbf{Неравенство треугольника} $\forall a, b$, связанных ребром  $f(b) \le f(a) + w$, где $w$ - вес ребра.
	    \end{enumerate}
	    
	     Функция $f$ подбирается, исходя из задачи. Если граф расположен в пространстве или на плоскости (например, города и дороги), то там существует естественная функция $f$ - эвклидово расстояние. Легко проверить, что все три свойства в этом случае выполняются. Тогда алгоритм Дейкстры будет пытаться продвигаться именно по направлению к нужной точке.
	    	
    	\Subsection{A*, алгоритм}
    	
    	А* делает в общем-то то же, что и алгоритм Дейкстры, но рассматривает вершины не в порядке $d$, а в порядке $d + f$. В остальном всё будет происходить точно так же. Все обозначения означают то же, что и раньше.  
    	
    	\textbf{Лемма:}  Пусть $u \notin A$, $d[u] + f[u]$ минимально среди всех ещё не обработанных вершин. Тогда расстояние $d[u]$ уже посчитано окончательно.
    	
    	\textbf{Док-во:} Рассмотрим произвольный путь $s \leadsto u$. В общем случае путь может заходить в $A$ и выходить оттуда несколько раз. Но так как до любой обработанной вершины $w$ существует кратчайший путь $s \leadsto w$ только по обработанным вершинам, мы можем считать, что путь $s \leadsto u$ никогда не возвращается в $A$ (наша цель сделать путь как можно короче).
    	
    	 Пусть $v_1$ - первая необработанная вершина на пути, $v_2$ - вторая, $v_k$ - предпоследняя. $w_i$ - вес ребра между $v_i$ и $v_{i + 1}$ (считаем, что $v_{k+1}=u$).
    	 \begin{enumerate}
    	 	\item   	 	
    	 	По неравенству треугольника для $f$:
				    	   $$f[v_k]\le f[u]+w_k$$
				    	   $$f[v_{k-1}] \le f[v_k] + w_{k-1}\le f[u]+w_{k-1}+w_k$$
				    	   $$\cdots$$
				    	   $$f[v_1]\le f[u]+w_0+w_1+\ldots w_k$$
			\item Мы выбрали $u$ так, что $d[u]+f[u]$ минимально среди всех необработанных вершин. Так как весь путь $s\leadsto v_1$ проходит по обработанным вершинам длина этого пути не меньше $d[v_1]$.
			
			Тогда длина всего пути равна:
			$$l=d[v_1]+w_1+\ldots w_k$$
			$$l+f[u]=d[v_1]+(w_1+\ldots w_k+f[u])\ge d[v_1]+f[v1]\ge d[u]+f[u]$$
			$$l\ge d[u]$$
		\end{enumerate}
		 Итак, мы рассмотрели произвольный путь и поняли, что его длина не меньше $d[u]$. Это значит, что $d[u]$ посчитано окончательно.
		 	
		 \Subsection{A*, эпилог}
		 
		  Чтобы получить $A*$ из Дейкстры, надо добавить очень мало. А именно, $relax$ теперь выглядит так:
		  \begin{verbatim}
		  void relax(int u, int val){
		      Insert( {u, f[u] + val} );
		  }
		  \end{verbatim}
		    А главный цикл - так:
		     \begin{verbatim}
		     u = s; //изначально у нас одна вершина с правильно посчитанным расстоянием - s
		     while (u != NIL && u != t){
		         for(edge in e[u])          //обрабатываем вершину u
		             relax(edge.to, d[u] + edge.weight); 
		     
		         u = find_min(); //находим новую вершину с минимальным d + f
		     }
		     \end{verbatim}
		    
		   Тут предполагается использование некоторой кучи, и мы по-прежнему вставляем новые элементы вместо того, чтобы обновлять старые.
		   
		    Время работы $A*$, очевидно, асимптотически такое же, как у Дейкстры. Однако на реальных графах $A*$ работает намного быстрее, так как не просматривает эвристически неоптимальные маршруты. Всё это, конечно, в предположении, что функция $f$ считается за $\mathcal{O}(1)$
		  
		
    	 	
    	
    	
		       
	     
	      

	 
	 
