What is the cost of A* search in the worst case?
anyone has the answer for this retarded question?
>>54975678
The time complexity of A* depends on the heuristic. In the worst case, the number of nodes expanded is exponential in the length of the solution (the shortest path), but it is polynomial when the search space is a tree, there is a single goal state, and the heuristic function h meets a certain criteria:
>>54976774
>In the worst case, the number of nodes expanded is exponential in the length of the solution (the shortest path),
What? No it's not. You can trivially construct an input where the length of the shortest path is 1 but the algorithm takes an arbitrary amount of time to finish.
>>54975678
What?
>>54976774
i saw it on wikipedia
>>54976852
can you eloberate
>>54975678
idk dude I wish there was a place where you could just look it up
>>54977335
its the last two word of the question. also i need to explain why.
>>54977343
A* with a bad heuristic is basically going to work like breadth first search.
>>54977343
Do your own homework.
>>54977686
incorrect.
without a heuristic, the search will be a breadth first search.
You can make a heuristic that makes performance worse.
Eg if you search for the longest path.
>>54977977
fuck off witty, its better than asking for naked cartoon girls.
>>54978058
what happens if there is a same length for every possible node? is it gonna break
>>54978296
>its better than asking for naked cartoon girls
But neither is appropriate for this board.
>>54978296
>what happens if there is a same length for every possible node? is it gonna break
Lets assume your heursitic says that the distance is the same on every path.
And assuming the real distance is the same on every path, you will most likely keep them in the order you are searching, so nothing changes. It still works fine.
Try making an application where you use A*.
Like solve a maze or something.
It shouldn't take you more than an hour to implement.
