#!/usr/bin/env python
# encoding=utf-8 (pep 0263)
from __future__ import division
from linked_lists import LinkedList, Cons, Nil, member_anyX
from best_search import BestSearch
biggest = 99
start = (LinkedList([("t1", 4), ("t2", 2), ("t3", 2), ("t4", 20),
("t5", 20), ("t6", 11), ("t7", 11)]),
LinkedList([("idle", 0), ("idle", 0), ("idle", 0)]), 0)
precedence = dict(
t1=["t4", "t5"],
t2=["t4", "t5"],
t3=["t5", "t6", "t7"])
def goes_before(T1, T2):
if T1 in precedence:
if T2 in precedence[T1]:
return True
for T in precedence[T1]:
if goes_before(T, T2):
return True
return False
def is_goal(state):
# zavisi na resenem problemu
waiting, _, _ = state
return waiting == Nil
def move_anyYC(state):
# zavisi na resenem problemu
tasks1, active, fin1 = state
_, f = active.head
active1 = active.tail
for (task, d), tasks2 in del1_anyX(tasks1):
permissible = True
for t, _ in member_anyX(tasks2):
if goes_before(t, task):
permissible = False
for t1, f1 in member_anyX(active1):
if f < f1 and goes_before(t1, task):
permissible = False
if not permissible:
continue
active2, fin2 = insert((task, f+d), active1, fin1)
cost = fin2 - fin1
yield ((tasks2, active2, fin2), cost)
for active3 in insert_idle(f, active1):
yield ((tasks1, active3, fin1), 0)
def insert(task, active, f1):
s, a = task
if active == Nil:
return (Cons((s, a), Nil), a)
t, b = active.head
l = active.tail
if a <= b:
return (Cons((s, a), active), f1)
l1, f2 = insert((s, a), l, f1)
return (Cons((t, b), l1), f2)
def insert_idle(a, active):
if active == Nil:
return
t, b = active.head
l = active.tail
if a < b:
yield Cons(("idle", b), active)
else:
for l1 in insert_idle(a, l):
yield Cons((t, b), l1)
def h(state):
waiting, active, fin = state
waiting_time = 0
for _, execution_time in waiting:
waiting_time = waiting_time + execution_time
active_time = 0
cpu_number = 0
for _, finishing_time in active:
active_time = active_time + finishing_time
cpu_number = cpu_number + 1
finall = (waiting_time + active_time) / cpu_number
return max(finall - fin, 0)
def del1_anyX(ys):
if ys == Nil:
return
yield (ys.head, ys.tail)
for (z, zs) in del1_anyX(ys.tail):
yield (z, Cons(ys.head, zs))
def writelist(xs):
writelist_(xs, 1)
def writelist_(xs, i):
if xs != Nil:
print("%d: %s" % (i, xs.head))
writelist_(xs.tail, i+1)
# demonstracni vypis
if __name__ == "__main__":
print("Rozvrh prace procesoru, algoritmus A*\n")
print("Pocatecni stav: %s" % (start,))
print("\nNalezene reseni:")
astar = BestSearch(biggest, is_goal, move_anyYC, h)
solution = next(astar.search(start))
print("Prohledano %d stavu, vysledne reseni ma cenu %d." % (astar.total, solution.head[2]))
writelist(solution.reverse())
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:
Prohledano 124 stavu, vysledne reseni ma cenu 24.
1: ([('t1', 4), ('t2', 2), ('t3', 2), ('t4', 20), ('t5', 20), ('t6', 11), ('t7', 11)], [('idle', 0), ('idle', 0), ('idle', 0)], 0)
2: ([('t2', 2), ('t3', 2), ('t4', 20), ('t5', 20), ('t6', 11), ('t7', 11)], [('idle', 0), ('idle', 0), ('t1', 4)], 4)
3: ([('t3', 2), ('t4', 20), ('t5', 20), ('t6', 11), ('t7', 11)], [('idle', 0), ('t2', 2), ('t1', 4)], 4)
4: ([('t4', 20), ('t5', 20), ('t6', 11), ('t7', 11)], [('t3', 2), ('t2', 2), ('t1', 4)], 4)
5: ([('t4', 20), ('t5', 20), ('t7', 11)], [('t2', 2), ('t1', 4), ('t6', 13)], 13)
6: ([('t4', 20), ('t5', 20), ('t7', 11)], [('idle', 4), ('t1', 4), ('t6', 13)], 13)
7: ([('t4', 20), ('t7', 11)], [('t1', 4), ('t6', 13), ('t5', 24)], 24)
8: ([('t7', 11)], [('t6', 13), ('t4', 24), ('t5', 24)], 24)
9: ([], [('t7', 24), ('t4', 24), ('t5', 24)], 24)
| % 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
|