reset password
Author Message
ceejay562
Posts: 25
Posted 15:52 Nov 14, 2014 |

In the instructions it say's "Modify the code above (don't copy some other code) to implement A* search."  Do we use the code from dikstra's alghorithm?

rabbott
Posts: 1649
Posted 15:58 Nov 14, 2014 |

Yes, use the code from Dijkstra's algorithm. The intent of the "don't copy" instruction was to say that you shouldn't just copy some A* code that you find on the web. (There are lots of examples.) I want you to understand  A* search (and Dijkstra's algorithm) well enough so that you can modify the code for Dijkstra's algorithm to do A* search.

Last edited by rabbott at 08:31 Nov 17, 2014.
ceejay562
Posts: 25
Posted 15:59 Nov 14, 2014 |

Ok, thank you.

 

hal255
Posts: 51
Posted 15:31 Nov 15, 2014 |

I'm confused how to apply the A* algorithm to the Dijkstra's algorithm. 

The A* seems to include diagonals, which is the pythagorean theorem value of the row and column.

The Example in the code, https://drive.google.com/file/d/0B-I58s-_d3o5a0JlZjdpcXl2SWs/view?usp=sharing has the following:

red -> blue (5) -> green (3)     So, total is 5+3 = 8.

red -> green(10).... do we change the value of 10 to sqrt(52 + 32), which is sqrt(34) = 5.8309...?

 

And what about the ones that do not include a "diagonal", such as the following:

a. red -> blue (5) -> purple (7)   so, total is 5+7 = 12

b. red -> orange (8) -> purple (2)    so, total is 8+2 = 10

But do we add in red -> purple? If so, which one of the above do we apply it to?

a. becomes sqrt(74) = 8.6023...

b. becomes sqrt(68) = 8.2462...

ceejay562
Posts: 25
Posted 16:11 Nov 15, 2014 |

is this for the heuristic cost?

rabbott
Posts: 1649
Posted 16:21 Nov 15, 2014 |

The diagonals in A* represent shortest conceivable routes, not actual routes. In general there are no edges with those values. Think about a grid of streets in which all the actual streets go either NS or EW. The diagonals represent the actual shortest distance between two points. You use those values as the heuristic shortest possible path. But you don't expect to see edges with those values in the graph.

The graph with the Dijkstra's algorithm code does not have enough information to construct diagonals. You would have to give the nodes (x, y) coordinates and then use those coordinates to compute direct distances. The graph as given does not tell you where the nodes are located and hence there is no way to figure out what the shortest possible distances are between them.

If you want to use the graph in the code as a starting point, give the nodes (x, y) coordinates. But be careful that the coordinates you choose are consistent with the edge distances. For example, the distance between red and blue is 5. If you were to assign red to (0, 0) and blue to (0, 10) it would be impossible for the distance to be 5 since they are 10 units apart. So as I said, if you use that graph as a starting point for an example, be sure the coordinates you choose are consistent with the given distances. Note that you could, for example, say that red is at (0, 0) and that blue is at (0, 3). It's still possible that the actual edge between them has a distance of 5 because it might be a curvy road.

Last edited by rabbott at 08:30 Nov 17, 2014.
hal255
Posts: 51
Posted 16:24 Nov 15, 2014 |

I see. Thank you Professor.

Last edited by hal255 at 16:33 Nov 15, 2014.