C
C
Ckpyt2013-01-17 14:49:18
Prolog
Ckpyt, 2013-01-17 14:49:18

The problem with the formation of the list

Given M tasks and N processors. The tasks are given a partial follow relationship and the execution time of each task. Build an optimal execution sequence
_________________

I've given up on optimality so far and reduced the task to splitting the initial list into a number of lists equal to the number of processors.


domains
  intptr=integer*
  ptrptr=intptr*
  
predicates
  sum(intptr,integer)          //суммирует весь список
  podschet(intptr,integer)  //подсчет числа членов
        
  start(ptrptr,integer,ptrptr)
  ptrSum(ptrptr,intptr)   //суммирует вложенные списки
  maxS(intptr,integer)   //находит максимальный член
  max(integer,integer,integer)  //возвращает максимум
  createSps(ptrptr,integer,integer,intptr,real)  //создает список задач проссоров
  mastSps(intptr,integer,intptr,real)  //создает список задач с суммой меньше максимальной
clauses
  max(X,Y,X):- X>Y ,!.
  max(X,Y,Y).	
  
  maxS([A|End],ANS):-!, maxS(End,ANS1),
    max(A,ANS1,ANS).
  maxS([],0).
  
  sum([A],Ans):-Ans=A.
  sum([A|Ends],ANS):-!, sum(Ends,Ans1),
    	  Ans=Ans1+A.
  sum([],0).

  ptrsum([A|Ends],[B|Endl]):-!, sum(A,B),
    ptrSum(Ends,Endl).
  ptrsum([],[]).
  
  podschet([A|Ends],ANS):-!, 
    podschet(Ends,Ans1),Ans=Ans1+1.
  podschet([],0).
    
  mastSps([],Lst,[],Max):-!,write("act1",Lst,"\n").
  mastSps([],0,[K],Max):-!,write("act2").
  mastSps([],0,[],Max).	
  mastSps([Q],Lst,[],Max):-write("act1 \n").
  mastSps([Q],0,[K|Endk],Max):-write("act2 \n"),
    mastSps([K,Q],1,Endk,Max).
  mastSps([Q|Endq],Lst,[Q|Endm],Max):-K=Lst-1,
  	  write("K=",K,"\n"),mastSps(Endq,K,Endm,Max),
    sum([Q|Endq],Sum),write("Q=",Q,Endq," "),
    Sum<Max,
    write("Sum=",Sum,"Max=",Max," "),
    Lst<5,!.

  
  createSps([],1,Lst,M,Max):-
    mastSps(Q,Lst,M,Max).
  createSps([Q|Ends],N,Lst,M,Max):-!, 
    createSps(Ends,K,Lst,M,Max), N=K-1,
    mastSps(Q,Lst,M,Max).
  
  start(M,N,Q):-!,ptrSum(M,Mk), //избавляемся от вложенных списков
    sum(Mk,A), //считаем общую длину
    podschet(Mk,Mi),   //считаем количество членов... уже просто так, на всякий случай
    Max=A/N,  //находим среднюю максимальную длину
          maxS(Mk,S), write("\nStep",Mi," ",Max,"\n"),  //находим член максимальной длины. В теории, хочу еще сравнить его со средним максимальным, но пока не знаю как быть с таким списком [1,1,1,1,18] на трех процессорах.
!!!	  mastSps(Qt,Mi,Mk,Max),write("Qt=",Qt).      //пока проверяю как работает эта функция. Почему-то не выводит список Qt
goal
  start(,2,Q),write("Q=",Q).


I will be grateful for any

help write on TurboProlog

Answer the question

In order to leave comments, you need to log in

Didn't find what you were looking for?

Ask your question

Ask a Question

731 491 924 answers to any question