Re: Floyd Warshall

På Thu, 30 Aug 2007 15:45:42 +0200, skrev Geoff Wozniak <geoff.wozniak@xxxxxxxxx>:

On Aug 30, 4:06 am, andrea <kerny...@xxxxxxxxx> wrote:
Another little thing, I also have a recursive version (the first I
did) which is working fine

BUT, for even a small number of cities (6) it take hours... That's
right because the numeber of function calls is factorial, but I think
there should be some ways to eliminate many calls...
Ideas?

Look into a technique called memoization.

http://en.wikipedia.org/wiki/Memoization

Check out Norvig's book Paradigms of Artificial Intelligence
Programming (PAIP) for a decent example. (section 9.6)


Tim Bradshaw wrote some memoize functions you can use.
http://www.tfeb.org/lisp/hax.html#MEMOIZE
.

Relevant Pages

  • Re: Floyd Warshall
    ... for even a small number of cities it take hours... ... right because the numeber of function calls is factorial, ... Programming (PAIP) for a decent example. ...
    (comp.lang.lisp)
  • Re: Is Zelaznys "Lord of Light" still highly regarded?
    ... any cities? ... and the 1972 map shows ... a decent 1970s map of Cambodia; but I don't have a decent 1970s map of ...
    (rec.arts.sf.written)