Hi Raphael,
Thanks very much for your reply.
I'm still considering what you have suggested, but I think it might just
do the trick.
Thanks again
Mark
Raphael Collet wrote:
Hi Mark,
I am not sure to understand fully the problem to solve, but my
impression is that your constraint model makes the evaluation of the
preferences quite difficult to compute. Let me propose a different
model, and see whether it might fit in your solution.
The problem consists in determining how to order a set of scenes.
Your solution is a list of scene indices; it defines a mapping from
position in the list to scene index. It might be more efficient to
consider the inverse mapping, from scene index to position. Consider
something like this:
% a list of scene identifiers (indexes or atoms)
Scenes = ...
% maps each scene to its position in the sequence
Position = {FD.record position Scenes 1#{Length Scenes}}
{FD.distinct Position}
% the following tells that scene X must precede scene Y
Position.X <: Position.Y
The constraint above is a hard constraint: it must be satisfied. You
can make it soft by reifying '<:', which introduces an FD boolean
variable (which is 1 iff the constraint is satisfied). Summing those
boolean variables tells how many preferences are satisfied.
To determine the preference constraints, simply iterate over all pairs
of scenes, and post the required constraint. If constraints are
reified, use the 'collect' feature in the for loop to collect all
boolean preference variables.
for X in Scenes do
for Y in Scenes do
if X\=Y andthen ... % a condition on the scene
descriptions
then
% post constraint
end
end
end
Hope this helps...
Cheers,
Raphael
On Fri, Feb 19, 2010 at 3:35 PM, mark richardson
<[email protected] <mailto:[email protected]>> wrote:
Hi,
I have a program which is very similar to the 'aligning for a
photo' example. My 'people' are scenes in a narrative, each scene
is a tuple which describes a scene by type, start time and
participants. A scene might require precedent scenes, which have
the participants in various different configurations, to have
occurred before. In my script, Alignment is a list of integers
which represent indexes to the actual scnenes. The order in which
the scenes should occur is the order of the list. I am trying to
order the scenes so that as many as possible of the precedences
are satisfied.
I have functions which create a tuple with 'wild-cards' and can
then match this tuple against actual scenes. So my current
approach is to loop through each item in 'Alignment', locating the
corresponding scene and building 'wild-card' tuples for any
precedence required. I then check each preceding item in Alignment
to see if the corresponding scene matches any of these tuples.
Finally a successful match is converted to a 1, unsuccessful to a 0.
In effect it's similar to aligning people for a photo so that each
person has preferences on who should be to the left of them in the
line, which may be none or more people.
I'm having enormous problems with my program, but if someone could
suggest how the photo example could be modified to add the 'to the
right of' preference, I might be able to convert that to suit my
purposes.
Thank you in advance for any help
Regards
Mark
_________________________________________________________________________________
mozart-users mailing list
[email protected] <mailto:[email protected]>
http://www.mozart-oz.org/mailman/listinfo/mozart-users
------------------------------------------------------------------------
_________________________________________________________________________________
mozart-users mailing list
[email protected]
http://www.mozart-oz.org/mailman/listinfo/mozart-users
_________________________________________________________________________________
mozart-users mailing list
[email protected]
http://www.mozart-oz.org/mailman/listinfo/mozart-users
