Тражење путање

С Википедије, слободне енциклопедије
Еквивалентне путање између А и Б у 2Д окружењу

Тражење путање компјутерском апликацијом је проналазак најкраће путање између две тачке. То је практичнија варијанта решавања лавирината. Ово поље истраживања ослања се на Дајкстрин алгоритам за проналажење најкраће путање на тежинском графу .

Алгоритми[уреди | уреди извор]

У суштини, метод тражења путање тражи граф почевши од једног чвора и наставља претраживање на суседне чворове док се не пронађе циљни чвор, са намеом да се пронађе најкраћи пут. Иако претраживања графа, као што су претрага у ширину налази пут за дато време, друге методе које "истражују" граф, имају тенденцију да раније стигну до одредишта. Аналогија би била да особа хода по соби, унапред испитује сваки могући пут, особа обично хода у правцу дестинације и одступа од путање да би избегла препреке, и да одступа што је мање могуће.

Два осбновна проблема тражења путање су (1) да пронађе пут између два чвора у графу; и (2) пронаћи оптимално најкраћи пут до проблема. Основни алгоритми као што су претрага у ширину и претрага у дубину тражења одредишта је први проблем исцрпљивања свих могућности; почев од датог чвора, они прелазе преко свих могућих путева док не стигну до циљног чвора. Ови алгоритми имају , или линеарно време, где је V број чворова и E број грана између чворова.

Што је компликованији проблем проналажење путање је оптималнији. Детаљан приступ у овом случају познат као Белман-Фордов алгоритам, који даје сложеност времена , или квадратно време. Међутим, није неопходно испитивати све могуће путеве како би се пронашао један оптималан. Алгоритми као што су A* алгоритам и Дајкстрин алгоритам стратешки елиминишу путању, хеуросточки или путем динамичког програмирања. Елиминисање немогућих путева, ови алгоритми могу да постигну мању сложеност времена .[1]

Наредни алгоритми су међу најбољим општим алгоритмима који раде на графу без предпроцесирања. Међутим, у практичном усмерена-путања систему, чак и боље време сложености може постићи алгоритам који може пре-процеса постићи боље перформансе.[2]. Један такав алгоритам је контракција хијерархије.

Дајкстрин алгоритам[уреди | уреди извор]

Уобичајени пример графа заснован на алгоритму тражења путање је Дајкстрин алгоритам. Овај алгоритам почиње од почетног чвора и "отвореног скупа" кандидата чворова. На сваком кораку, чвор н отвореном скупу са најмањом удаљености се од самог почетка испитуе. Чвор је означен као "затворен", а сви суседни чворови се додају на отворен скуп ако нису већ разматрани. Овај процес понавља се све док се не пронађе пут до циља. Пошто су чворови са најмањом удаљености први пут прегледани, први пут је наћи, пут до њега ће бити најраћи пут.[3]

Дајкстрин алгоритам не постоји ако постоји грана са негативном тежином. Хипотетички, ситуације у којој чворови A, B, и C формирају повезан неусмерен граф са гранама AB = 3, AC = 4, и BC = −2, оптималност пута од A до C кошта 1, а оптималност пута од A до B кошта 2. Дајкстрин алгоритам почев од A ће прво испитати B, јер је он најближи. То ће доделити трошкак 3 до њега, и означити је затвореном, што значи да његова цена никада неће бити преиспитана. Дакле, Дајкстрин не може проценити гране са негативним тежинама. Међутим, пошто за многе практичне сврхе никада неће бити грана са негативним тежинама, Дајкстрин алгоритам је углавном погодан за потребе тражења путање.

А* алгоритам[уреди | уреди извор]

А* је варијанта Дајкстрин алгоритма који се најчешће користи у играма. А* додељује тежину сваком отвореном чвору на тежини гране тог чвора плус приближно растојање између тог чвора и завршне обраде. Ово приближно растојање је хеуристика, и представља најмању могућу удаљеност између тог чвора и краја. Ово омогућава елиминисање дугих путева када се нађе почетни пут. Ако постоји пут дужине x између почетног и крајњег чвора, као и минимална раздаљина између чвора и крајњег чвора већа од x, тај чвор не мора бити прегледан.[4]

А* користи хеуристику да побољша однос са Дајкстрин алгоритмом. Када је хеуристика процењена на нулу, А* је еквивалентан са Дајкстрин алгоритмом. Хеуристичка процена се повећава и приближава правој раздаљини, А* наставља да проналази оптималне путање, али ради брже (на основу испитивања мање чворова). Када је хеуристичка вредност тачно удаљена од одредишта, А* испитује најмање чворове. (Међутим, генерално је непрактично да се напише хеуристичка функција која увек израчунава праву путању). Кад се вредност хеуристике повећава, А* истражује мање чворова, али не гарантује оптималну путању. У многим апликацијама, као што су видео игре, то је прихватљиво па чак и пожељно, како би задржали да алгоритам ради брзо.

Узорак алгоритма[уреди | уреди извор]

Ово је прилично једноставан и лак за разумевање алгоритам тражења путање за мапе базиране на плочицама. За почетак, имате мапу, почетак координата и дестинацију координата. Мапа ће изгледати овако, X је зид, S почетак, 0 је крај и постоји отворени простор, бројеви дуж врха и десне грае су колоне и редови бројева: 

  1 2 3 4 5 6 7 8
X X X X X X X X X X
X _ _ _ X X _ X _ X 1
X _ X _ _ X _ _ _ X 2
X S X X _ _ _ X _ X 3
X _ X _ _ X _ _ _ X 4
X _ _ _ X X _ X _ X 5
X _ X _ _ X _ X _ X 6
X _ X X _ _ _ X _ X 7
X _ _ O _ X _ _ _ X 8
X X X X X X X X X X

Прво направити листу координата, коју ћемо користити као ред. Ред ће бити покренут са једном координаом, крај координата. Свака координата ће имати привржену контра променљиву (сврха овога ће ускоро постати евидентна). Тако да ред почиње са ((3,8,0)).

Затим, идите кроз сваки елемент у реду, укључујући и елементе додате на крају током алгоритма, и за сваки елемент, урадити следеће:

  1. Направити листу са 4 суседне ћелије, са контра променљивом актуелног елемента бројача променљиве + 1 (у нашем примеру четири ћелије су ((2,8,1),(3,7,1),(4,8,1),(3,9,1)))
  2. Проверити све ћелије у свакој листи за следећа два услова:
    1. Ако је ћелија зид, уклоните га из листе
    2. Ако постоји елемент у главној листи са истим координатама и један једнак или већи бројач, уклоните га из листе
  3. Додај све преостале ћелије на листи до краја главне листе
  4. Прелазак на следећу ставку на листи

Тако, након потеза 1, листа елемената је ово: ((3,8,0),(2,8,1),(4,8,1))

  • Након 2 потеза:((3,8,0),(2,8,1),(4,8,1),(1,8,2),(4,7,2))
  • Након 3 потеза:(...(1,7,3),(4,6,3),(5,7,3))
  • Након 4 потеза: (...(1,6,4),(3,6,4),(6,7,4))
  • Након 5 потеза: (...(1,5,5),(3,5,5),(6,6,5),(6,8,5))
  • Након 6 потеза: (...(1,4,6),(2,5,6),(3,4,6),(6,5,6),(7,8,6))
  • Након 7 потеза: ((1,3,7)) - проблем решен, завршити ову фазу алгоритма - на уму да ако имате више јединица јуре исти циљ (као у многим играма - крај за почетак покренути пристпу алгоритмима намерно да ту олакша), можете наставити све док се читава мапа не пренесе, док се не достигне да су све јединице или контра граница.
Сада, мапа бројача на мапи, узима ово: 

  1 2 3 4 5 6 7 8
X X X X X X X X X X
X _ _ _ X X _ X _ X 1
X _ X _ _ X _ _ _ X 2
X S X X _ _ _ X _ X 3
X 6 X 6 _ X _ _ _ X 4
X 5 6 5 X X 6 X _ X 5
X 4 X 4 3 X 5 X _ X 6
X 3 X X 2 3 4 X _ X 7
X 2 1 0 1 X 5 6 _ X 8
X X X X X X X X X X

Сада се креће од S (7) и иде на оближње ћелије са најмањим бројем (непроверене ћелије се могу преместити). Пут је (1,3,7) -> (1,4,6) -> (1,5,5) -> (1,6,4) -> (1,7,3) -> (1,8,2) -> (2,8,1) -> (3,8,0). У случају да су два броја подједнако мала (нпр. S је био (2,5))), одабрати случајан смер - дужине су исте. Алгоритам је сада завршен.

У видео играма[уреди | уреди извор]

Тражење путање у контексту видео игара тиче се начина на који покретно лице проналази пут око препреке; најчешћи контекст стратегија у реалном времену игре (у којој играч усмерава јединице око простора који садржи препреке), али ови облици се могу наћи у већини модерних игара. Порастао је значај тражења путање као игре и њихове околине су постале сложеније, и као резултат тога, многи AI софтверски пакети су развијени да реше проблем.

Игре стратегије обично садрже велике површине отворених терена који су често релативно једноставни за прелажење, мада је заједничко за више од једне јединице да се прелази истовремено: ово ствара потребу за различитим и често значајно више сложеним алгоритмом да би се избегле гужве у саобраћају на закрченим местима на терену, или када јединице долазе у контакт једна са другом. У стратешким играма са картама нормално је подељен на плочице, као чворови у алгоритму тражења путање.

Више отворених завршних структура као што су Пуцачка игра из првог лица често имају више затворених (или мешавину затворених и отворених) области које нису само подељене у чворове, и која је дала поводе за коришћење навигације мрежа. Они су конструисани представљањем чворова у свету игара који чувају детаље који су чворови приступачни из њега.

Алгоритми који се користе за тражење путање[уреди | уреди извор]

  • A* алгоритам
  • Дајкстрин алгоритам, неинформисани, мање моћни посебан случај A* алгоритма
  • D*, породица постепеног хеуристичког претраживања алгоритама за проблеме у којима се разликују ограничења током времена или нису у потпуности познати када агент први пут планира своју путању
  • Алгоритам било који угао планирања путање, породица алгоритама за планирање путање које нису ограничене на кретање дуж грана у претрази графа, намењен да буде у стању да преузме угао и на тај начин пронађе краће путање.

Референце[уреди | уреди извор]

  1. ^ „7.2.1 Single Source Shortest Paths Problem: Dijkstra's Algorithm[[Категорија:Ботовски наслови]]”. Архивирано из оригинала 04. 03. 2016. г. Приступљено 26. 01. 2016.  Сукоб URL—викивеза (помоћ)
  2. ^ Delling, D.; Sanders, P.; Schultes, D.; Wagner, D. (2009). "Engineering route planning algorithms". Algorithmics of Large and Complex Networks: Design, Analysis, and Simulation. Springer. стр. 117–139. . doi:10.1007/978-3-642-02094-0_7.  Недостаје или је празан параметар |title= (помоћ)
  3. ^ 5.7.1 Dijkstra Algorithm
  4. ^ Introduction to A* Pathfinding
Преузето из „https://sr.wikipedia.org/w/index.php?title=Тражење_путање&oldid=27754914”