Алчна ли е звездата?

2024 Автор: Lynn Donovan | [email protected]. Последно модифициран: 2023-12-15 23:43

А*(А звезда ) A* е комбинация от Dijkstra и Алчен . Той използва разстояние от основния възел плюс евристично разстояние до целта. Алгоритъмът приключва, когато намерим целевия възел.

Освен това алчното най-добро първо търсене Завършено ли е?

В обобщение, алчен BFS не е завършен , не оптимален , има времева сложност от O(bm) и пространствена сложност, която може да бъде полиномна. A* е завършен , оптимален и има времева и пространствена сложност от O(bm). Така че като цяло A* използва повече памет от алчен BFS. A* става непрактично, когато Търсене пространството е огромно.

Освен по-горе, допустимо ли е *? Ако евристична функция е допустимо , което означава, че никога не надценява действителните разходи за достигане до целта, A* гарантирано ще върне най-евтиния път от началото до целта. Тогава f стойността на целта е цената на най-краткия път, тъй като h при целта е нула в an допустимо евристичен.

Освен това, защо * е по-добро от най-доброто първо търсене?

A* постига По-добре производителност чрез използване на евристика за насочване Търсене . A* съчетава предимствата на Най-добрият - първо търсене и единна цена Търсене : гарантира, че ще намерите оптимизирания път, като същевременно увеличавате ефективността на алгоритъма с помощта на евристики.

Алгоритъмът A * завършен ли е?

A* е завършен и винаги ще намери решение, ако такова съществува. Разгледайте статията в Уикипедия. Ако по-нататък евристиката е допустима и монотонна алгоритъм също ще бъде допустимо (т.е. оптимално).