Loading ...
Sorry, an error occurred while loading the content.

A* algorithm

Expand Messages
  • Imanpreet Singh Arora
    Hi I am reading Russell and Norvig s AIMA and I have the following query. I am reading section 4.1 regarding A* algorithm, I was wondering if the triangular
    Message 1 of 4 , Dec 12, 2003
    • 0 Attachment
      Hi I am reading Russell and Norvig's AIMA and I have the following
      query.
      I am reading section 4.1 regarding A* algorithm, I was
      wondering if the triangular inequality that has been shown on page
      99 is applicable for

      c(n,a,n') <= h(n) + h(n')
      also

      that is the triangular inequality should be held as a whole.

      Furthermore in the following scenario

      -------------
      | A[ 100] |
      _____________
      / \60
      /70 \
      _____ __________
      f=120| B[50]| | C [80] | 140
      _____ _________
      40 \ /20
      _________
      | D [80] | f(from B) = 110 + 80 = 190, and f ( from C ) = 80
      + 80 = 160
      __________
      | 80
      ________
      | Goal |
      _________

      Now to me the above state space seems to be admissible and
      consistent but still the solution path that would be found would
      involve D's parent to be B because the first parent would be
      accepted. Which is obviously not the best solution because it
      involves a total cost of 70+ 40 + 80 = 190 but the path through C
      requires 60 + 20 + 80 = 160.

      What is the point that I am missing?

      --
      Imanpreet Singh Arora
      isingh AT acm DOT org
    • E etech058
      Hi, I have used AIMA version 1, do you use version 1 or not? I haven t found the inequality of c(n,a,n )
      Message 2 of 4 , Dec 17, 2003
      • 0 Attachment
        Hi,
        I have used AIMA version 1, do you use version 1 or not?
        I haven't found the inequality of "c(n,a,n') <= h(n) + h(n')" in page 99.
        In addition, the scenario is not easy to understand, could you represent it more clearly.


        Kind regards/chenyu



        -----Original Message-----
        From: Imanpreet Singh Arora [mailto:imanpreet_arora@...]
        Sent: 2003年12月13日 1:46
        To: aima-talk@yahoogroups.com
        Subject: [aima-talk] A* algorithm

        Hi I am reading Russell and Norvig's AIMA and I have the following
        query.
        I am reading section 4.1 regarding A* algorithm, I was
        wondering if the triangular inequality that has been shown on page
        99 is applicable for

        c(n,a,n') <= h(n) + h(n')
        also

        that is the triangular inequality should be held as a whole.

        Furthermore in the following scenario

        -------------
        | A[ 100] |
        _____________
        / \60
        /70 \
        _____ __________
        f=120| B[50]| | C [80] | 140
        _____ _________
        40 \ /20
        _________
        | D [80] | f(from B) = 110 + 80 = 190, and f ( from C ) = 80
        + 80 = 160
        __________
        | 80
        ________
        | Goal |
        _________

        Now to me the above state space seems to be admissible and
        consistent but still the solution path that would be found would
        involve D's parent to be B because the first parent would be
        accepted. Which is obviously not the best solution because it
        involves a total cost of 70+ 40 + 80 = 190 but the path through C
        requires 60 + 20 + 80 = 160.

        What is the point that I am missing?

        --
        Imanpreet Singh Arora
        isingh AT acm DOT org



        To unsubscribe from this group, send an email to:
        aima-talk-unsubscribe@yahoogroups.com




        Yahoo! Groups Links

        To visit your group on the web, go to:
        http://groups.yahoo.com/group/aima-talk/

        To unsubscribe from this group, send an email to:
        aima-talk-unsubscribe@yahoogroups.com

        Your use of Yahoo! Groups is subject to:
        http://docs.yahoo.com/info/terms/
      • Imanpreet Singh Arora
        ... page 99. ... represent it more clearly. ... Thanks, I am using version 2.0. Moreover on page 99 you won t find the given inequality but the following h(n)
        Message 3 of 4 , Dec 18, 2003
        • 0 Attachment
          --- In aima-talk@yahoogroups.com, E etech058 <etech058@o...> wrote:
          > Hi,
          > I have used AIMA version 1, do you use version 1 or not?
          > I haven't found the inequality of "c(n,a,n') <= h(n) + h(n')" in
          page 99.
          > In addition, the scenario is not easy to understand, could you
          represent it more clearly.
          >
          >
          > Kind regards/chenyu
          >

          Thanks, I am using version 2.0. Moreover on page 99 you won't find the
          given inequality but the following

          h(n) <= c(n, a, n') + h(n');

          and it was written that it is a triangular inequality, I am wondering
          if the triangular inequality is applicable as whole for all the sides
          like is it applicable for the inequality

          c(n, a, n') <= h(n) + h(n');

          I would try to clarify the scenario, though since I know that the
          original indentation that I provided in the message seems to have been
          lost.

          We have a root node A, and the h(A) is 100.
          It has two childern B and C.
          g(B) =70 and g(C) = 60
          h(B) = 50 and h(C) = 80
          so
          f(B) = 120
          f(C) = 140

          Meaning that it would be f(B) that would be expanded, B has a Child
          named D and this child is common for the nodes B and C.

          Now when B would be expanded the child D would have it's parent set to B.

          The cost of getting to D from B and C is respectively 40 and 20 so the
          total

          g( D through B) is 110
          g ( D through C) is 80

          Now at this juncture C would be expanded and though D is the child of
          C, D's parent would be still set to B because according to section 3.5
          the new path would always be rejected.

          According to the claims of the authors if h(n) is consitent and
          admissible we would certainly find an optimal solution I am not sure
          we are able to in this very case.

          I belive that if we use the f cost in order to determine the parent of
          a node we would certainly find the optimal soution, because for D

          f( D through B ) is 190
          f ( D through C) is 160

          Would the authors and peers be kind to elucidate? I seem to be unable
          to relate the equations and principles to a possible graph space that
          can clarify me.

          --
          Imanpreet Singh Arora
        • E etech058
          Hello Imanpreet, I have read your email carefully, and then read the AIMA book again. My idea is as follows: 1. A* will find the optimal (best) solution. It is
          Message 4 of 4 , Dec 19, 2003
          • 0 Attachment
            Hello Imanpreet,
            I have read your email carefully, and then read the AIMA book again. My idea is as follows:
            1. A* will find the optimal (best) solution. It is correct.
            2. Your idea has one implicit assumption, which is not same as the book. That's you assume that "GOAL-TEST(NODE)" check will be run immediate after the "EXPAND" function. The correct one (AIMA books "GENERAL-SEARCH" pceudo-code) is "EXPAND", then "QUEUE-FN", then "GOAL-TEST".
            2.1 Your above implicit assumption means that you doesn't give the more chance to "A*" for finding more optimal solution.
            2.2 Explain by your example. After "Node B f(B)=120" is expanded, in the A* queue, 2 nodes exists. One is "Node D f(D)=180", the other is "Node C f(C)=140". Then (Please look at "GENERAL-SEARCH" pseudo-code) function "QUEUING-FN" will work. It will produce list which "Node B f(B)=120" is a header. In the next loop, "Node B" will be expanded. It means that although the goal of "Node D" has been founded, the A* will continue to run until it finds a optimal solution.
            3. I just think in the actual programming, your implicit assumption will be used. It means comparing between found pure optimal (A*) solution, the quick and efficient algorithm is more important.



            Kind regards/chenyu



            -----Original Message-----
            From: Imanpreet Singh Arora [mailto:imanpreet_arora@...]
            Sent: 2003年12月19日 3:54
            To: aima-talk@yahoogroups.com
            Subject: [aima-talk] Re: A* algorithm

            --- In aima-talk@yahoogroups.com, E etech058 <etech058@o...> wrote:
            > Hi,
            > I have used AIMA version 1, do you use version 1 or not?
            > I haven't found the inequality of "c(n,a,n') <= h(n) + h(n')" in
            page 99.
            > In addition, the scenario is not easy to understand, could you
            represent it more clearly.
            >
            >
            > Kind regards/chenyu
            >

            Thanks, I am using version 2.0. Moreover on page 99 you won't find the
            given inequality but the following

            h(n) <= c(n, a, n') + h(n');

            and it was written that it is a triangular inequality, I am wondering
            if the triangular inequality is applicable as whole for all the sides
            like is it applicable for the inequality

            c(n, a, n') <= h(n) + h(n');

            I would try to clarify the scenario, though since I know that the
            original indentation that I provided in the message seems to have been
            lost.

            We have a root node A, and the h(A) is 100.
            It has two childern B and C.
            g(B) =70 and g(C) = 60
            h(B) = 50 and h(C) = 80
            so
            f(B) = 120
            f(C) = 140

            Meaning that it would be f(B) that would be expanded, B has a Child
            named D and this child is common for the nodes B and C.

            Now when B would be expanded the child D would have it's parent set to B.

            The cost of getting to D from B and C is respectively 40 and 20 so the
            total

            g( D through B) is 110
            g ( D through C) is 80

            Now at this juncture C would be expanded and though D is the child of
            C, D's parent would be still set to B because according to section 3.5
            the new path would always be rejected.

            According to the claims of the authors if h(n) is consitent and
            admissible we would certainly find an optimal solution I am not sure
            we are able to in this very case.

            I belive that if we use the f cost in order to determine the parent of
            a node we would certainly find the optimal soution, because for D

            f( D through B ) is 190
            f ( D through C) is 160

            Would the authors and peers be kind to elucidate? I seem to be unable
            to relate the equations and principles to a possible graph space that
            can clarify me.

            --
            Imanpreet Singh Arora



            To unsubscribe from this group, send an email to:
            aima-talk-unsubscribe@yahoogroups.com



            Yahoo! Groups Links

            To visit your group on the web, go to:
            http://groups.yahoo.com/group/aima-talk/

            To unsubscribe from this group, send an email to:
            aima-talk-unsubscribe@yahoogroups.com

            Your use of Yahoo! Groups is subject to:
            http://docs.yahoo.com/info/terms/
          Your message has been successfully submitted and would be delivered to recipients shortly.