From cube-lovers-errors@oolong.camellia.org Sat Jun 7 15:57:59 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 PAA03635; Sat, 7 Jun 1997 15:57:58 -0400
Precedence: bulk
Errors-To: cube-lovers-errors@oolong.camellia.org
From: SCHMIDTG@iccgcc.cle.ab.com
Date: Sat, 7 Jun 1997 1:50:04 -0400 (EDT)
To: cube-lovers@ai.mit.edu
Message-Id: <970607015004.21414d85@iccgcc.cle.ab.com>
Subject: Re: Detailed explanation of two phase algorithm
On the subject of differences between IDA* and the phase1 algorithm,
Herbert Kociemba wrote:
>Because h0<=9 in phase1 and b=18 for the first node, you generate at
>most 162 nodes too much, which from a practical point of view is
>nothing. In the general case, h0<=N, where N is the minimal solution
>length, and you generate at most (N-1)*b nodes too much - so it really
>makes no difference.
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.
For example. Let's say that we are iterating through the search and
our current depth limit happens to be 5. Now we examine the first node
at level one. Your analysis above assumes that this node (and all others
at this level for that matter) will be pruned. Now let's also say that
I now consult the pruning tables and compute an overly optimistic lower
bound cost of 3. We now add the 3 to our current depth of 1 and since
3+1<5 we would not prune that node. So if this can occur, I think one
is actually looking at evaluating b^(h0-1) additional nodes in the worst
case.
>Does it make a difference if you increase the treshhold to the cost of
>the lowest-cost node, that was pruned during the iteration or just
>increase the treshhold by 1, if you start the next iteration? In case of
>the cube, this question seems a bit academical. I can't believe, that it
>is possible to omit a certain iteration depth >h0, though I must admit
>that I found no obvious proof for that using the properties of the
>heuristic functions in phase1 or phase2 (and it only depends on these
>functions).
While I believe your phase1 algorithm is certainly ID (iterative deepening),
I do not believe it is A* since the depth limit is not based purely on
the cost. 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. However, I agree
that from a purely practical standpoint and considering this particular
application of the algorithm to the cube problem this *may* not be an
important distinction. But I don't think that conclusion has yet
been fully established.
-- Greg