Assignment 2 Exercise 4.1

Hi Guys

I am a bit stuck with this one. I am finding myself in a situation where I am looping between Mehadia and Lugoj. What action do we take if we find ourselves in that setup (where the next branch takes you back to the parent endlessly) in A* Search?


Kay

Hey there Kay

I think it's a bit premature to start asking stuff about the second assignment. I'm only expecting my textbook to arrive at the end of the month so I haven't even started yet. I'm suspecting that most students haven't even got to the point where they can do the first assignment let alone the second one.

Looks like you're on your own for a while. Good luck.

Rob

A* search uses g(n) + h(n).

Since g(n) represents the actual distances and h(n) is admissable; it should be impossible to loop. In fact its because of this that A* is optimal.

I suspect you are not calculating g(n) correctly.

g(n) is calculated using the actual cost to get the town in question, so far. So in the initial state g(n) always equals zero as you have not travelled any distance to get there. The branching states then equal the distance to that town.

For example if we start in Durban and are trying to get to Bucharest. g(n) at Durban would be zero. If I expand the state to Umkomaas the value of that node's g(n) would be 55km. If I then expand Durban again from Umkomaas this time the node with Durban in it would have a g(n) of 110kms.

Hope that helps....

Read page 97, 4th line from the top:
Furthermore, if we are not careful to detect repeated states, the solution will never be found - the search will oscillate between Neamt and Iasi.
This is what you are describing above - also look at Fig 4.3 - they do not expand Arad if it is a subnode of another city.

I dont have that text book with me... but... is that an A* search?

Logically; as g(n) increases the oscillation should eventually end and the search will follow the correct route...

I think you are looking at the greedy best first search?

It is a reference to the Greedy best-first search with straight-line distance heuristic. So, no. But, the way I understood the A* search, is that it is a form of best-first search (actually states that as part of the definition) and thus the comment that I've quoted should also apply? Right?
Also, if you are trying to get the cheapest solution, you are not going to "back-track" or repeat on a path/node already handled.

Reanie.. it does not apply to A* search...

And backtracking in the search is actually correct - as the solution presented to the agent by the search will be optimal - even if finding the path required backtracking.

I've re-read your answer given above about g(n) = 0 if again at original state. So, guess, I need to redo some calculation and drawing....

g(n) will increase every branch... so every time you expand a node (that is also a previously visited state) it will increase.

Your Durban / Umkomaas example actually put me on the rigth track.
Well, going to submit now, so here goes...