Still celebrating National IT Professionals Day with 3 months of free Premium Membership. Use Code ITDAY17

x
?
Solved

Backward Chaining

Posted on 2010-11-11
9
Medium Priority
?
642 Views
Last Modified: 2012-05-10
Could you explain backward chaining? For example how would I handle

1 - allergies(x) => sneeze(x)

2 - cat(y) ^ allergic-to-cat(x) => allergies

3 - cat(Felix)

4 - allergic-to-cat(Lisa)

Goal: Sneeze(Lisa)
0
Comment
Question by:JCW2
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 5
  • 4
9 Comments
 
LVL 37

Expert Comment

by:TommySzalapski
ID: 34117957
You start from the back. So in order to get Sneeze(Lisa) you select a rule that could lead you there and add it to the list of goals. In this case the only rule that does this is rule 1. So now the list of goals is just allergies(Lisa)=>Sneeze(Lisa) (replacing x with Lisa). So this is your new goal (in more complicated questions you may have multiple goals in the list at a time).

So what could get you to the new goal? Pick all the rules that could get you there and make those the goals (in this problem you'll only have one again)

If you run into a problem where you have more than one goal at some point, just do the same thing for all the goals.

What I would do is just write the goal and then draw an arrow to all the new goals and write them.
0
 
LVL 37

Expert Comment

by:TommySzalapski
ID: 34117967
And you just keep going until you get a goal that is given directly by a rule or by the given conditions of the problem.
0
 

Author Comment

by:JCW2
ID: 34123022
Can you describe how to work with this:
BC.PNG
0
Learn how to optimize MySQL for your business need

With the increasing importance of apps & networks in both business & personal interconnections, perfor. has become one of the key metrics of successful communication. This ebook is a hands-on business-case-driven guide to understanding MySQL query parameter tuning & database perf

 
LVL 37

Expert Comment

by:TommySzalapski
ID: 34123088
Yes. It's saying to do the same thing I said.

q = Goal

"check if q is known already"
Do you have a rule or a given statement that says q is true?

"prove by BC all premises of some rule concluding q"
Take all the rules that have q on the right hand side and add them to the goal list.
Do the last two steps for each of them.
Note that this will continue until you find a rule that directly says one of your goals is true.

"Avoid loops"
If you get ready to add a goal to the goal list and it was already there before, don't add it again.

"Avoid repeated work"
If you add a goal to the list but you already proved it true or false, don't add it. Just use true or false.
0
 

Author Comment

by:JCW2
ID: 34125850
I need to demonstrate use of a stack when implementing backward chaining. How should I do this?
0
 
LVL 37

Expert Comment

by:TommySzalapski
ID: 34125936
By each step of the process put your entire goal list (stack). So in the first step, the stack will have one goal. In the second step, two goals, etc. Of course if two rules will satisfy a goal you'll add two new goals to the stack at once.
0
 

Author Comment

by:JCW2
ID: 34129051
Would the stack look anything like this:
Stack.PNG
0
 
LVL 37

Accepted Solution

by:
TommySzalapski earned 2000 total points
ID: 34129266
Absolutely. The only thing I'd do differently is mark the 'active' goals (the ones that have not been satisfied by other goals).
So in steps 1 and 2, I'd put a mark by the top goal and in step 3 the top 2 goals.
0
 

Author Closing Comment

by:JCW2
ID: 34146910
Thank you for your help.
0

Featured Post

Free Tool: Path Explorer

An intuitive utility to help find the CSS path to UI elements on a webpage. These paths are used frequently in a variety of front-end development and QA automation tasks.

One of a set of tools we're offering as a way of saying thank you for being a part of the community.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Whether you’re a college noob or a soon-to-be pro, these tips are sure to help you in your journey to becoming a programming ninja and stand out from the crowd.
In this post we will learn how to make Android Gesture Tutorial and give different functionality whenever a user Touch or Scroll android screen.
Finds all prime numbers in a range requested and places them in a public primes() array. I've demostrated a template size of 30 (2 * 3 * 5) but larger templates can be built such 210  (2 * 3 * 5 * 7) or 2310  (2 * 3 * 5 * 7 * 11). The larger templa…
Progress

660 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question