@InnocuosFox

Yes but is very low...

Your question is tricky :)

If i say yes to you then also 2 and 3 in this example never overestimate the distance to the goal considering the other cars.

O no?

Quote: Original post by STRIKE82
@Alvaro

Thanks. Your statement makes things very clear.

So considering the situation i would say that Heuristic 3 is admissible, because the cars blocking the path represent the minimum number of moves to clear the path, abstracting other cars or without considering them.

You have to learn to be precise. "The cars blocking the path represent the minimum number of moves to clear the path" is not true. You probably have the right intuition for it, but that doesn't cut it.

Quote: I am tempted to say yes to heuristic 2 in this example, but i think is not admissible because there could be cars in other examples that don't necessarily block the way to the red car.

Then why are you tempted to say "yes"?

Quote: For the first heuristic I would say no, because if it always return 1 then it means that the path is always clear.

No, it doesn't mean anything of that type, and you seem to be forgetting what the question is. The only question you have to answer is this: Is the statement "The distance to the solution is always at least 1" true or false? That's all that matters.

@Alvaro

OK

So to be precise then we can say that only H1 is true because in the easiest of the possibilities, or when the path is clear then it never overestimates the distance to the goal.

H2 i was tempted to say yes in relation to this example, because the number of the other cars is the same as the number of moves required to exit, but i think is not precise to say this. So H2 is false.

H3 again is false because there could be other cars blocking the cars that directly block the path of the red car.

As you said i have guessed and that is not precise and can not be accepted.
But i can only guess if i don't have the tools to evaluate each heuristic.

I mean i don't know how to precisely evaluate each of the given heuristic.

Am i right this time about H1, H2, and H3?

What you think?

I don't know if you are getting any closer. If you say a heuristic is admissible, you need to provide proof that it never overshoots. If you say it isn't admissible, you can for instance show a situation where the heuristic overestimates the number of moves.

H1 then can never overshoot because the solution can never be less than 1. It must be at least 1.

H2 can overshoot because there could be as in this case 5 cars beside the red car in other locations that would require the solution to be less than 5.

H3 can overshoot everytime there is more than one car directly blocking the way.

Is this ok as proof?

What you say?

Quote: Original post by STRIKE82
H1 then can never overshoot because the solution can never be less than 1. It must be at least 1.

Yup, it's as easy as that. [EDIT: Actually, your wording is not quite right. You can say that the *distance to the goal* can never be less than 1, or that the solution can never be shorter than 1 move. The solution is not a number.]

Quote: H2 can overshoot because there could be as in this case 5 cars beside the red car in other locations that would require the solution to be less than 5.

That didn't make sense. If you think it can overshoot, just describe one example where it does overshoot. A diagram would do.

Quote: H3 can overshoot everytime there is more than one car directly blocking the way.

That doesn't sound right. I don't think you have thought this one through.

[Edited by - alvaro on November 12, 2009 1:27:10 PM]

I think throughout this whole thread you are getting two ideas confused. Remember, you are not trying to solve the path. You are not even trying to come up with an estimation formula based on other inputs for how many moves it might take. What you are supposed to be doing is, essentially, calibrating your measuring device in such a way that every possible path that you evaluate can be compared to it in a reasonable fashion. To continue the metaphor, you don't calibrate your scale with something sitting on it.

In normal A*, the typical heuristic is a straight line. Never mind the complications - if they even exist. That's what A* is supposed to handle. In this case, the 2nd and 3rd options address ONLY the complications - not the simplest, most vanilla case. The 1st option is, essentially, the scale with nothing on it. No complications; no weights.

A variation on option 1 would be the minimum distance that the car would have to travel if there were no other obstacles. In fact, that would be the idea heuristic. However, that would have been too easy and they wanted to make you think.

Quote: Original post by InnocuousFox
I think throughout this whole thread you are getting two ideas confused. Remember, you are not trying to solve the path. You are not even trying to

Uhm, are you sure about that? Maybee I got that wrong, too. But isn't the question actually to find the best set of moves (of all cars) that solves the puzzle?

In that case wouldn't the vanilla heuristic have to at least take the number cars into account, that have to be moved (at least once)?

I suppose that's a valid point.

I still object to the wording of the question anyway.

I don't see any problems with the wording of the question. What are your objections, Dave?