а основі алгоритму Дейкстри.
В області розробки ігор широке застосування знаходить алгоритм А *, класичним прикладом його застосування є гра «Lines», «ColorLines», в якій гравцеві необхідно скласти в ряд декілька куль, шлях кулі якраз розраховується за допомогою цього алгоритму. Крім цього А * застосовується в багатьох іграх жанру «RTS» (RealTimeStrategy), для розрахунку траєкторії руху юнітів, його модифікації застосовуються в таких великих проектах як «StarCraft2» і «Warcraft3».
ВИСНОВОК
У цій роботі була висвітлена завдання пошуку найкоротших шляхів на графі, а також розглянуті 3 найбільш популярних алгоритму для її вирішення. Були написані програми, що реалізують алгоритм Дейкстри, і алгоритм Форда-Беллмана.
Список використаних джерел
1. Алексєєв В.Є., Таланов В.А.- Графи. Моделі обчислень. Структури даних, Глава 3.4 Знаходження найкоротших шляхів в графі - Нижній Новгород, 2005;
2. Оліфер В.Г. Оліфер Н.А.- Основи комп'ютерних мереж - Пітер, 2009;
3. «Глосарій теорії графів», lt; # justify gt; ДОДАТКИ
ВИХІДНИЙ КОД РЕАЛІЗАЦІЇ алгоритм Дейкстри
# include stdafx.h
# include lt; iostream gt ;; V=6; (intmatSize [V] [V], intst)
{distance [V], count, index, i, u; m=st + 1; visited [V]; (i=0; i lt; V; i ++) {[i]=INT_MAX ; [i]=false;
} [st]=0; (count=0; count lt; V - 1; count ++)
{min=INT_MAX; (i=0; i lt; V; i ++) (! visited [i] amp; amp; distance [i] lt;=min)
{= distance [i]; index=i;
}=index; [u]=true; (i=0; i lt; V; i ++) (! visited [i] amp; amp; matSize [u] [i] amp; amp; distance [u]!=INT_MAX amp; amp; [u] + matSize [u] [i] lt; distance [i]) [i]=distance [u] + matSize [u] [i];
} lt; lt; Вартість шляху з початкової вершини до інших: t n raquo ;;
for (i=0; i lt; V; i ++) (distance [i]!=INT_MAX) lt; lt; m lt; lt; gt; lt; lt; i + 1 lt; lt; = Raquo; lt; lt; distance [i] lt; lt; endl; lt; lt; m lt; lt; gt; lt; lt; i + 1 lt; lt; = Raquo; lt; lt; маршрутнедоступен lt; lt; endl;
} main ()
{(LC_ALL, Rus ); start, matSize [V] [V]=
{
{0, 1, 4, 0, 2, 0},
{0, 0, 0, 9, 0, 0},
{4, 0, 0, 7, 0, 0},
{0, 9, 7, 0, 0, 2},
{0, 0, 0, 0, 0, 8},
{0, 0, 0, 0, 0, 0}
}; lt; lt; Начальнаявершіна gt; gt; raquo ;; cin gt; gt; start; (matSize, start - 1); ( pause gt; gt; void );
}
ВИХІДНИЙ КОД РЕАЛІЗАЦІЇ АЛГОРИТМУ Беллмана-ФОРДА
# include stdafx.h
# include lt; iostream gt;
# include lt; list gt;
# include lt; stack gt;
# include lt; limits.h gt ;;
{v ;; :( int_v, int_w) {v=_v; ves=_w; } () {Return v; } () {Returnves; }
};
{V; lt; AdjListNode gt; * adj; :( int V); (int u, int v, intves); _ ford (intsrc);
}; :: Graph (intV)
{ gt; V=V;=newlist lt; AdjListNode gt; [V];
} :: addEdge (intu, intv, intves)
{(v, ves); [u] .push_back (node);
} :: bellman_ford (intsrc)
{* dist=newint [V]; (inti=0; i lt; V; i ++) [i]=INT_MAX; [src]=0; (int u=0; u lt; V ; u ++)
{ lt; AdjListNode gt; :: iteratori; (dist [u]!=INT_MAX)
{(i=adj [u] .begin (); i!=adj [u] .end (); ++ i) (dist [i- gt; getV ()] gt; dist [u] + i- gt; getves ())
{[i- gt; getV ()]=dist [u] + i- gt; getves ();
}
}
} lt; lt; Вершина t tРасстояніе lt; lt; endl; (inti=0; i lt; V; i ++)
{ lt; lt; i lt; lt; t t lt; lt; dist [i] lt; lt; t t raquo ;; lt; lt; endl;
}
} main ()
{(LC_ALL, rus ); (5) ;. addEdge (0, 1, - 1) ;. addEdge (0, 2, 4) ;. addEdge (1, 2, 3) ;. addEdge (1, 3, 2) ;. addEdge (1, 4, 2) ;. addEdge (3, 2, 5) ;. addEdge (3, 1, 1) ;. addEdge (4, 3,- 3); s=1; lt; lt; Найкоротші відстані від джерела lt; lt; s lt; lt; n raquo ;;
