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

1st version exercise 3.16 sequence predication problem

Expand Messages
  • chenyu468
    hi everyone, 1. According to the guide, it is necessary to build a binary-tree for representing the state . The tree s leaves are 1 or n and internal
    Message 1 of 3 , Nov 11, 2003
    • 0 Attachment
      hi everyone,
      1. According to the guide, it is necessary to build a binary-tree for
      representing the "state". The tree's leaves are "1" or "n" and
      internal nodes are "+" "-" "*" "/" "exp" operator.

      1. I don't know how to check the "dead end" for expression. If
      no "dead end" check, it seems that only "breadth_first_search" is
      acceptable. The the speed and space complexity is too high.

      2. the "action" set for replacing "1" is 16 (20-4) by deleting "n
      divide n", "1 divide 1", "1 multiply 1", "exp(1,1)", "
      for replacing "n" is also 16 for the similar reason.
      The expanding branch factor is too high (16). How to reduce it?

      3. I don't know how to identify the "same state" from different path
      for avoiding expanding them. Could you tell me? Or is it possible to
      create unique tree everytime, therefore no need to identify them are
      the same state or not?

      Thank you in advance.
      kind regards/chenyu
    • Brandon Corfman
      I m not sure what you mean by dead end . If a node can be broken down, into a new center node and two leaves, then at some point, the whole process will stop
      Message 2 of 3 , Nov 13, 2003
      • 0 Attachment
        I'm not sure what you mean by "dead end". If a node can be broken
        down, into a new center node and two leaves, then at some point, the
        whole process will stop because there are no more operations to be
        performed. (In other words, how can you break down 2 down any further
        than 1 + 1 in the operations given?)

        I think that you are breaking things down too far. If you have a tree
        with all 1's or n's at leaf nodes and +,-,/, or * in the internal
        nodes, then the problem seems to indicate that that should be your
        goal condition.

        This is speculation, since I haven't worked through the problem
        myself, but these are my initial impressions.

        Brandon

        --- In aima-talk@yahoogroups.com, "chenyu468" <chenyu468@y...> wrote:
        > hi everyone,
        > 1. According to the guide, it is necessary to build a binary-tree for
        > representing the "state". The tree's leaves are "1" or "n" and
        > internal nodes are "+" "-" "*" "/" "exp" operator.
        >
        > 1. I don't know how to check the "dead end" for expression. If
        > no "dead end" check, it seems that only "breadth_first_search" is
        > acceptable. The the speed and space complexity is too high.
        >
        > 2. the "action" set for replacing "1" is 16 (20-4) by deleting "n
        > divide n", "1 divide 1", "1 multiply 1", "exp(1,1)", "
        > for replacing "n" is also 16 for the similar reason.
        > The expanding branch factor is too high (16). How to reduce it?
        >
        > 3. I don't know how to identify the "same state" from different path
        > for avoiding expanding them. Could you tell me? Or is it possible to
        > create unique tree everytime, therefore no need to identify them are
        > the same state or not?
        >
        > Thank you in advance.
        > kind regards/chenyu
      • chenyu468
        ... What I means: dead end means It is impossible to further expand the node, that s no possible action If a node can be broken ... further ... According
        Message 3 of 3 , Nov 15, 2003
        • 0 Attachment
          --- In aima-talk@yahoogroups.com, "Brandon Corfman" <bcorfman@a...>
          wrote:
          > I'm not sure what you mean by "dead end".
          What I means:
          "dead end" means "It is impossible to further expand the node, that's
          no possible action"

          If a node can be broken
          > down, into a new center node and two leaves, then at some point, the
          > whole process will stop because there are no more operations to be
          > performed. (In other words, how can you break down 2 down any
          further
          > than 1 + 1 in the operations given?)

          According the books guide, it is allowed to break down
          ("expand") "1+1". For example:
          1. replace the first "1" in "1+1" state by "(1+1)+1
          2. replace the first "1" in "1+1" state by "(1+n)+1
          3. replace the first "1" in "1+1" state by "(n+n)+1
          4. replace the first "1" in "1+1" state by "(n+1)+1 (One of my
          question is "delete this action or not, because this is same as above
          item "2")
          5. replace the first "1" in "1+1" state by "(1-1)+1
          6. replace the first "1" in "1+1" state by "(n-1)+11.
          7. replace the first "1" in "1+1" state by "(n-n)+1
          7. replace the first "1" in "1+1" state by "(1-n)+1
          ...
          ...
          ...

          Thank you for your attention.
          kind regards/chenyu


          >
          > I think that you are breaking things down too far. If you have a
          tree
          > with all 1's or n's at leaf nodes and +,-,/, or * in the internal
          > nodes, then the problem seems to indicate that that should be your
          > goal condition.
          >
          > This is speculation, since I haven't worked through the problem
          > myself, but these are my initial impressions.
          >
          > Brandon
          >
          > --- In aima-talk@yahoogroups.com, "chenyu468" <chenyu468@y...>
          wrote:
          > > hi everyone,
          > > 1. According to the guide, it is necessary to build a binary-tree
          for
          > > representing the "state". The tree's leaves are "1" or "n" and
          > > internal nodes are "+" "-" "*" "/" "exp" operator.
          > >
          > > 1. I don't know how to check the "dead end" for expression. If
          > > no "dead end" check, it seems that only "breadth_first_search" is
          > > acceptable. The the speed and space complexity is too high.
          > >
          > > 2. the "action" set for replacing "1" is 16 (20-4) by deleting "n
          > > divide n", "1 divide 1", "1 multiply 1", "exp(1,1)", "
          > > for replacing "n" is also 16 for the similar reason.
          > > The expanding branch factor is too high (16). How to reduce it?
          > >
          > > 3. I don't know how to identify the "same state" from different
          path
          > > for avoiding expanding them. Could you tell me? Or is it possible
          to
          > > create unique tree everytime, therefore no need to identify them
          are
          > > the same state or not?
          > >
          > > Thank you in advance.
          > > kind regards/chenyu
        Your message has been successfully submitted and would be delivered to recipients shortly.