A* algorithm improvements
Author 
Message 
Alvaro Garcia Ugart #1 / 8

A* algorithm improvements
I've programmed A* algorithm in ASM under DOS4GW and in the first code I didn't sort F=G+H when storing them in an array. So I had to found the best one searching it, that is reading and comparing all the array. In a second code, I do sort them, inserting the new F in the appropiate place, and my code is 50 times faster using a 512x512 map and a 100 positions path length (WATCOM profiler told me I expent 97% of the time searching the best F). AND HERE IS MY QUESTION: My current insertion code (is bad) begins reading and comparing from the begining of the array to find the correct insertion place. I know that DICOTOMIC searching/insertion algorithm will improve my code. Is there any other algorithm better than this (dicotomic)? I don't need to reorder an unsorted array, so I don't need sorting algorithms such us, QuickSort, Shell, etc... (I think). I only need to insert one new F at a time. Thanks.
Reus, CAT SPAIN

Mon, 21 Dec 1998 03:00:00 GMT 


Jasper Philli #2 / 8

A* algorithm improvements
Quote: >I've programmed A* algorithm in ASM under DOS4GW and in the first code I didn't sort F=G+H when storing them in an array. >So I had to found the best one searching it, that is reading and comparing all the array. >In a second code, I do sort them, inserting the new F in the appropiate place, and my code is 50 times faster using a 512x512 >map and a 100 positions path length (WATCOM profiler told me I expent 97% of the time searching the best F). >AND HERE IS MY QUESTION: >My current insertion code (is bad) begins reading and comparing from the begining of the array to find the correct insertion >place. I know that DICOTOMIC searching/insertion algorithm will improve my code >Is there any other algorithm better than this (dicotomic)? I don't need to reorder an unsorted array, so I don't need sorting >algorithms such us, QuickSort, Shell, etc... (I think). I only need to insert one new F at a time. >Thanks.
>Reus, CAT >SPAIN
Hmmm, first off, what is Dicotomic? All the stuff I found on that through lycos was in italien. :( Anyway, couldn't you just use some sort of binary tree or heap? Certainly far better than a linear search; The only thing I can think off hand that's faster is a hash dictionary, but I don't see how that'll work for what you need (an ordered list). You should be able to find many examples of these in any basic algorothms text. Hope this helps, Jasper  /\ Jasper Phillips (Pit Fiend) ______,...., /VVVVVVVVVVVVVV==================="""""""""""" ___,..' `^^^^^^^^^^^^^^======================"""""" \/ http://www.cs.orst.edu/~philljas/

Sun, 27 Dec 1998 03:00:00 GMT 


Sebastien Loise #3 / 8

A* algorithm improvements
Quote:
> AND HERE IS MY QUESTION: > My current insertion code (is bad) begins reading and comparing from the begining of the array to find the correct insertion > place. I know that DICOTOMIC searching/insertion algorithm will improve my code.
A dichotomic search will not solve your problem  dichotomic searches are mostly for arrays which are linear in time for insertion anyway. The proper data structure for storing paths in Dijktra's algorithm is the priority queue, which is ideally implemented on top of Fibonnacci (sp?) heaps. Alternately, if you don't need all the features of the Fibonnacci heap, you could do away with a Binomial heap. I'm not 100% certain on implementation details of these two heaps (read: I couldn't describe it to you if my life depended on it)  please consult the white book: "Introduction to Algorithms" by MIT press (I hope I got that right  don't have the book around here to check against). It's a really good book. The book having "introduction" in its title is sort of misleading for it covers more than most computer scientists will know at the end of their Bachelor's degree in terms of basic algorithmics. Hope this helps.  Sebastien Loisel SGI Graphics Engineering/NextGen Graphics (ISD)
+++ While in California (summer 1996)  The rest of the time  450 Loreto Street  1 J.K. Laflamme  Mountain View, CA, USA, 94041  Levis, Quebec, Canada, G6V 3R1  Work: 4159337197 ++ ++

Sun, 27 Dec 1998 03:00:00 GMT 


Jerzy Tarasi #4 / 8

A* algorithm improvements
A> AND HERE IS MY QUESTION: A> Is there any other algorithm better than this (dicotomic)? I don't need to reorder an unsorted array, so I don't need sorting A> algorithms such us, QuickSort, Shell, etc... (I think). I only need to insert one new F at a time. Inserting into a table which need to be looked: you can use AVL weighted tree (it is a tree, in which each node has two branches of max length same or differing by one and a flag signalling how compare lengths of these branches, and value). Dicotomic search is a bit faster than tree, but when you insert, you must move about half of data (average). Another method allowing faster than dicotomic search: hash table; the only problem is you must be able to compute hash value of element you are looking for  easy when looking for exact match, rather useless otherwise. In assembly for sorted table search you can make few comparisons before jump  add carry bits from comparisons and use sum as branch index  maybe it can be faster. Or use dicotomic search without braches  use SBB opcode to extend carry bit to entire register, and mask value with the register, this way computing new index without conditional jump (jump would clear prefetch queue).

Sun, 27 Dec 1998 03:00:00 GMT 


Terje Mathise #5 / 8

A* algorithm improvements
Quote:
> I've programmed A* algorithm in ASM under DOS4GW and in the first code I > didn't sort F=G+H when storing them in an array. > So I had to found the best one searching it, that is reading and comparing > all the array. > In a second code, I do sort them, inserting the new F in the appropiate place, > and my code is 50 times faster using a 512x512 map and a 100 positions path > length (WATCOM profiler told me I expent 97% of the time searching the best > F).
As other people have already told you, some sort of tree structure is the obvious choice here, but the fastest approach might be different: I assume from what you wrote that you have maximum 100 elements in your F table, with 32 bits for each of them, that's just 400 bytes, which will fit easily into the L1 cache. With semirandom F values, a new entry will by average be inserted into the middle of the array, forcing you to shift 50 entries down, or 200 bytes. Using REP MOVS to do the shift, this will take about 63 cycles on a Pentium (1 cycle/dword plus the startup overhead), which is probably faster than most tree algorithms can handle the problem! The real cost is going to be the binary search to locate the insertion point, not the shifting of the data to make room after you find it. I don't know what the A* algorithm does, so I don't know if you also need to remove entries from F (presumably from the front). If so, just shift the preceeding data towards the front when inserting the next item. 
"almost all programming can be viewed as an exercise in caching"

Sun, 27 Dec 1998 03:00:00 GMT 


Matthew B Gric #6 / 8

A* algorithm improvements
Quote:
> > AND HERE IS MY QUESTION: > > My current insertion code (is bad) begins reading and comparing from the begining of the array to find the correct insertion > > place. I know that DICOTOMIC searching/insertion algorithm will improve my code. > A dichotomic search will not solve your problem  dichotomic searches > are mostly for arrays which are linear in time for insertion anyway. > The proper data structure for storing paths in Dijktra's algorithm is > the priority queue, which is ideally implemented on top of Fibonnacci > (sp?) heaps. Alternately, if you don't need all the features of the > Fibonnacci heap, you could do away with a Binomial heap.
I have to admit I did not know WTF the original poster is talking about, and still am not quite sure... But saying that a priority queue is ideally implemented with a fibbonacci help is not quite correct, I believe. While this is true asymptotically, the constant terms associated with the F Heap operation make the binomial a better choice for any problem you are likely to encounter. So Fib heaps are only useful in theory. I am not 100% sure about the above, it is what i remember from reading through the book you mention, an excellent reference or introduction, I agree. It is one of the most valuable and intelligently written technical books I have ever written. I think the information i am trying to recall is on approx. page 520, if you are interested. Quote: > certain on implementation details of these two heaps (read: I couldn't > describe it to you if my life depended on it)  please consult the white > book: "Introduction to Algorithms" by MIT press (I hope I got that right >  don't have the book around here to check against). It's a really good > book. The book having "introduction" in its title is sort of misleading > for it covers more than most computer scientists will know at the end of > their Bachelor's degree in terms of basic algorithmics. > Sebastien Loisel > SGI Graphics Engineering/NextGen Graphics (ISD)
> +++ > While in California (summer 1996)  The rest of the time  > 450 Loreto Street  1 J.K. Laflamme  > Mountain View, CA, USA, 94041  Levis, Quebec, Canada, G6V 3R1  > Work: 4159337197 ++ > ++

Mon, 28 Dec 1998 03:00:00 GMT 


ss.. #7 / 8

A* algorithm improvements
Subject: Re: A* algorithm improvem Ph> Hmmm, first off, what is Dicotomic? All the stuff I found on that Dichotomic searches == binary searches. Ph> Anyway, couldn't you just use some sort of binary tree or heap? ^^^^^^^^^^^ ;) 
Also on my web page: The Programmers' Booklist /booklist.html WASTE (AI Contest) /waste/waste.html comp.ai.games FAQ /cagfaq.html Synapsis Entertainment /synapsis.html moneyworld.com signed me up to a mailing list without my consent.   t Blue Wave/QWK v2.20 t Quote: >> Slipstream Jet  The QWK solution for Usenets #UNREGISTERED

Wed, 30 Dec 1998 03:00:00 GMT 


Alvaro Garcia Ugart #8 / 8

A* algorithm improvements
Dicotomic is a search algorithm that consists on a continous splitting of an ordered array. 
Reus, CAT SPAIN

Wed, 30 Dec 1998 03:00:00 GMT 


