Results 1 to 6 of 6

Math Help - creating a better heurstic formula using 2 given heuristics.

  1. #1
    Senior Member
    Joined
    Jan 2007
    Posts
    477

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Aug 2007
    From
    USA
    Posts
    3,110
    Thanks
    2
    Why not just switch a few genes? h3: 10 12 14 6 9 7 2 10
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Jan 2007
    Posts
    477
    Quote Originally Posted by TKHunny View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,517
    Thanks
    771
    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).
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member
    Joined
    Jan 2007
    Posts
    477
    Quote Originally Posted by emakarov View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,517
    Thanks
    771
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Help creating a formula for a software.
    Posted in the Math Software Forum
    Replies: 0
    Last Post: September 5th 2011, 02:11 PM
  2. Problem with creating a formula
    Posted in the Trigonometry Forum
    Replies: 5
    Last Post: January 15th 2011, 09:33 AM
  3. Creating a Formula
    Posted in the Algebra Forum
    Replies: 5
    Last Post: October 20th 2010, 05:40 PM
  4. Need help creating a formula
    Posted in the Geometry Forum
    Replies: 7
    Last Post: November 2nd 2009, 07:40 AM
  5. Need help with creating Break Even Formula
    Posted in the Business Math Forum
    Replies: 0
    Last Post: February 7th 2009, 10:35 AM

Search Tags


/mathhelpforum @mathhelpforum