A* algorithm improvements 
Author Message
 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  
 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  
 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: 415-933-7197                   +--------------------------------+
+-------------------------------------+



Sun, 27 Dec 1998 03:00:00 GMT  
 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  
 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 semi-random 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  
 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: 415-933-7197                   +--------------------------------+
> +-------------------------------------+



Mon, 28 Dec 1998 03:00:00 GMT  
 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  
 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  
 
 [ 8 post ] 

 Relevant Pages 

1. A* algorithm improvements

2. Converting recursive algorithms to tail recursive algorithms...???

3. Improvement to generated ActiveX methods?

4. Refinancing, Second Mortgage, Home Improvement

5. Minor DBConnection bug / suggestion for improvement

6. Performance improvements in 5.0?

7. Two suggested improvements

8. Performance improvements between VW 3.0 and VW 5i

9. vw2.5 performance improvements

10. J Performance Improvements

11. Productivity improvement with Smalltalk

12. Any Improvements to this process killing script?

 

 
Powered by phpBB® Forum Software