% nacteni:
/* ['4.2_17.pl']. */

% move(+Uzel, -NaslUzel, -Cena)
% Uzel - aktualni stav
% NaslUzel - novy stav
% Cena - cena prechodu

move(Tasks1*[_/F|Active1]*Fin1, Tasks2*Active2*Fin2, Cost) :-
    del1(Task/D,Tasks1,Tasks2), \+ (member(T/_,Tasks2),before(T,Task)),
    \+ (member(T1/F1,Active1),F<F1,before(T1,Task)),
    Time is F+D, insert(Task/Time,Active1,Active2,Fin1,Fin2), Cost is Fin2-Fin1.
move(Tasks*[_/F|Active1]*Fin,Tasks*Active2*Fin,0) :- insertidle(F,Active1,Active2).

before(T1,T2) :- precedence(T1,T2).
before(T1,T2) :- precedence(T,T2),before(T1,T).

insert(S/A,[T/B|L ],[ S/A,T/B|L],F,F) :- A=<B,!.
insert(S/A,[T/B|L ],[ T/B|L1],F1,F2) :- insert(S/A,L,L1,F1,F2).
insert(S/A,[],[ S/A],_,A).

insertidle(A,[T/B|L ],[ idle /B,T/B|L]) :- A<B,!.
insertidle(A,[T/B|L ],[ T/B|L1]) :- insertidle(A,L,L1).

goal([]*_*_).

% del1

del1(A,[A|T],T).
del1(A,[H|T1],[H|T2]) :- del1(A,T1,T2).

% pocatecni uzel

start([t1/4, t2/2, t3/2, t4/20, t5/20, t6/11, t7/11]*[idle/0, idle/0, idle/0]*0).

% heuristika

h(Tasks * Processors * Fin, H) :-
    totaltime(Tasks, Tottime),
    sumnum(Processors, Ftime, N),
    Finall is (Tottime + Ftime)/N,
    (Finall > Fin, ! , H is Finall - Fin ; H = 0).
    
totaltime([], 0).
totaltime([_/D | Tasks], T) :-
    totaltime(Tasks, T1), T is T1 + D.
    
sumnum([], 0, 0).
sumnum([_/T | Procs], FT, N) :-
    sumnum(Procs, FT1, N1),
    N is N1 + 1, FT is FT1 + T.

precedence( t1, t4). precedence( t1, t5). precedence( t2, t4). precedence( t2, t5).
precedence( t3, t5). precedence( t3, t6). precedence( t3, t7).

% 

biggest(99).
writelist(L):-writelist(L,1).
writelist([E|L],I):-write(I),write(': '),write(E),nl,I1 is I+1,writelist(L,I1).
writelist([],_).

run:- 
    ['4.1_9.pl'], nl,
    write('Rozvrh prace procesoru, algoritmus A*'), nl, nl,
    start(Start),
    write('Pocatecni stav: '), write(Start), nl,
    bestsearch(Start, Solution), 
    write('Nalezene reseni:'),nl,
    reverse(Solution,RSolution),
    writelist(RSolution).

:- run.

% vim: set ft=prolog:

Rozvrh prace procesoru, algoritmus A*

Pocatecni stav: [t1/4,t2/2,t3/2,t4/20,t5/20,t6/11,t7/11]*[idle/0,idle/0,idle/0]*0
Nalezene reseni:
1: [t1/4,t2/2,t3/2,t4/20,t5/20,t6/11,t7/11]*[idle/0,idle/0,idle/0]*0
2: [t1/4,t2/2,t4/20,t5/20,t6/11,t7/11]*[idle/0,idle/0,t3/2]*2
3: [t1/4,t4/20,t5/20,t6/11,t7/11]*[idle/0,t2/2,t3/2]*2
4: [t4/20,t5/20,t6/11,t7/11]*[t2/2,t3/2,t1/4]*4
5: [t4/20,t5/20,t6/11]*[t3/2,t1/4,t7/13]*13
6: [t4/20,t5/20,t6/11]*[idle/4,t1/4,t7/13]*13
7: [t5/20,t6/11]*[t1/4,t7/13,t4/24]*24
8: [t6/11]*[t7/13,t5/24,t4/24]*24
9: []*[t6/24,t5/24,t4/24]*24