[gecode-users] skipping alternative branchings during search?

[Christian Schulte]

I think it might be best to do your own search engine: that's the very
reason why search is programmable in Gecode. To me it is not clear whether
this will be generally useful.

On a different note: it is better to not abuse (or reuse) a different
concept such as a branching description. They are very very delicate beasts
(actually, they are involved in the most tricky invariants in the Gecode
kernel and it took as half a year to understand the right way to do it).

Always remember: you have full access to a space inside a search engine, so
maybe that's a direction.

Christian

-----Original Message-----
From: users-bounces at gecode.org [mailto:users-bounces at gecode.org] On Behalf
Of Martin Mann
Sent: Thursday, June 08, 2006 4:23 PM
To: gecode user list
Subject: [gecode-users] skipping alternative branchings during search?


Me once more,

I am interested in the following scenario:

Given a CSP and a corresponding search tree (e.g. via DFS). During the 
enumeration of all solutions I test the solution. If it fullfills a 
certain criteria I would like to skip the alternatives of this solution 
due to the last branching (== A). Or (B): skip until a specific branching.

Think this is possible using the idea of the description stack of a 
search engine.

as a sketch in my mind it works like that:

(A) : just pop and skip the topmost BranchingDesc object from the 
description stack.

(B) : it would be neccessarry to identify the BranchingDesc objects 
(B.1) or to introduce a special tag that is placed on the stack (B.2)

(B.1) : if the BranchingDesc objects can be identified they are popped 
from stack until the searched one is reached. It's only neccessary to 
know the identifier for the description you want to jump to.

(B.2) : all are popped until the special tag description has been 
reached. but for that a special function to introduce the tags is 
neccessarry.

So my first question: is it possible? I had a closer look into the DFS 
implementation and thinking about to introduce the changes there, but I 
m not sure if it is really possible there.

Out of that my second question arises: what do you think about such a 
feature? Is it worth to become part of Gecode, or do you think I m the 
only one who would like to have it?

Or, is it already available and I m blind? ;)

Hope you arent bored ..

Martin

_______________________________________________
Gecode users mailing list
users at gecode.org https://www.gecode.org/mailman/listinfo/gecode-users