开发者

Extending a Prolog goal through recursion?

开发者 https://www.devze.com 2022-12-18 14:10 出处:网络
I\'ve implemented (finally) a few goals that will schedule a series of tasks according to a startBy startAfter and duration. The schedule goal however, accepts only the prescribed number of tasks. I\'

I've implemented (finally) a few goals that will schedule a series of tasks according to a startBy startAfter and duration. The schedule goal however, accepts only the prescribed number of tasks. I'd like to extend the functionality of the schedule goal to accept a single list and iterate through that list while scheduling.

unfortunately I think this is going to require rather different goals than the can run and conflicts goals shown below.

UPDATE: Coming close now ... can_run/3 returns true if any one of the RT,TT pairs does not conflict ... which is decidedly not what I want, but I am close ... if anyone can tell me how to keep that from happening (perhaps using the ! operator somehow?) That would be marvelous.

UPDATE: Eet werkz! Now for cleanup of superfluous imperfect solutions (not scheduling a task) and the solution permutations (a,b,c and a,c,b and b,a,c and b,c,a etc...)

UPDATE: Bah .. okay so this isn't act开发者_开发技巧ually working ... for anything over a duration of 1 ... mutter mutter Also ... seems like it may be rather processing intensive

UPDATE (final): Got it working and implemented a "smallest window first" heuristic to improve processing time ... still have problems returning false quickly for schedules that cannot be resolved, but finding a solution comes rather quickly.

Here is what I have so far:

can_run(R,T) :- startAfter(R,TA),startBy(R,TB),between(TA,TB,T).

conflicts(R,T,RTs) :- duration(R,D),member([RT,TT],RTs),R=\=RT,duration(RT,DT),T<DT+TT,T+D>TT.

schedule :- findall(R,request(R),Rs),predsort(windowCompare,Rs,Rtn),schedule(Rtn,[]).

windowCompare(D,R1,R2) :- startAfter(R1,SA1),startBy(R1,SB1),W1=SB1-SA1,
                          startAfter(R2,SA2),startBy(R2,SB2),W2=SB2-SA2,
                          W1>W2->D='>';D='<'.

schedule(Rs,RTs) :- Rs==[];
                    (
                    member(R,Rs),select(R,Rs,Rst),
                    can_run(R,T),\+conflicts(R,T,RTs),
                    append(RTs,[[R,T]],RTN),schedule(Rst,RTN),
                    writef('%t @ %t\n',[R,T])
                    ).

request(1).
request(2).
request(3).
request(4).
request(5).
request(6).
request(7).
request(8).
request(9).

startAfter(1,0).
startAfter(2,0).
startAfter(3,0).
startAfter(4,0).
startAfter(5,0).
startAfter(6,0).
startAfter(7,0).
startAfter(8,0).
startAfter(9,0).

startBy(1,20).
startBy(2,40).
startBy(3,15).
startBy(4,5).
startBy(5,0).
startBy(6,35).
startBy(7,30).
startBy(8,10).
startBy(9,25).

duration(1,5).
duration(2,5).
duration(3,5).
duration(4,5).
duration(5,5).
duration(6,5).
duration(7,5).
duration(8,5).
duration(9,5).

I'm thinking i may need to maintain a persistent structure that each iteration updates...


If what you want is for can_run(R,T,Rts) to fail if ANY of the pairs in the list conflicts, then the final clause in your predicate should be

\+ (member([RT,TT], RTs), conflicts(T, RT,TT))

I'm not familiar with the between/3 predicate, but it is important that the effect of the solution of between(TA,TB,T) is to bind T to a ground value before the call to + (...)

0

精彩评论

暂无评论...
验证码 换一张
取 消