Algorytm A*: Różnice pomiędzy wersjami
| [wersja przejrzana] | [wersja nieprzejrzana] |
Usunięta treść Dodana treść
m Zamieniam przestarzały tag 'source' na 'syntaxhighlight' |
m →Cechy algorytmu A*: jęz., drobne merytoryczne Pojęcie "zbiór zamknięty" które było użyte, nijak się ma do matematycznego znaczenia tego pojęcia, autorowi chodziło o zbiór "closed_set" z kodu, który oznacza zbiór przetworzonych już wierzchołków. Wygląda, że ktoś to przetłumaczył z języka angielskiego bez głębszej analizy lub użył automatycznego tłumacza. Któryś raz już ten błąd spowodował, że musiałem się dłużej nad tym zastanawiać, więc zgłaszam poprawkę. |
||
Linia 70:
== Cechy algorytmu A* ==
Algorytm A* jest kompletny – w każdym przypadku znajdzie optymalną drogę i zakończy działanie, jeśli taka droga istnieje.
Jeśli heurystyka <math>h</math> jest dopuszczalna (czyli nigdy nie zawyża wartości wagi na ścieżce między dowolnymi dwoma wierzchołkami) to algorytm A* jest dopuszczalny, o ile w algorytmie nie używamy
:: <math>h(x) \leqslant d(x,y) + h(y),</math>
gdzie <math>d(x,y)</math> oznacza faktyczną odległość
Spełnienie tego warunku gwarantuje poprawność decyzji podejmowanych przez algorytm w oparciu o heurystykę, ponieważ nie zajdzie sytuacja, w której <math>h(x)</math> dla pewnego <math>x</math> będzie większe niż faktyczna długość ścieżki z <math>x</math> do wierzchołka docelowego. Niespełnienie warunku oznacza, że algorytm mógłby wskazać nieoptymalną ścieżkę, jeśli dla pewnego węzła <math>y</math> w optymalnej ścieżce <math>h(y)</math> byłoby zawyżone.
| |||