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

Re: 1st version exercise 3.16 sequence predication problem

Expand Messages
  • 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 1 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 2 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.