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 d<h0, we
>have

1.6	d<h[0]

and from 1.5

1.7	d<f[0]

>d<h0<=f, but d<f means, that the depth-one node will be pruned, q.e.d.

I don't see that as 1.7 does not seem sufficient to prune since we only
prune when:

1.8	d + h[d] > 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