From cube-lovers-errors@oolong.camellia.org Sun Jun 8 22:01:29 1997
Return-Path: cube-lovers-errors@oolong.camellia.org
Received: from oolong.camellia.org (localhost [127.0.0.1]) by oolong.camellia.org (8.6.12/8.6.12) with SMTP id WAA06481; Sun, 8 Jun 1997 22:01:29 -0400
Precedence: bulk
Errors-To: cube-lovers-errors@oolong.camellia.org
From: SCHMIDTG@iccgcc.cle.ab.com
Date: Sun, 8 Jun 1997 19:31:31 -0400 (EDT)
To: cube-lovers@ai.mit.edu
Message-Id: <970608193131.21411978@iccgcc.cle.ab.com>
Subject: Re: Detailed explanation of two phas algorithm
Herbert Kociemba wrote:
>> If one can show that the cost values have a property such that they will
>> prune all nodes at levels less then h0, then I would agree with your
>> assessment. However, I do not see why that should necessarily be
>> the case as the costs examined at lower levels could be overly optimistic
>> with respect to h0.
>
>In phase1, the heuristic function is
>h(x,y,z):=max{h1(x,y),h2(x,z),h3(y,z)}, where for example
>h1(x,y):=min {lenght of maneuvers m with m(x,y,z)=(x0,y0,z0)|z<495},
>and (x0,y0,z0) denotes the goal state.
>From this it follows, that |h(x,y,z)-h(x',y',z')| <=1, if (x',y',z') is
>a state which is the result of a single move applied on (x,y,z).
Let me try to add a bit more detail that I find helpful in this analysis.
Consider the following heuristic cost formula:
1.1 f[n] = g[n] + h[n]
Where:
f[n] is an estimate of the total path length (i.e. cost) for some
node n.
g[n] is the actual cost of the path to get to node n.
h[n] is an estimate of the cost of the path to get from node n to the
goal node (x0,y0,z0).
Let d be the current iteration depth and let D be the depth limit. Since
g[n] = d for this problem we can slightly simplify 1.1 to:
1.2 f[n] = d + h[n]
Also since we're not interested in specific nodes, but rather all nodes
at a specific depth, let n in 1.2 represent "some node at depth n".
>In particular this is true for the initial state (x,y,z) and any
>depth-one node (x',y',z'). The cost f of the depth-one node is f=1 +
>h(x',y',z'), and from the above we have h0:=h(x,y,z)<=1 + h(x',y',z')=f
The cost of the depth one node is:
1.3 f[1] = 1 + h[1] where h[1] = h(x',y',z')
and our initial estimate is:
1.4 f[0] = 0 + h[0]
or simply
1.5 f[0] = h[0]
>When we now make an iteration with an iteration depth d and dhave
1.6 dd D
or
1.9 f[d] > D
but I don't think we have shown that.
And if we want to show that all depth one nodes will be pruned when
we are at some search depth d where 1 < d < h[0] we would need to show
that:
1.9 1 + h[1] > h[0]
for all nodes at depth 1 and I don't think we have shown that either.
It seems to me that the validity of 1.9 can only be determined by taking
into consideration properties of the particular heuristic function h[n]
that is used. For any given admissible heuristic h[n], 1.9 will either
be true or false for all depth 1 nodes and I think one has to show this
based on properties of the heuristic function alone. Have I completely
missed some important point? (please be patient with me if I have :) )
>> Given an A* search algorithm, certain hard conclusions can
>> be proven (such as the guarantee that the first solution found is optimal
>> if an admissible heuristic is employed). I don't know if these same
>> conclusions can be proven with the phase1 algorithm.
>
>Obviously the first solution is optimal for phase1, because the
>maneuverlength of a later solution cannot be smaller.
Very true and for the same reason non-heuristic breadth first search always
finds optimal solutions first. I should have clarified that my interest
in this thread is to point out differences between phase1 and IDA* whether
or not these differences are important to the cube problem. I do agree
that phase1 is optimal in this particular application. However, I do
not believe that it would necessarily be optimal for problems where there
is an indirect relationship between path cost and search depth whereas IDA*
would be optimal in that case.
graphically, this could be illustrated by the following trivial search
tree:
(1)
/ \
(2) (3*) cost = .9
/
(4*) cost = .7
Suppose nodes 3 and nodes 4 were both solutions. Even though node 4
has a lower cost, phase1 would find node 3 to be our first solution
whereas IDA* wouldn't.
With respect to your program, this is completely academic, but I think
it does point out a subtle, but important difference between the two
algorithms. However, it might be important to someone wanting to apply
these algorithms to some other problem. Would you grant me that?
Best regards,
-- Greg