AI search strategies using discrete mathematics

[rcmango]

Homework Statement

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.

Homework Equations

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 Attempt at a Solution

h1, h2 : {A, B, C, D, E, F, G, H} -> {1, 2, ...}.
Both are admissible,
for example: h1(x) <= C(x) and h2(x) <= C(x) for all x, where C(x) is the lowest cost to the goal.
using h3(x) = (h1(x) + h2(x)) / 2, then h3(x) will be admissible, this may not be better than h1 or h2.

I've tried using (h1+h2)/2 = h3

So, using 2 elements from h1 and h2, h3(A) = (10 + 8) / 2 = 9 < 10 = h1(A)

so the new path cost is lower than h1, but not h2, so is that necessarily more dominate? Not sure what formula would create an optimal solution.

 

[lippyka]

The cost of each of the states according to h3 would be: A: 9, B: 10.5, C: 13, D: 5, E: 8, F: 7, G: 1.5, H: 9.5