From cube-lovers-errors@oolong.camellia.org Fri Jun 6 21:24:01 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 VAA11751; Fri, 6 Jun 1997 21:24:00 -0400
Precedence: bulk
Errors-To: cube-lovers-errors@oolong.camellia.org
Message-ID: <33984270.3E2C@hrz1.hrz.th-darmstadt.de>
Date: Fri, 06 Jun 1997 19:01:36 +0200
From: Herbert Kociemba
X-Mailer: Mozilla 3.0 (Win95; I)
MIME-Version: 1.0
To: cube-lovers@ai.mit.edu
Subject: Re: Detailed explanation of two phase algorithm
References: <970605193206.214149bd@iccgcc.cle.ab.com>
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Greg wrote:
>
> 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.
> .....
>
> 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.
I hardly can imagine a problem, where it makes any practical difference,
if you start with an initial treshhold determined by the heuristic
function for the initial cube state (let's denote it h0) or just start
with a treshhold of 1: In the latter case all depth 1 nodes will be
pruned immediately, and you generate exactly b*(h0-1) nodes, before you
start the search with treshhold h0, b denoting the branching factor.
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.
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).
Herbert