Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <list>
- #include <algorithm>
- #include <fstream>
- #include <stdlib.h>
- #include <queue>
- #include <string>
- using namespace std;
- template <class T>
- class Kopiec
- {
- private:
- T * tablicaElementow;
- int iloscElementow;
- bool (*funkcjaPorownujaca)(const T &, const T &);
- public:
- int push(T element);
- T pop();
- T top();
- bool empty();
- void wypisz();
- Kopiec (bool (*compare)(const T &, const T &));
- };
- class Zadanie
- {
- public:
- int r, p, q, nr, t_on;
- friend ostream & operator<< (ostream & strumWyj, const Zadanie & doWypisania);
- static bool compR(const Zadanie &it1, const Zadanie &it2) {
- return it1.r > it2.r; //UWAGA NA KIERUNEK!!
- }
- static bool compQ(const Zadanie &it1, const Zadanie &it2){
- return it1.q < it2.q; ///UWAGA NA KIERUNEK!
- }
- Zadanie(int rr, int pp, int qq, int nnr);
- Zadanie(void);
- ~Zadanie(void);
- };
- class Permutacja
- {
- public:
- vector<Zadanie> listaZadan; //vector przechowujacy zadaną kolejnosc wykonywania zadan
- int n; //ilosc wczytanych zadan
- int Cmax; //moment zakonczenia q ostatniego zadania
- int LB; //wartosc Cmax zwrocona przez algorytm Schrage z przerywaniami
- int a,b; //indeksy początku i konca sciezki krytycznej
- int c; //indeks zadania interferencyjnego
- int sLB; //szybki LB. wg tego permutacje są kopcowane;
- int Schrage(); //algorytm Schrege'a: modyfikuje kolejnosc listyZadan
- int SciezkaKrytyczna(); //metoda odnajduje w liscieZadan sciezke krytyczna.
- //indeksy poczatku i konca przypisuje do pol a i b;
- int ZadanieInterferencyjne(); //metoda odnajduje zadanie interferencyjne w sciezce krytycznej
- // wymaga poprawnie oznaczonej sciezki przez pola a i b.
- // modyfikuje pole c;
- int h(int aa, int bb); // metoda zwraca wartosc rmin+sumap+qmin dla zadanego przedziału;
- int rMin(int aa, int bb); //metoda wyszukuje najmniejszy r z zadanego przedziału
- int qMin(int aa, int bb); //metoda wyszukuje najmniejsze q z zadanego przedziału;
- int sumaP(int aa, int bb); //metoda zwraca sume p z zadanego przedziału
- int rMinBloku(); //Trzy metody zwracają odpowiednie parametry BlokuK - zadan
- //od pierwszego za zadaniem interferencyjnym do ostatniego na
- int qMinBloku(); //sciezce krytycznej.
- int sumaPBloku();
- int SchragePtm(); //metoda zwraca wartosc Cmax algorytmu Schrage z przerywaniami. Modyfikuje pole LB
- int szybkiLB(); //metoda generuje szybki LB;
- void testyEliminacyjne(int UB);
- static bool cmpsLB (const Permutacja & p1, const Permutacja & p2) {
- return p1.sLB < p2.sLB;
- }
- friend ostream & operator << (ostream & strumienWyjsciowy, Permutacja & doWypisania);
- Permutacja (char * nazwa_pliku);
- Permutacja(void);
- ~Permutacja(void);
- };
- int Carlier(char * pliki, char * pliko);
- Permutacja::Permutacja(char * nazwa_pliku)
- {
- int rozmiar; //zmienna pozorowana. trzeba gdzies wczytac "3"
- ifstream plikin(nazwa_pliku);
- plikin >> n;
- plikin >> rozmiar;
- Zadanie * wczytywane;
- int rr, pp, qq;
- for (int i=0; i<n; i++) {
- plikin >> rr >> pp >> qq;
- wczytywane = new Zadanie(rr,pp,qq,i+1);
- listaZadan.push_back(*(wczytywane));
- delete wczytywane;
- }
- plikin.close();
- }
- int Permutacja::Schrage()
- {
- int aktualnyCzas = 0;
- int _Cmax = 0;
- Kopiec<Zadanie> kopiecZadan(&Zadanie::compR); //kopiec z wszystkimi zadaniami posortowanymi wg. R
- for (int i=0; i<n; i++)
- kopiecZadan.push(listaZadan[i]);
- Kopiec<Zadanie> dostepneZadania(&Zadanie::compQ); //kopiec dostepnych w danej chwili czasowej zadan; posortowana od największego Q
- vector<Zadanie> listaSchrage; //lista uszeregowana wg. algorytmu Schrage'a. pod koniec metody podpinana pod listeZadan
- while ((!kopiecZadan.empty()) || (!dostepneZadania.empty())) {
- while ((!kopiecZadan.empty()) && (kopiecZadan.top().r<=aktualnyCzas)) {
- dostepneZadania.push(kopiecZadan.top());
- kopiecZadan.pop();
- }
- if (dostepneZadania.empty()) {
- aktualnyCzas=kopiecZadan.top().r;
- }
- else {
- listaSchrage.push_back(dostepneZadania.top()); //dodajesz zadanie do listy
- dostepneZadania.pop(); //usuwa zadanie z puli dostepnych
- listaSchrage.back().t_on=aktualnyCzas; //ustawia realny czas rozpoczecia realizacji zadania na maszynie
- aktualnyCzas+=listaSchrage.back().p; //aktualizuje czas
- if (aktualnyCzas + listaSchrage.back().q > _Cmax)
- _Cmax=aktualnyCzas + listaSchrage.back().q;
- }
- }
- Cmax=_Cmax;
- listaZadan.clear();
- listaZadan=listaSchrage;
- listaSchrage.clear();
- return Cmax;
- }
- int Permutacja::SciezkaKrytyczna()
- {
- int aktualnyMax=0;
- for (int i=0; i < n; i++) { //przejrzyj listeZadan. jezeli moment rozpoczecia realizacji+r+q = Cmax,
- if (listaZadan[i].t_on+listaZadan[i].p+listaZadan[i].q > aktualnyMax) { //to mamy zadanie, ktore konczy caly proces
- b=i;
- aktualnyMax=listaZadan[i].t_on+listaZadan[i].p+listaZadan[i].q;
- }
- }
- a=b;
- while ((a>=1) && (listaZadan[a-1].t_on+listaZadan[a-1].p >= listaZadan[a].r) ){
- a--;
- }
- return 0;
- }
- int Permutacja::ZadanieInterferencyjne()
- {
- bool znalezionoC = false;
- for(int i=b-1; i>=a; i--)
- if ((!znalezionoC) && (listaZadan[i].q < listaZadan[b].q)) {
- znalezionoC=true;
- c=i;
- }
- if (znalezionoC==true)
- return 1;
- else
- return 0;
- }
- int Permutacja::rMinBloku() {
- return rMin(c+1,b);
- }
- int Permutacja::qMinBloku() {
- return qMin(c+1,b);
- }
- int Permutacja::sumaPBloku() {
- return sumaP(c+1,b);
- }
- int Permutacja::SchragePtm()
- {
- int aktualnyCzas = 0;
- int _Cmax = 0;
- vector<Zadanie>listaNieprzydzielonych; //ze wzgledu na konieczność swobodnego dostepu do wszystkich zadan nie mozna tego realizowac na kopcu.
- listaNieprzydzielonych = listaZadan; //tworzymy kopie listy zadan
- sort(listaNieprzydzielonych.begin(), listaNieprzydzielonych.end(), Zadanie::compR);
- Kopiec<Zadanie> listaDostepnych(&Zadanie::compQ); //kopiec dostepnych w danej chwili czasowej zadan. Posortowany od najwiekszego Q
- vector<Zadanie> listaSchrage; //lista uszeregowana wg. algorytmu Schrage'a. pod koniec metody podpinana pod listeZadan
- Kopiec<Zadanie> listaPrzerwan(&Zadanie::compQ); //lista tych zadan, na rzecz ktorych moze wystapic przerwanie.
- //Posortowana od najmniejszego R
- while ((!listaNieprzydzielonych.empty()) || (!listaDostepnych.empty())) {
- while ((!listaNieprzydzielonych.empty()) && (listaNieprzydzielonych.back().r<=aktualnyCzas)) {
- listaDostepnych.push(listaNieprzydzielonych.back()); //tworzymy listę zadan, ktorych r juz uplynelo
- listaNieprzydzielonych.pop_back();
- }
- if (listaDostepnych.empty()) {
- aktualnyCzas=listaNieprzydzielonych.back().r;
- }
- else {
- while (!listaPrzerwan.empty())
- listaPrzerwan.pop(); //czyszczenie listy przerwan
- for (int i=0; i< (int)listaNieprzydzielonych.size();i++) //tworzenie nowej listy przerwan
- if ((listaDostepnych.top().p + aktualnyCzas > listaNieprzydzielonych[i].r)&&(listaDostepnych.top().q < listaNieprzydzielonych[i].q))
- listaPrzerwan.push(listaNieprzydzielonych[i]); //na liste przerwan kladziemy te zadania, ktorych q jest wieksze od aktualnie dodawanego algorytmem Schrage'a
- //a r miesci sie w przedziale (aktualnyCzas, aktualnyCzas+p dodawanego). Na rzecz tych zadan powinno wystąpić przerwanie.
- //elementy na liscie przerwan sa kopiami!
- if (listaPrzerwan.empty()) { //nie ma przerwan - normalna procedura Schrage'a
- listaSchrage.push_back(listaDostepnych.top()); //dodajesz zadanie do listy
- listaDostepnych.pop(); //usuwa zadanie z puli dostepnych
- listaSchrage.back().t_on=aktualnyCzas; //ustawia realny czas rozpoczecia realizacji zadania na maszynie
- aktualnyCzas+=listaSchrage.back().p; //aktualizuje czas
- if (aktualnyCzas + listaSchrage.back().q > _Cmax)
- _Cmax=aktualnyCzas + listaSchrage.back().q;
- }
- else { //przerwanie
- Zadanie part1 = listaDostepnych.top();
- listaDostepnych.pop();
- Zadanie part2=part1;
- part1.p=listaPrzerwan.top().r-aktualnyCzas; //część zadania, która zrealizuje się do momentu przerwania.
- part2.p-=part1.p; //pozostała część zadania: od part2.p (==part1.p oryginalnego) odejmujesz część, która będzie zrealizowana
- listaDostepnych.push(part2); //reszta realizowanego zadania trafia spowrotem do listy dostepnych zadan
- listaSchrage.push_back(part1);
- listaSchrage.back().t_on=aktualnyCzas;
- aktualnyCzas+=listaSchrage.back().p;
- if (aktualnyCzas + listaSchrage.back().q > _Cmax)
- _Cmax=aktualnyCzas + listaSchrage.back().q;
- }
- }
- }
- return _Cmax;
- }
- ostream & operator << (ostream & strumienWyjsciowy, Permutacja & doWypisania)
- {
- for (int i=0; i < (int)doWypisania.listaZadan.size(); i++)
- strumienWyjsciowy<<doWypisania.listaZadan[i];
- return strumienWyjsciowy;
- }
- Permutacja::Permutacja(void)
- {
- }
- Permutacja::~Permutacja(void)
- {
- }
- int Permutacja::szybkiLB()
- {
- sLB=max(h(c+1,b), h(c,b));
- return sLB;
- }
- int Permutacja::rMin(int aa, int bb)
- {
- int rmin=listaZadan.at(a).r;
- for (int i=a; i<=b; i++) {
- if (listaZadan.at(i).r<rmin)
- rmin=listaZadan.at(i).r;
- }
- return rmin;
- }
- int Permutacja::qMin(int aa, int bb)
- {
- int qmin=listaZadan.at(a).q;
- for (int i=a; i<=b; i++) {
- if (listaZadan.at(i).q<qmin)
- qmin=listaZadan.at(i).q;
- }
- return qmin;
- }
- int Permutacja::sumaP(int aa, int bb)
- {
- int sumaP=0;
- for (int i=a; i<=b; i++) {
- sumaP+=listaZadan.at(i).p;
- }
- return sumaP;
- }
- int Permutacja::h(int aa, int bb)
- {
- if ((aa<0) || (aa>bb) || (bb>(int)listaZadan.size())) {
- cerr<<"błąd wywołania funkcji h(int, int)\n";
- return 0;
- }
- return (rMin(aa,bb)+sumaP(aa,bb)+qMin(aa,bb));
- }
- void Permutacja::testyEliminacyjne(int UB)
- {
- int hK=h(c+1,b);
- for (int i=0; i< (int) listaZadan.size(); i++) {
- if ((i<a)||(i>b)) {
- if (listaZadan[i].p > UB - hK) { //i należy do L
- if(listaZadan[i].r+listaZadan[i].p+sumaPBloku()+listaZadan[b].q >= UB )
- listaZadan[i].r=max(listaZadan[i].r, rMinBloku() + sumaPBloku());
- else if (rMinBloku()+listaZadan[i].p + sumaPBloku()+ listaZadan[i].q >=UB)
- listaZadan[i].q=max(listaZadan[i].q,qMinBloku()+sumaPBloku());
- }
- }
- }
- }
- Zadanie::Zadanie(int rr, int pp, int qq, int nnr) {
- r=rr;
- p=pp;
- q=qq;
- nr=nnr;
- t_on=0;
- }
- ostream & operator << (ostream & strumWyj, const Zadanie & doWypisania)
- {
- strumWyj<<"Nr: "<<doWypisania.nr<<"\tr: "<<doWypisania.r<<"\tp: "<<doWypisania.p<<"\tq: "<<doWypisania.q<<"\tt_on: "<<doWypisania.t_on<<endl;
- return strumWyj;
- }
- Zadanie::Zadanie(void)
- {
- }
- Zadanie::~Zadanie(void)
- {
- }
- #pragma region Kopiec
- template <class T>
- Kopiec<T>::Kopiec(bool (*cmp)(const T & ,const T & ))
- {
- iloscElementow = 0;
- funkcjaPorownujaca = cmp;
- tablicaElementow=NULL;
- }
- template <class T>
- int Kopiec<T>::push(T element)
- {
- if (iloscElementow==0) { //dodajemy na szczyt kopca
- tablicaElementow = new T[1];
- tablicaElementow[iloscElementow]=element;
- iloscElementow++;
- return 1;
- }
- else {
- T * temp = tablicaElementow;
- tablicaElementow = new T [iloscElementow+1];
- copy(temp, temp+iloscElementow, tablicaElementow);
- delete [] temp;
- int aktualnyIndeks=iloscElementow;
- int indeksOjca=iloscElementow/2;
- T tmp;
- tablicaElementow[iloscElementow]=element;
- while ((indeksOjca>=0) && (funkcjaPorownujaca(tablicaElementow[indeksOjca],tablicaElementow[aktualnyIndeks])))
- {
- tmp = tablicaElementow[indeksOjca];
- tablicaElementow[indeksOjca]=tablicaElementow[aktualnyIndeks];
- tablicaElementow[aktualnyIndeks]=tmp;
- aktualnyIndeks=indeksOjca;
- indeksOjca/=2;
- }
- iloscElementow++;
- return iloscElementow;
- }
- }
- template <class T>
- T Kopiec<T>::pop()
- {
- T doZwrotu;
- if (iloscElementow==0)
- {
- cerr<<"Brak elementow na kopcu!"<<endl;
- return doZwrotu;
- }
- doZwrotu = tablicaElementow[0];
- tablicaElementow[0]=tablicaElementow[iloscElementow-1];
- int aktualnyIndeks=0;
- while ((((aktualnyIndeks+1)*2-1<iloscElementow-1)&&(funkcjaPorownujaca (tablicaElementow[aktualnyIndeks],tablicaElementow[(aktualnyIndeks+1)*2-1]))) || //jezeli ktores z dzieci jest wieksze - zamien z wiekszym z nich
- (((aktualnyIndeks+1)*2<iloscElementow-1)&&(funkcjaPorownujaca (tablicaElementow[aktualnyIndeks],tablicaElementow[(aktualnyIndeks+1)*2]))))
- {
- if (funkcjaPorownujaca(tablicaElementow[(aktualnyIndeks+1)*2-1], tablicaElementow[(aktualnyIndeks+1)*2])) //jeżeli prawe dziecko jest wieksze
- { // to z nim zamieniamy aktualny indeks
- T tmp = tablicaElementow[(aktualnyIndeks+1)*2];
- tablicaElementow[(aktualnyIndeks+1)*2]=tablicaElementow[aktualnyIndeks];
- tablicaElementow[aktualnyIndeks]=tmp;
- aktualnyIndeks=(aktualnyIndeks+1)*2;
- }
- else
- {
- T tmp = tablicaElementow[(aktualnyIndeks+1)*2-1];
- tablicaElementow[(aktualnyIndeks+1)*2-1]=tablicaElementow[aktualnyIndeks];
- tablicaElementow[aktualnyIndeks]=tmp;
- aktualnyIndeks=(aktualnyIndeks+1)*2-1;
- }
- }
- iloscElementow--;
- T * temp = tablicaElementow;
- tablicaElementow = new T [iloscElementow];
- copy(temp, temp+iloscElementow, tablicaElementow);
- delete [] temp;
- return doZwrotu;
- }
- template <class T>
- T Kopiec<T>::top()
- {
- T doZwrotu;
- if (iloscElementow==0)
- {
- cerr<<"Brak elementow na kopcu!\n";
- return doZwrotu;
- }
- doZwrotu = tablicaElementow[0];
- return doZwrotu;
- }
- template <class T>
- void Kopiec<T>::wypisz()
- {
- for (int i=0; i<iloscElementow; i++)
- {
- cout<<"Indeks: "<<i<<" wartosc: "<<tablicaElementow[i]<<endl;
- }
- }
- template <class T>
- bool Kopiec<T>::empty()
- {
- if (iloscElementow==0)
- return true;
- else
- return false;
- }
- #pragma endregion Kopiec
- int Carlier(char * pliki, char * pliko) {
- int LB, UB;
- bool znalezionoOptymalne = false;
- Permutacja permut0(pliki);
- Permutacja optymalna, aktualna, potomek1, potomek2;
- permut0.sLB=1; //i tak jest zdejmowana odrazu
- Kopiec<Permutacja> kolejkaCarliera(&Permutacja::cmpsLB);
- UB=permut0.Schrage();
- LB=permut0.SchragePtm();
- kolejkaCarliera.push(permut0);
- optymalna=permut0;
- while (!kolejkaCarliera.empty()) { //&&(!znalezionoOptymalne) ?
- aktualna=kolejkaCarliera.top();
- kolejkaCarliera.pop();
- if (aktualna.SchragePtm() < UB){ //najlepszy możliwy jest lepszy od znalezionego UB - dzielimy problem
- aktualna.Schrage();
- if (aktualna.Cmax < UB) { //układamy wg. algorytmu Schrage. Jezeli znaleźliśmy lepsze rozwiazanie - zapisujemy je.
- UB=aktualna.Cmax;
- optymalna=aktualna;
- }
- aktualna.SciezkaKrytyczna();
- if(aktualna.ZadanieInterferencyjne()) {
- aktualna.testyEliminacyjne(UB);
- potomek1=potomek2=aktualna;
- potomek1.listaZadan[potomek1.c].r=potomek1.rMinBloku()+potomek1.sumaPBloku();
- potomek2.listaZadan[potomek2.c].q=potomek2.qMinBloku()+potomek2.sumaPBloku();
- potomek1.szybkiLB();
- potomek2.szybkiLB();
- kolejkaCarliera.push(potomek1);
- kolejkaCarliera.push(potomek2);
- }
- else {
- znalezionoOptymalne=true;
- cout<<"znaleziono lokalnie optymalne: "<< aktualna.Cmax<<endl;
- }
- }
- }
- cout<<"Cmax znalezionego: "<<optymalna.Cmax<<endl;
- ofstream plikout(pliko);
- //plikout<<"1 "<<optymalna.n<<endl;
- for(int i=0;i<optymalna.n;i++){
- plikout<<optymalna.listaZadan[i].nr<<" ";
- }
- plikout<<endl<<optymalna.Cmax;
- plikout.close();
- return optymalna.Cmax;
- }
- int main () {
- char pause;
- Carlier("in50.txt", "out50.txt");
- Carlier("in100.txt", "out100.txt");
- Carlier("in200.txt", "out200.txt");
- cin >> pause;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement