Задача сетевого планирования на SWI Prolog

В этой теме 1 ответ, 2 участника, последнее обновление  Васильев Владимир Сергеевич 5 мес. назад.

  • Автор
    Сообщения
  • #3938

    Morgan163
    Участник

    Написал программу из книги Ивана Братко по решению задачи сетевого планирования. Условие задачи:

    Дана совокупность задач t1, t2, …, имеющих времена выполнения соответственно T1, Т2, …. Все эти задачи нужно решить на m идентичных процессорах. Каждая задача может быть решена на любом процессоре, но в каждый данный момент каждый процессор решает только одну из задач. Между задачами существует отношение предшествования, определяющее, какие задачи (если таковые есть) должны быть завершены, прежде чем данная задача может быть запущена. Необходимо распределить задачи между процессорами без нарушения отношения предшествования, причем таким образом, чтобы вся совокупность задач была решена за минимальное время.

    bestfirst(Start, Solution) :-
    	biggest(Big),
    	expand([], l(Start,0/0), Big, _, yes, Solution).
    
    expand(P, l(N, _), _, _, yes, [N|P] ) :-
    	goal(N).
    
    expand(P, l(N, F/G), Bound, Tree1, Solved, Sol) :-
    	F =< Bound,
    	bagof(M/C, (s(N,M,C), not(member(M,P)) ), Succ), !,
    		succlist(G, Succ, Ts),
    		bestf( Ts, F1),
    		expand( P, t(N, F1/G,Ts), Bound, Tree1, Solved, Sol);
    	Solved = never. 
    
    expand( P, t( N, F/G, [T|Ts] ), Bound, Tree1, Solved, Sol) :-
    	F =< Bound,
    	bestf(Ts,BF), 
    	min( Bound, BF, Bound1),
    	expand( [N|P], T, Bound1, T1, Solved1, Sol),
    	continue( P, t(N, F/G, [T1|Ts] ), Bound, Tree1, Solved1, Solved, Sol).
    
    expand(_, t(_, _, [] ), _, _, never, _) :- !. 
    
    expand( _, Tree, Bound, Tree, no, _) :-
    	f( Tree, F), 
    	F > Bound. 
    
    continue( _, _, _, _, yes, yes, Sol).
    
    continue( P, t(N, F/G, [T1|Ts]), Bound, Tree1, Solved1, Solved, Sol) :-
    	(Solved1 = no, 
    	insert( T1, Ts, NTs);
    	Solved1 = never, 
    	NTs = Ts),
    	bestf(NTs, F1),
    	expand(P, t(N, F1/G, NTs), Bound, Tree1, Solved, Sol).
    
    succlist(_, [], []).
    succlist(G0, [N/C|NCs], Ts) :-
    	G is G0+C,
    	h( N, H), 
    	F is G+H,
    	succlist(G0, NCs, Ts1),
    	insert( l(N, F/G), Ts1, Ts).
    
    f(l( _, F/_ ), F).
    
    f(t( _, F/_, _ ), F).
    
    bestf([T|_],F):-
    	f( T, F).
    
    bestf( [], Big) :-
    	biggest( Big).
    
    min(X, Y, X) :-
    	X =< Y,!.
    
    min(X, Y, Y).
    
    biggest(Big):-
    	Big is 1000.
    
    s(Tasks1*[_/F|Act1]*END1,Tasks2*Act2*END2,St):-
          del(Task/D,Tasks1,Tasks2),
          not(member(T/_,Tasks2)), 
          	not(before(T,Task)),
          not(member(T1/F1,Act1)),
          	not(F<F1),
          	not(before(T1,Task)),
          Time is F+D,
          insert(Task/Time,Act1,Act2,END1,END2),
          St is END2-END1.
    
    s(Tasks*[_/F|Act1]*END,Tasks*Act2*END,0):-	
    	insertidle(F,Act1,Act2).
    
    before(Task1,Task2):-
    	prec(Task1,Task2).
    
    before(Task1,Task2):-
    	prec(Task,Task2),
    	before(Task1,Task).
    
    insert(S/A,[T/B|List],[S/A,T/B|List],F,F):-
    	A=<B,!.
    
    insert(S/A,[T/B|List],[T/B|List1],F1,F2):-
    	insert(S/A,List,List1,F1,F2).
    
    insert(S/A,[],[S/A],_,A).
    
    insert( T, Ts, [T|Ts] ) :-
    	f( T, F), 
    	bestf( Ts, F1),
    	F=<F1, !.
    
    insert( T, [T1|Ts], [T1|Ts1] ):-
    	insert( T, Ts, Ts1).
    
    insertidle(A,[T/B|List],[idle/B,T/B|List]):-
    	A<B,!.
    
    insertidle(A,[T/B|List],[T/B|List1]):-
    	insertidle(A,List,List1).
    
    del(A,[A|List],List).
    
    del(A,[B|List],[B|List1]):-
    	del(A,List,List1).
    
    goal([]*_*_).
    
    h(Tasks*CPUs*END,H):-
    	totaltime(Tasks,SumTime),
    	sumnum(CPUs,EndTime,N),
    	GlobalEnd is (SumTime+EndTime)/N,
    	(GlobalEnd>END,!,H is GlobalEnd-END;H=0).
    
    totaltime([],0).
    
    totaltime([_/T|Tasks],Tm):-
    	totaltime(Tasks,Tm1),
    	Tm is Tm1+T.
    
    sumnum([],0,0).
    
    sumnum([_/T|ListCPU],EndTm,N):-
    	sumnum(ListCPU,EndTm1,N1),
    	N is N1+1,
    	EndTm is EndTm1+T.
    
    prec(t1,t4). prec(t1,t5). prec(t2,t4).
    prec(t2,t5). prec(t3,t5). prec(t3,t6).
    prec(t3,t7).
    
    start([t1/4,t2/2,t3/2,t4/20,t5/20,t6/11,t7/11]*[idle/0,idle/0,idle/0]*0).
    
    %?-
    %start(P),Resh is 0,bestfirst(P,Resh),write(Resh).
    `

    Проблема с встроенным предикатом bagof строка 10. Подскажите пожалуйста, почему предикат фейлится и как его заставить работать.

  • #3939

    Здравствуйте. Очень сложно разобраться в вашем коде без пояснений – описания метода (алгоритма) планирования и каждого метода. Имена типа s и f ясности не добавляют. Я бы в первую очередь подумал над тем, всегда ли есть ли хоть одно решение у того предиката, который вы вызываете в bagof, ведь если решения нет – то bagof завершится неудачей, что у вас и происходит. Кроме того, вот эта конструкция not(member(...)) в bagof выглядит очень опасно. Попробуйте этот код:
    bagof(X, not(member(X, [1,2,3])), List)
    Он, как и ваш, вернет fail.

    Примите мои комментарии по коду. В программе очень много лишнего. Вам не нужно писать свой предикат del, в SWI Prolog есть встроенный delete(+List1, @Elem, -List2). Вместо min/3 я бы использовал стандартный min_member/2.

    Не пишите кучу предикатов типа totaltime, вместо них надо использовать стандартный sumlist. Вместо этого:
    L = [1/2, a/3, d2/5], totaltime(L, TotalTime).
    Можно написать так:
    L = [1/2, a/3, d2/5], findall(X, member(_/X, L), Times), sumlist(Times, TotalTime).

    Ну или в крайнем случае, реализуйте предикаты типа totaltime не рекурсивно, а через стандартный sumlist.

    Аналогичным образом sumnum можно заменить на sumlist и length.

    Вот эти insert/3, insert/5 читаются ужасно. Я не совсем понял что они делают, но кажется, что вставляют элемент в отсортированный список. Во-первых они реализованы не оптимально (на каждой итерации у insert/3 вызывается функция bestf для вставляемого элемента). Во-вторых, более эффективно для такой задачи использовать не список, а дерево. Если же эффективность не важна (только этим я могу объяснить наличие такого решения, как у вас) – рассмотрите возможность использования вместо вставки стандартной функции sort/4 примерно так:
    List = [1,5,9], Element = 4, sort(0, @=<, [Element|List], NewList).

    В результате не только функций станет меньше (и пространство имен будет менее забито), но и код станет значительно лучше читаться.

Для ответа в этой теме необходимо авторизоваться.