Hi,
I have a further question regarding this problem. Just to recap, I am
ordering narrative scenes by time and precedence. In other words, all
scenes MUST be ordered in time (this constraint overrides all others)
and also, scenes which occur at the same time are ordered by causality -
this is implemented by searching for the maximal value of the sum of all
scenes which have been identified as having a precedence scene. I have a
function {IsPreced X Y} which returns true if X is a preceding scene of
Y, false otherwise.
The main solver script is this:
fun {Sorter Ls}
%%Ls is a list of unsorted scenes
proc {$ Root}
Preced
%%a list of indexes to the actual scene list
Scenes={List.number 1 {Length Ls} 1}
%%a FD record for the position of each scene
%%ie Position.X is the position of scene X
Position={FD.record position Scenes 1#{Length Scenes}}
%%FD var for number of satisfied precedence constraints
NumPrec={FD.decl}
in
%%a record representing any precedent scenes found
Preced={FD.record preced Scenes 0#{Length Scenes}}
%%only one precedence action used at a time
%%ie a scene can not be a precedence of another scene more than once
for X in 1..{Length Scenes} do
{FD.atMost 1 Preced X}
end
Root=r(numprecedences: NumPrec position: Position preced : Preced)
{FD.distinct Position}
%%just to limit NumPrec to a sensible value
NumPrec<:{Length @AllScenes}
%%if time of X is before time of Y then order accordingly
for X in Scenes do
for Y in Scenes do
if X\=Y andthen {Utils.getDetails scene time {Nth Ls X}
}<{Utils.getDetails scene time {Nth Ls Y}} then
Position.X<:Position.Y
end
%%if X is a precedent scene for Y, update Preced record if not
already found
if X\=Y andthen {IsPreced X Y} then
if {Not {IsDet Preced.Y}} then Preced.Y=:X end
end
end
end
%%finally, sum the number of scenes which have matching precedent
scenes
{FD.sum for X in Scenes collect:Collect do
for Y in Scenes do
if X\=Y andthen {IsPreced X Y} then %X is a precedent
of Y
{Collect (Position.X=<:Position.Y)}
end
end
end '=:' NumPrec}
%%search for highest number of matching precedences first
{FD.distribute generic(order:naive value:max) [NumPrec]}
%%then look for positions
{FD.distribute ff Position}
%%and keep Preced record updated
{FD.distribute naive Preced}
end
end
Preced is a record which contains fields that are either 0 or a
reference to a matching precedence scene. The number of fields which are
NOT 0 should in theory match the value of NumPrec.
This script gives a single solution which looks okay at first glance.
NumPrec is determined as 6 and I get 6 entries in my Preced record
matching the 6 identified precedences.
However, if I search for further solutions in the explorer, I can find
solutions which have 7 or more entries in the Preced record (ie 7 or
more matched precedences) but NumPrec is still determined as 6 - why
isn't this 7 or more?
This is something I am at a loss to explain. If anyone could shed any
light on this I would be extremely grateful.
Also, as an afterthought, I wondered if the distribution steps for
Position and Preced can be combined into one statement without affecting
the script?
Regards
Mark
Raphael Collet wrote:
Dear Mark,
I wrote "simple", because this solution might be very efficient if
many of the preferences are conflicting. The issue is that a
propagator like
B = (X =<: Y)
will perform no propagation until either B is known, or both X and Y
are known. To get maximal performance, you need to have as much
propagation as possible. A good heuristics might be to determine the
B's as soon as possible. Something like
Bs = for X in Scenes collect:Collect do
for Y in Scenes do
if X\=Y andthen {IsPreced X Y} then %X is a precedent of Y
{Collect (Position.X=<:Position.Y)}
end
end
end
{FD.sum Bs '=:' NumPrec}
%% determine NumPrec, then the Bs, trying high values first, then the
positions
{FD.distribute generic(order:naive value:max) NumPrec|Bs}
{FD.distribute ff Position}
I haven't tried it, but that's something you could give a try at.
Cheers,
Raphael
On Thu, Feb 25, 2010 at 1:00 PM, mark richardson
<[email protected] <mailto:[email protected]>> wrote:
Hi,
Thank you so much for your help with this.
I did have another small problem that I have now solved - I had
{IsPreced X Y} returning true if Y had no precedences at all which
was causing chaos.
(Oh and I deliberately left the distribution of the position
vector out of the message, but thank you for your reminder :+) )
You say that this approach is a 'simple way to maximize the number
of preferences'.
I might regret asking this, but is there a way which is less
simple, but perhaps better?
Regards
Mark
Raphael Collet wrote:
Dear Mark,
Yes, I think you got it right. That is a simple way to maximize
the number of preferences. (Just don't forget to distribute the
vector Position in your script.)
Cheers,
Raphael
On Thu, Feb 25, 2010 at 12:26 PM, mark richardson
<[email protected] <mailto:[email protected]>> wrote:
Hi,
I've modified the script slightly to this:
{FD.sum
for X in Scenes collect:Collect do
for Y in Scenes do
if X\=Y andthen {IsPreced X Y} then %X is a precedent of Y
{Collect (Position.X=<:Position.Y)}
end
end
end '=:' NumPrec}
I realised the mistake I was making with X and Y instead of
Position.X and Position.Y and mistyping 'and' instead of
'andthen'
Regards
Mark
--
Mark Richardson MBCS
Research Assistant
University of Teesside, UK
Email: [email protected]
<mailto:[email protected]>
[email protected] <mailto:[email protected]>
Skype: mark.richardson.
_________________________________________________________________________________
mozart-users mailing list
[email protected] <mailto:[email protected]>
http://www.mozart-oz.org/mailman/listinfo/mozart-users
------------------------------------------------------------------------
_________________________________________________________________________________
mozart-users mailing list [email protected]
<mailto:[email protected]>
http://www.mozart-oz.org/mailman/listinfo/mozart-users
--
Mark Richardson MBCS
Research Assistant
University of Teesside, UK
Email: [email protected] <mailto:[email protected]>
[email protected] <mailto:[email protected]>
Skype: mark.richardson.
_________________________________________________________________________________
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
--
Mark Richardson MBCS
Research Assistant
University of Teesside, UK
Email: [email protected]
[email protected]
Skype: mark.richardson.
_________________________________________________________________________________
mozart-users mailing list
[email protected]
http://www.mozart-oz.org/mailman/listinfo/mozart-users
