Re: Computationally expensive AI problem

[EMAIL PROTECTED] (Griffin) writes:
> Can somebody give me an example of an AI problem that is
> computationally very expensive (needs a lot of computer resources e.g.
> CPU). The problem may be from any area of AI whether GAs or Neural
> Networks or anything from AI.

"Travelling Salesman"?  Aka given a set of cities on a map, with distances
between them, what is the shortest path that goes through every city.

In general, any NP-complete problem can quickly be made computationally
intractable just by making it sufficiently large.  And you can call it an
AI problem if it's mostly about search, especially if there are domain-specific
heuristics that you might be able to apply.

A more real-world example of the same thing might be finding airline flights.
Something like Orbitz.com needs to solve an interesting search problem very
quickly.

Or: try scheduling.  A set of tasks with durations and resource requirements;
a limited set of resources; how do you order and pack the tasks in order to
minimize the total start-to-finish time?  (Scheduling experiments on the
Hubble Space Telescope was one such real-world example.)

Or: automated inference, which is even worse than computationally
intractable (since it is undecidable in general).  Try writing a theorem
prover than can solve all the examples at tptp.org ("Thousands of Problems
for Theorem Provers").

        -- Don
_______________________________________________________________________________
Don Geddis                  http://don.geddis.org/               [EMAIL PROTECTED]
Solution to two of the world's problems:  Feed the homeless to the hungry.

[ comp.ai is moderated.  To submit, just post and be patient, or if ]
[ that fails mail your article to <[EMAIL PROTECTED]>, and ]
[ ask your news administrator to fix the problems with your system. ]