Beefy Boxes and Bandwidth Generously Provided by pair Networks
Your skill will accomplish
what the force of many cannot
 
PerlMonks  

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

by dragonchild (Archbishop)
on Jul 16, 2002 at 15:55 UTC ( [id://182123]=note: print w/replies, xml ) Need Help??


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

Can you give an example of backtracking issues that might arise?

------
We are the carpenters and bricklayers of the Information Age.

Don't go borrowing trouble. For programmers, this means Worry only about what you need to implement.

Replies are listed 'Best First'.
Re: Re: Re: Re: Choosing a data structure for AI applications
by Ovid (Cardinal) on Jul 16, 2002 at 16:25 UTC

    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.

Re4: Choosing a data structure for AI applications
by talexb (Chancellor) on Jul 16, 2002 at 16:20 UTC
      This reminds me of Aristotelian logic and those circle diagrams. "All mammals have hair." "All mammals give birth live." "Some fish give birth live." "Do some fish have hair?" and be able to solve that.
    I believe the backtracking issue has to do with finding out the answer to the question (ref:Above) What objects have attribute 'hair'?

    The example maps to the following facts

    • All mammals -> have hair
    • All mammals -> give birth live
    • Some fish -> give birth live
    .. and then tries to backtrack to determine if 'giving birth live' maps to 'All mammals' and from there to 'have hair'.

    --t. alex

    "Mud, mud, glorious mud. Nothing quite like it for cooling the blood!"
    --Michael Flanders and Donald Swann

Log In?
Username:
Password:

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

How do I use this?Last hourOther CB clients
Other Users?
Others taking refuge in the Monastery: (5)
As of 2024-03-29 11:12 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found