From cube-lovers-errors@oolong.camellia.org Thu Jun 5 22:52:37 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 WAA09130; Thu, 5 Jun 1997 22:52:37 -0400
Precedence: bulk
Errors-To: cube-lovers-errors@oolong.camellia.org
From: SCHMIDTG@iccgcc.cle.ab.com
Date: Thu, 5 Jun 1997 19:32:06 -0400 (EDT)
To: cube-lovers@ai.mit.edu
Message-Id: <970605193206.214149bd@iccgcc.cle.ab.com>
Subject: Re: Detailed explanation of two phase algorithm
Herbert Kociemba wrote:
>Reading the many contributions in the mailing list in the last days, I
>state, that the insight im my two phase algorithm solving the cube
>ranges from misunderstood to partly understood, so I will add some more
>really detailed explanation here.
Well I must account for most, if not at least some, of the misunderstanding.
Although I wasn't quite certain, I was previously under the impression
that since Korf's tables were much larger and took longer to generate that
they were somehow "better". I see now that the nature of the tables depends
almost entirely upon the particular subgroup that is being searched and so
Korf's tables may not be totally applicable to the specific subgroups
utilized in your approach.
>The memory requirements for the search algorithm are of the order
>O(d*log b), where b is the branching factor and d is the solution depth,
>so it definitely is not breadth-first search with O(b^d) nor is it
>bidirectional search with O(b^d/2).
Actually, when I mentioned O(b^d/2) for bidirectional search I was
referring to time complexity as opposed to space complexity. It still
strikes me that the two phase search is a form of bidirectional search
where one searches from both ends and the two solutions must "meet"
in the middle. I suppose it depends upon how strict one wants to
interpret the definition of bidirectional search.
>If you analyze the preceeding phase1 algorithm you will see that it is
>indeed just an IDA* with lowerbound heuristic functions based on tables.
I do not believe your phase1 is *exactly* IDA* as I think there is a
subtle difference. IDA* limits search depth based on reaching a
cost threshold whereas phase1 simply iterates uniformaly at depth
1, 2, ... N pruning nodes within the bounds of the current search depth.
At the start of a search, IDA* consults its heuristic function to determine
the initial threshold. As IDA* examines nodes, it keeps track of the
minimum cost of any node that exceeded the current threshold. It uses
that as the cost threshold for the next repeated search. So IDA* could
conceivably choose 2, 4, 5, 7, .. N for a sequence of cost threshold's
(as opposed to 1, 2, ... N) during the search.
It is this aspect of IDA* combined with the notion of an admissible
heuristic that guarantees that the first solution IDA* finds is optimal.
(Granted, you are doing a two phase search and optimality of phase1 does
not guarantee optimality of the combined solution). I agree that your
overall search is guaranteed to eventually find the combined optimal
since it iterates through all possible depth combinations.
I don't know to what extent, if at all, this difference is signficant. Of
course if it turns out that in phase1, one always happens to exceed the
current threshold by 1 for the cube problem, then I think the two algorithms
would effectively behave identically for this problem. I don't know if this
is in fact the case. But I would say that an initial depth limit computed
from your pruning tables from the initial cube state would start you off
searching at a depth greater than one with no loss of optimality.
>Herbert
Thank you for the detailed explanation of your algorithm.
-- Greg