StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>I am not an expert, but I studied the Wikipedia article for a while and my explanation would be this one (hope i have understood it well :)</p> <p>Say, we have a 4x4 matrix of nodes.<BR> A,B,C,D are the directions we can take at a given time (North,South,East,West)<BR> The A* algorithm starts searching.<BR></p> <p>A<BR> Queue: B,C,D<BR> AA<BR> Queue: B,C,D,AB,AC,AD<BR> AAA-->Goal<BR> Queue: B,C,D,AB,AC,AD,AAB,AAC,AAD<BR> The goal is reached but there are still other possibilities to consider.<BR></p> <p>D<BR> Queue: B,C,AB,AC,AD,AAB,AAC,AAD<BR> DC<BR> Queue: B,C,AB,AC,AD,AAB,AAC,AAD,DA,DB,DD<BR> DCA<BR> Queue: B,C,AB,AC,AD,AAB,AAC,AAD,DA,DB,DD,DCB,DCC,DCD<BR> DCAB-->Goal<BR> Queue: B,C,AB,AC,AD,AAB,AAC,AAD,DA,DB,DD,DCB,DCC,DCD,DCAA,DCAC,DCAD<BR> Etc etc</p> <p>As you can see, for every step taken, three more nodes are added to the queue.<BR> Since A* follows only acyclic paths [1], the maximum number of steps per route is 15.<BR> The max number of possible routes in this case is 3^15, or directions^nodes.<BR> Since every route has 15 steps,the worst case steps taken is 15*3^15.<BR> In the absolute worst case, every step ever taken is "wrong".<BR> In that case 3*15*3^15 nodes are in the queue before finding the answer.<BR> So the worst case amount of nodes that needs to be kept in memory is a constant, to the power of the number of nodes available. In other words the memory use is exponential to the amount of nodes.<BR></p> <p>[1] <a href="http://www.autonlab.org/tutorials/astar08.pdf" rel="nofollow noreferrer">http://www.autonlab.org/tutorials/astar08.pdf</a>, slide 15</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload