Jump to content

Uniform Cost Search Algorithm: Can't understand the Path


zak100

Recommended Posts

Hi,

I can't understand the path specified in red arcs in the attached slide. 

The slide shows a movement from A to C and then from C to B and then from B to D. I can’t understand the C to B and B to D movements (or arcs) because there is no edge supporting these movements.

Somebody please explain me the path shown in the red dotted line in the slide.

Uniform Cost Search2.png

Link to comment
Share on other sites

This is difficult to interpret-- but I notice the heading says 'Expands the least expensive node first.'  So-- my interpretation is that the red dashed lines are intended only to indicate the order in which the pathways are tested-- not the actual path used.  The dashed line from A indicates that the first path examined is from A to C, because the cost from A to C is less than from A to B.  The red line from C to B is only to indicate that the next pathway examined is the one that leads to B (from A).  The next path examined is the one that leads to D from C, the next is the one that leads form B to D.  The next is from D back to B (pathway ACDB - which fails) and finally the next pathway examined is ACDE, a success.  In other words, I'm postulating that the red dashed lines show the order in which the algorithm tests destinations, not the path taken to test them.  Summarizing, the system keeps testing paths starting with the least values until it finds the solution.  The paths tested, in order, are AC, AB, ACD. ABD. ACDB, and finally ACDE.

Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
×
×
  • Create New...

Important Information

We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.