Thread: creating a better heurstic formula using 2 given heuristics.

This is a question about AI search strategies using discrete mathematics.

there are 2 admissible heuristics h1 and h2:

Code:

States:
    A  B  C  D E F G H
h1: 10,12,12,6,7,7,2,10
h2: 8, 9, 14,4,9,7,1,9

the question is to provide a new composite heuristic h3 that is admissible and dominates h1 and h2. Then show the cost of each of the states through H according to h3.

I'm not sure how to answer this question based from the information.

My guess would be that since there are already 2 effective heuristics, why not take both of them and divide them by 2, then that will create the new heurstic h3?

(h1+h2)/2 = h3

Does that seem to be on the right track?
thanks alot.

Why not just switch a few genes? h3: 10 12 14 6 9 7 2 10

Originally Posted by TKHunny

Why not just switch a few genes? h3: 10 12 14 6 9 7 2 10

This is sounding more like a genetic algorithm, So that would make h3 a more admissible heuristic?
If so, I'm not sure what formula would suffice for such a task?

So, h1 and h2 are two functions; h1, h2 : {A, B, C, D, E, F, G, H} -> {1, 2, ...}. Both are admissible, i.e., h1(x) <= C(x) and h2(x) <= C(x) for all x, where C(x) is the lowest cost to the goal. If you take h3(x) = (h1(x) + h2(x)) / 2, then h3(x) will be admissible, but it will not necessarily dominate h1 and h2. For example, h3(A) = (10 + 8) / 2 = 9 < 10 = h1(A).

Originally Posted by emakarov

So, h1 and h2 are two functions; h1, h2 : {A, B, C, D, E, F, G, H} -> {1, 2, ...}. Both are admissible, i.e., h1(x) <= C(x) and h2(x) <= C(x) for all x, where C(x) is the lowest cost to the goal. If you take h3(x) = (h1(x) + h2(x)) / 2, then h3(x) will be admissible, but it will not necessarily dominate h1 and h2. For example, h3(A) = (10 + 8) / 2 = 9 < 10 = h1(A).

Okay, so for sure, h3(x) would be an admissible function by using my formula as a guess. I'm still not sure what formula would make h3(x) more admissible thatn h1(x) and h2(x)

I thought the genetic algorithm idea was getting closer, by taking mix matching a few elements to create a possible better heurstic, but thats the idea for genetic algorithm. Any other ideas?

The value of h3(x) for each argument x can be found from h1(x) and h2(x), without looking at other arguments. Now, given two numbers that are don't exceed some real cost, you need to find a number that is not smaller than any of those two numbers, but still does not exceed the same cost.