С наступающим Новым годом! Форум программистов, компьютерный форум, киберфорум
Наши страницы
Prolog
Войти
Регистрация
Восстановить пароль
 
Morgan63
0 / 0 / 0
Регистрация: 12.11.2016
Сообщений: 1
1

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

18.05.2017, 15:06. Просмотров 242. Ответов 1

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

Prolog
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
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. Подскажите пожалуйста, почему предикат фейлится и как его заставить работать.
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
18.05.2017, 15:06
Ответы с готовыми решениями:

Задача на Swi-Prolog
Здравствуйте. В общем появилась проблема. Никогда не изучал пролог. И вот дали...

Задача SWI prolog
Подскажите, пожалуйста, как можно решить эту задачу? База данных содержит...

Списки в SWI-Prolog. Задача
Добрый день! Помогите, пожалуйста, решить задачу на SWI-Prolog. Задание:...

Логическая задача на SWI Prolog
Задали решить логическую задачу посредством языка пролог, лог задачи: На...

Логическая задача swi prolog
База данных содержит факты вида ученик(имя, класс) и увлекается(имя, хобби)....

1
arlat
399 / 390 / 77
Регистрация: 07.10.2013
Сообщений: 857
19.05.2017, 21:42 2
да вроде же все написано bagof/3

Добавлено через 5 минут
можете использовать findall/3, но это все-таки уже немного другая логика для обработки
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
19.05.2017, 21:42

Задача со списками (SWI-Prolog)
Доброго времени суток, Есть 2 задачи на списки: 1. Разделить список на две...

SWI-Prolog, Шахматная задача, Конь
Доброго времени суток. Столкнулся с &quot;классической&quot; задачей, о которой все...

Задача Прима-Краскала (SWI-Prolog)
Дана страна (плоская и в ней n городов). Нужно соединить города телефонной...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru