## 1st version exercise 3.16 sequence predication problem

Expand Messages
• 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
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?

kind regards/chenyu
• 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
> 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?
>
> kind regards/chenyu
• ... 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
...
...
...

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.