Beefy Boxes and Bandwidth Generously Provided by pair Networks
laziness, impatience, and hubris
 
PerlMonks  

Re: Re: Re: Re: Choosing a data structure for AI applications

by Ovid (Cardinal)
on Jul 16, 2002 at 16:25 UTC ( #182141=note: print w/ replies, xml ) Need Help??


in reply to Re: Re: Re: Choosing a data structure for AI applications
in thread Choosing a data structure for AI applications

Here's a very simple example that I pulled from http://www.csm.astate.edu/~rossa/cs3543/plect5.html.

on(red_box, table). on(glove, red_box). on(blue_box, table). on(baseball, blue_box).

Let's say that I want to find all X that is on Y that, in turn, is on Z. I would issue the following query:

?- on(X,Y),on(Y,Z).

Here's how the backtracking works.

  1. X = red_box, Y = table.
  2. There are no facts where Y is the first argument to the fact, so this fails.
  3. Prolog backtracks and sets X = glove, Y = red box.
  4. Y is matches the first fact, so we have our first answer.
  5. Prolog backtracks to match Y to another fact, but this fails.
  6. X = blue_box. Y = table
  7. Y does not match any first arguments, so this fails.
  8. Prolog backtracks again and sets X = baseball and Y = blue_box.
  9. Y matches the third fact, so we have our second answer.
  10. Prolog backtracks to match Y to another fact, but this fails.
  11. Prolog backtracks again and tries to set X to another argument, but no more arguments are available, so this fails and the unification of arguments to variables halts.

This is a trivial example (and I took some shortcuts - see the actual link above), but imagine what happens why we have facts embedded in facts and we need to gain information from those subfacts:

gives(ovid,book(learning_perl,[merlyn,rootbeer],publisher(o_reilly),th +ird_edition),grep).

Now, if I issue queries against that (and we're in a proper SQL database), I have at least three tables that I need to span and potentially backtrack across. If my query is more complicated, the number of tables can rise dramatically.

You can also read this link for a more complicated example, or an example of how a bad database can lead to infinite recursion with backtracking.

Cheers,
Ovid

Join the Perlmonks Setiathome Group or just click on the the link and check out our stats.


Comment on Re: Re: Re: Re: Choosing a data structure for AI applications
Select or Download Code

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://182141]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others musing on the Monastery: (10)
As of 2014-12-27 01:56 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    Is guessing a good strategy for surviving in the IT business?





    Results (176 votes), past polls