-1
$\begingroup$

I am working on an online course on AI and I am now working to understand A* better.

Basically, right now I am working on a problem where: we live on a tropical island and we're trying to navigate between areas, starting from d and heading towards q.

enter image description here

I am trying to find:

  • the cost used between d and q using A* search
  • how many 'nodes' that were opened during the search
  • Whether this route is actually optimal
  • How many cycles where detected
  • If the person was good at swimming, and what could we change the value of q-r (that's the river path) from 240 to what, to lead to the optimal path.

(see far below for my ideas to these problems)

Below is the costs (when travelling to nodes)

Below is the distance to the target

enter image description here

Attempt at Solving

  1. The optimal path from d to q is d->e->f->g->l->n->q with which would give me a cost of 50+70+20+60+45+20 = 265. This looks like it is the optimal path to get from d to q as well.

  2. Also, we should be expanding 1+2+2+3+1+1=10 nodes to find this path with A*.

  3. I tried a bunch of other different paths and it looks like this one gives us the least cost. So YES! this is true.

  4. Err, this one I don't actually know how to do. Is there a cycle detector in A*?

  5. If the cost of q-r was 0, then that would be the best route indeed. (This seems pretty obvious).


Can any of you AI gurus/graph theorists help me confirm whether I am understanding this properly?

Thanks a ton in advance!

$\endgroup$
  • 1
    $\begingroup$ Your question already includes complete answers to all parts of the original problem except for part 4, but no question about these answer. Thus, only "yes/no" answers may remain, helping neither you nor future visitors. Please read related meta discussions here and here and adjust your question accordingly, e.g. by formulating a specific question about a single element of your answer you are uncertain about. $\endgroup$ – David Richerby Oct 9 '14 at 18:08
  • 1
    $\begingroup$ If you have no questions about parts 1-3 and 5, I suggest deleting those parts and focusing on what you don't understand about part 4. $\endgroup$ – David Richerby Oct 9 '14 at 18:08
1
$\begingroup$

I can respond to your question as follows:

  • the cost used between d and q using A* search

This can be done by applying the algorithm on paper.

  • how many 'nodes' that were opened during the search

This also needs to be done on paper to see

  • Whether this route is actually optimal

If you really want to know if a route is optimal without having guarantee correctness of the algorithm or your application, then you will need to check every possible route and compared with what you have

  • How many cycles where detected

Apply the algorithm on paper

  • If the person was good at swimming, and what could we change the value of q-r (that's the river path) from 240 to what, to lead to the optimal path.

There are other edges that cross the river. You have to look at that as well.

In your particular map, the use of distance might help you. I don't know I haven't exhaustively searched all the paths and I don't think anybody want to do brute force search on it. In general, the distance (Euclidean) I suppose will not help you when the cost is not proportional to it.

In general, without having a heuristic cost function that makes use of distance while still guarantees that the real cost is more than the heuristic cost, you will not have the optimal route.

However, it is possible that if you have a limit on the cost which is if you have a notion of a good enough path, then A* will still help you, the heuristic also adds in value. You check this 'good enough value' after you reached the destination node. Because some heuristic is better than no heuristic, the better the heuristic, the better path you will find.

In this map of yours, since you have river crossing costs that are not intuitively proportional to distance, I am not sure you should apply A* unless you construct a good heuristic cost function that I don't know. So it seems that there is little help using D if you want to expand that map.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.