Эвристики для поиска кратчайших путей — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «Данная статья - перевод выступления Renato F. Werneck на Microsoft Data Structures and Algorithms School в 2010 году. == П...»)
 
(→‎Проблема поиска кратчайшего пути)
Строка 2: Строка 2:
  
 
== Проблема поиска кратчайшего пути ==
 
== Проблема поиска кратчайшего пути ==
 +
Дано:
 +
* ориентированный граф <tex>G=(V,E)</tex>
 +
* <tex>l(u,v) \geqslant 0</tex>
 +
* <tex>|V|=n, |E|=m</tex>
 +
* отправная точка - вершина <tex>s</tex>, пункт назначения - вершина <tex>t</tex>
 +
 +
Цель: найти кратчайший путь <tex> s \rightsquigarrow t</tex>
 +
 +
Мы будем рассматривать сеть автомобильных дорог:
 +
* <tex>V</tex> - множество населённых пунктов
 +
* <tex>E</tex> - множество дорог
 +
* <tex>l(u,v)</tex> - среднее время, которое занимает проезд по дороге

Версия 14:34, 1 декабря 2013

Данная статья - перевод выступления Renato F. Werneck на Microsoft Data Structures and Algorithms School в 2010 году.

Проблема поиска кратчайшего пути

Дано:

  • ориентированный граф [math]G=(V,E)[/math]
  • [math]l(u,v) \geqslant 0[/math]
  • [math]|V|=n, |E|=m[/math]
  • отправная точка - вершина [math]s[/math], пункт назначения - вершина [math]t[/math]

Цель: найти кратчайший путь [math] s \rightsquigarrow t[/math]

Мы будем рассматривать сеть автомобильных дорог:

  • [math]V[/math] - множество населённых пунктов
  • [math]E[/math] - множество дорог
  • [math]l(u,v)[/math] - среднее время, которое занимает проезд по дороге
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Эвристики_для_поиска_кратчайших_путей&oldid=33850»