Advertisement
Guest User

Untitled

a guest
Apr 26th, 2015
197
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 15.60 KB | None | 0 0
  1.  
  2. #include <iostream>
  3. #include <vector>
  4. #include <list>
  5. #include <algorithm>
  6. #include <fstream>
  7. #include <stdlib.h>
  8. #include <queue>
  9. #include <string>
  10.  
  11. using namespace std;
  12.  
  13.  
  14. template <class T>
  15. class Kopiec
  16. {
  17. private:
  18. T * tablicaElementow;
  19. int iloscElementow;
  20. bool (*funkcjaPorownujaca)(const T &, const T &);
  21. public:
  22. int push(T element);
  23. T pop();
  24. T top();
  25. bool empty();
  26. void wypisz();
  27. Kopiec (bool (*compare)(const T &, const T &));
  28.  
  29. };
  30.  
  31. class Zadanie
  32. {
  33. public:
  34. int r, p, q, nr, t_on;
  35.  
  36. friend ostream & operator<< (ostream & strumWyj, const Zadanie & doWypisania);
  37. static bool compR(const Zadanie &it1, const Zadanie &it2) {
  38. return it1.r > it2.r; //UWAGA NA KIERUNEK!!
  39. }
  40. static bool compQ(const Zadanie &it1, const Zadanie &it2){
  41. return it1.q < it2.q; ///UWAGA NA KIERUNEK!
  42. }
  43.  
  44. Zadanie(int rr, int pp, int qq, int nnr);
  45. Zadanie(void);
  46. ~Zadanie(void);
  47. };
  48.  
  49. class Permutacja
  50. {
  51. public:
  52. vector<Zadanie> listaZadan; //vector przechowujacy zadaną kolejnosc wykonywania zadan
  53. int n; //ilosc wczytanych zadan
  54. int Cmax; //moment zakonczenia q ostatniego zadania
  55. int LB; //wartosc Cmax zwrocona przez algorytm Schrage z przerywaniami
  56. int a,b; //indeksy początku i konca sciezki krytycznej
  57. int c; //indeks zadania interferencyjnego
  58. int sLB; //szybki LB. wg tego permutacje są kopcowane;
  59.  
  60.  
  61. int Schrage(); //algorytm Schrege'a: modyfikuje kolejnosc listyZadan
  62.  
  63. int SciezkaKrytyczna(); //metoda odnajduje w liscieZadan sciezke krytyczna.
  64. //indeksy poczatku i konca przypisuje do pol a i b;
  65. int ZadanieInterferencyjne(); //metoda odnajduje zadanie interferencyjne w sciezce krytycznej
  66. // wymaga poprawnie oznaczonej sciezki przez pola a i b.
  67. // modyfikuje pole c;
  68. int h(int aa, int bb); // metoda zwraca wartosc rmin+sumap+qmin dla zadanego przedziału;
  69.  
  70. int rMin(int aa, int bb); //metoda wyszukuje najmniejszy r z zadanego przedziału
  71.  
  72. int qMin(int aa, int bb); //metoda wyszukuje najmniejsze q z zadanego przedziału;
  73.  
  74. int sumaP(int aa, int bb); //metoda zwraca sume p z zadanego przedziału
  75.  
  76. int rMinBloku(); //Trzy metody zwracają odpowiednie parametry BlokuK - zadan
  77. //od pierwszego za zadaniem interferencyjnym do ostatniego na
  78. int qMinBloku(); //sciezce krytycznej.
  79.  
  80. int sumaPBloku();
  81.  
  82. int SchragePtm(); //metoda zwraca wartosc Cmax algorytmu Schrage z przerywaniami. Modyfikuje pole LB
  83.  
  84. int szybkiLB(); //metoda generuje szybki LB;
  85.  
  86. void testyEliminacyjne(int UB);
  87.  
  88. static bool cmpsLB (const Permutacja & p1, const Permutacja & p2) {
  89. return p1.sLB < p2.sLB;
  90. }
  91.  
  92. friend ostream & operator << (ostream & strumienWyjsciowy, Permutacja & doWypisania);
  93.  
  94.  
  95. Permutacja (char * nazwa_pliku);
  96. Permutacja(void);
  97. ~Permutacja(void);
  98. };
  99.  
  100. int Carlier(char * pliki, char * pliko);
  101.  
  102.  
  103.  
  104.  
  105.  
  106.  
  107. Permutacja::Permutacja(char * nazwa_pliku)
  108. {
  109. int rozmiar; //zmienna pozorowana. trzeba gdzies wczytac "3"
  110. ifstream plikin(nazwa_pliku);
  111. plikin >> n;
  112. plikin >> rozmiar;
  113. Zadanie * wczytywane;
  114. int rr, pp, qq;
  115. for (int i=0; i<n; i++) {
  116. plikin >> rr >> pp >> qq;
  117. wczytywane = new Zadanie(rr,pp,qq,i+1);
  118. listaZadan.push_back(*(wczytywane));
  119. delete wczytywane;
  120. }
  121. plikin.close();
  122.  
  123. }
  124.  
  125.  
  126. int Permutacja::Schrage()
  127. {
  128. int aktualnyCzas = 0;
  129. int _Cmax = 0;
  130.  
  131. Kopiec<Zadanie> kopiecZadan(&Zadanie::compR); //kopiec z wszystkimi zadaniami posortowanymi wg. R
  132. for (int i=0; i<n; i++)
  133. kopiecZadan.push(listaZadan[i]);
  134.  
  135. Kopiec<Zadanie> dostepneZadania(&Zadanie::compQ); //kopiec dostepnych w danej chwili czasowej zadan; posortowana od największego Q
  136. vector<Zadanie> listaSchrage; //lista uszeregowana wg. algorytmu Schrage'a. pod koniec metody podpinana pod listeZadan
  137.  
  138. while ((!kopiecZadan.empty()) || (!dostepneZadania.empty())) {
  139. while ((!kopiecZadan.empty()) && (kopiecZadan.top().r<=aktualnyCzas)) {
  140. dostepneZadania.push(kopiecZadan.top());
  141. kopiecZadan.pop();
  142. }
  143.  
  144. if (dostepneZadania.empty()) {
  145. aktualnyCzas=kopiecZadan.top().r;
  146. }
  147. else {
  148. listaSchrage.push_back(dostepneZadania.top()); //dodajesz zadanie do listy
  149. dostepneZadania.pop(); //usuwa zadanie z puli dostepnych
  150. listaSchrage.back().t_on=aktualnyCzas; //ustawia realny czas rozpoczecia realizacji zadania na maszynie
  151. aktualnyCzas+=listaSchrage.back().p; //aktualizuje czas
  152.  
  153. if (aktualnyCzas + listaSchrage.back().q > _Cmax)
  154. _Cmax=aktualnyCzas + listaSchrage.back().q;
  155. }
  156. }
  157.  
  158. Cmax=_Cmax;
  159. listaZadan.clear();
  160. listaZadan=listaSchrage;
  161. listaSchrage.clear();
  162. return Cmax;
  163. }
  164.  
  165. int Permutacja::SciezkaKrytyczna()
  166. {
  167. int aktualnyMax=0;
  168. for (int i=0; i < n; i++) { //przejrzyj listeZadan. jezeli moment rozpoczecia realizacji+r+q = Cmax,
  169. if (listaZadan[i].t_on+listaZadan[i].p+listaZadan[i].q > aktualnyMax) { //to mamy zadanie, ktore konczy caly proces
  170. b=i;
  171. aktualnyMax=listaZadan[i].t_on+listaZadan[i].p+listaZadan[i].q;
  172. }
  173. }
  174. a=b;
  175. while ((a>=1) && (listaZadan[a-1].t_on+listaZadan[a-1].p >= listaZadan[a].r) ){
  176. a--;
  177. }
  178. return 0;
  179. }
  180.  
  181. int Permutacja::ZadanieInterferencyjne()
  182. {
  183. bool znalezionoC = false;
  184.  
  185. for(int i=b-1; i>=a; i--)
  186. if ((!znalezionoC) && (listaZadan[i].q < listaZadan[b].q)) {
  187. znalezionoC=true;
  188. c=i;
  189. }
  190.  
  191. if (znalezionoC==true)
  192. return 1;
  193. else
  194. return 0;
  195. }
  196.  
  197. int Permutacja::rMinBloku() {
  198. return rMin(c+1,b);
  199. }
  200.  
  201. int Permutacja::qMinBloku() {
  202. return qMin(c+1,b);
  203. }
  204.  
  205. int Permutacja::sumaPBloku() {
  206. return sumaP(c+1,b);
  207. }
  208.  
  209. int Permutacja::SchragePtm()
  210. {
  211. int aktualnyCzas = 0;
  212. int _Cmax = 0;
  213.  
  214. vector<Zadanie>listaNieprzydzielonych; //ze wzgledu na konieczność swobodnego dostepu do wszystkich zadan nie mozna tego realizowac na kopcu.
  215. listaNieprzydzielonych = listaZadan; //tworzymy kopie listy zadan
  216. sort(listaNieprzydzielonych.begin(), listaNieprzydzielonych.end(), Zadanie::compR);
  217.  
  218. Kopiec<Zadanie> listaDostepnych(&Zadanie::compQ); //kopiec dostepnych w danej chwili czasowej zadan. Posortowany od najwiekszego Q
  219.  
  220. vector<Zadanie> listaSchrage; //lista uszeregowana wg. algorytmu Schrage'a. pod koniec metody podpinana pod listeZadan
  221.  
  222. Kopiec<Zadanie> listaPrzerwan(&Zadanie::compQ); //lista tych zadan, na rzecz ktorych moze wystapic przerwanie.
  223. //Posortowana od najmniejszego R
  224.  
  225. while ((!listaNieprzydzielonych.empty()) || (!listaDostepnych.empty())) {
  226. while ((!listaNieprzydzielonych.empty()) && (listaNieprzydzielonych.back().r<=aktualnyCzas)) {
  227. listaDostepnych.push(listaNieprzydzielonych.back()); //tworzymy listę zadan, ktorych r juz uplynelo
  228. listaNieprzydzielonych.pop_back();
  229. }
  230.  
  231. if (listaDostepnych.empty()) {
  232. aktualnyCzas=listaNieprzydzielonych.back().r;
  233. }
  234. else {
  235. while (!listaPrzerwan.empty())
  236. listaPrzerwan.pop(); //czyszczenie listy przerwan
  237.  
  238. for (int i=0; i< (int)listaNieprzydzielonych.size();i++) //tworzenie nowej listy przerwan
  239. if ((listaDostepnych.top().p + aktualnyCzas > listaNieprzydzielonych[i].r)&&(listaDostepnych.top().q < listaNieprzydzielonych[i].q))
  240. listaPrzerwan.push(listaNieprzydzielonych[i]); //na liste przerwan kladziemy te zadania, ktorych q jest wieksze od aktualnie dodawanego algorytmem Schrage'a
  241. //a r miesci sie w przedziale (aktualnyCzas, aktualnyCzas+p dodawanego). Na rzecz tych zadan powinno wystąpić przerwanie.
  242. //elementy na liscie przerwan sa kopiami!
  243.  
  244. if (listaPrzerwan.empty()) { //nie ma przerwan - normalna procedura Schrage'a
  245. listaSchrage.push_back(listaDostepnych.top()); //dodajesz zadanie do listy
  246. listaDostepnych.pop(); //usuwa zadanie z puli dostepnych
  247. listaSchrage.back().t_on=aktualnyCzas; //ustawia realny czas rozpoczecia realizacji zadania na maszynie
  248. aktualnyCzas+=listaSchrage.back().p; //aktualizuje czas
  249.  
  250. if (aktualnyCzas + listaSchrage.back().q > _Cmax)
  251. _Cmax=aktualnyCzas + listaSchrage.back().q;
  252. }
  253. else { //przerwanie
  254. Zadanie part1 = listaDostepnych.top();
  255. listaDostepnych.pop();
  256. Zadanie part2=part1;
  257.  
  258. part1.p=listaPrzerwan.top().r-aktualnyCzas; //część zadania, która zrealizuje się do momentu przerwania.
  259. part2.p-=part1.p; //pozostała część zadania: od part2.p (==part1.p oryginalnego) odejmujesz część, która będzie zrealizowana
  260. listaDostepnych.push(part2); //reszta realizowanego zadania trafia spowrotem do listy dostepnych zadan
  261.  
  262. listaSchrage.push_back(part1);
  263. listaSchrage.back().t_on=aktualnyCzas;
  264. aktualnyCzas+=listaSchrage.back().p;
  265.  
  266. if (aktualnyCzas + listaSchrage.back().q > _Cmax)
  267. _Cmax=aktualnyCzas + listaSchrage.back().q;
  268.  
  269. }
  270. }
  271. }
  272. return _Cmax;
  273. }
  274.  
  275. ostream & operator << (ostream & strumienWyjsciowy, Permutacja & doWypisania)
  276. {
  277. for (int i=0; i < (int)doWypisania.listaZadan.size(); i++)
  278. strumienWyjsciowy<<doWypisania.listaZadan[i];
  279.  
  280. return strumienWyjsciowy;
  281. }
  282.  
  283. Permutacja::Permutacja(void)
  284. {
  285. }
  286.  
  287. Permutacja::~Permutacja(void)
  288. {
  289. }
  290.  
  291. int Permutacja::szybkiLB()
  292. {
  293. sLB=max(h(c+1,b), h(c,b));
  294. return sLB;
  295. }
  296.  
  297. int Permutacja::rMin(int aa, int bb)
  298. {
  299. int rmin=listaZadan.at(a).r;
  300.  
  301. for (int i=a; i<=b; i++) {
  302. if (listaZadan.at(i).r<rmin)
  303. rmin=listaZadan.at(i).r;
  304. }
  305.  
  306. return rmin;
  307. }
  308.  
  309. int Permutacja::qMin(int aa, int bb)
  310. {
  311. int qmin=listaZadan.at(a).q;
  312.  
  313. for (int i=a; i<=b; i++) {
  314. if (listaZadan.at(i).q<qmin)
  315. qmin=listaZadan.at(i).q;
  316. }
  317. return qmin;
  318. }
  319.  
  320. int Permutacja::sumaP(int aa, int bb)
  321. {
  322. int sumaP=0;
  323.  
  324. for (int i=a; i<=b; i++) {
  325. sumaP+=listaZadan.at(i).p;
  326. }
  327.  
  328. return sumaP;
  329. }
  330.  
  331.  
  332. int Permutacja::h(int aa, int bb)
  333. {
  334. if ((aa<0) || (aa>bb) || (bb>(int)listaZadan.size())) {
  335. cerr<<"błąd wywołania funkcji h(int, int)\n";
  336. return 0;
  337. }
  338. return (rMin(aa,bb)+sumaP(aa,bb)+qMin(aa,bb));
  339. }
  340.  
  341. void Permutacja::testyEliminacyjne(int UB)
  342. {
  343. int hK=h(c+1,b);
  344. for (int i=0; i< (int) listaZadan.size(); i++) {
  345. if ((i<a)||(i>b)) {
  346. if (listaZadan[i].p > UB - hK) { //i należy do L
  347. if(listaZadan[i].r+listaZadan[i].p+sumaPBloku()+listaZadan[b].q >= UB )
  348. listaZadan[i].r=max(listaZadan[i].r, rMinBloku() + sumaPBloku());
  349. else if (rMinBloku()+listaZadan[i].p + sumaPBloku()+ listaZadan[i].q >=UB)
  350. listaZadan[i].q=max(listaZadan[i].q,qMinBloku()+sumaPBloku());
  351. }
  352. }
  353.  
  354. }
  355. }
  356.  
  357.  
  358. Zadanie::Zadanie(int rr, int pp, int qq, int nnr) {
  359. r=rr;
  360. p=pp;
  361. q=qq;
  362. nr=nnr;
  363. t_on=0;
  364. }
  365.  
  366. ostream & operator << (ostream & strumWyj, const Zadanie & doWypisania)
  367. {
  368. strumWyj<<"Nr: "<<doWypisania.nr<<"\tr: "<<doWypisania.r<<"\tp: "<<doWypisania.p<<"\tq: "<<doWypisania.q<<"\tt_on: "<<doWypisania.t_on<<endl;
  369. return strumWyj;
  370. }
  371.  
  372. Zadanie::Zadanie(void)
  373. {
  374. }
  375.  
  376. Zadanie::~Zadanie(void)
  377. {
  378. }
  379.  
  380. #pragma region Kopiec
  381. template <class T>
  382. Kopiec<T>::Kopiec(bool (*cmp)(const T & ,const T & ))
  383. {
  384. iloscElementow = 0;
  385. funkcjaPorownujaca = cmp;
  386. tablicaElementow=NULL;
  387. }
  388.  
  389. template <class T>
  390. int Kopiec<T>::push(T element)
  391. {
  392.  
  393. if (iloscElementow==0) { //dodajemy na szczyt kopca
  394. tablicaElementow = new T[1];
  395. tablicaElementow[iloscElementow]=element;
  396. iloscElementow++;
  397. return 1;
  398. }
  399. else {
  400. T * temp = tablicaElementow;
  401. tablicaElementow = new T [iloscElementow+1];
  402. copy(temp, temp+iloscElementow, tablicaElementow);
  403. delete [] temp;
  404.  
  405. int aktualnyIndeks=iloscElementow;
  406. int indeksOjca=iloscElementow/2;
  407. T tmp;
  408.  
  409. tablicaElementow[iloscElementow]=element;
  410. while ((indeksOjca>=0) && (funkcjaPorownujaca(tablicaElementow[indeksOjca],tablicaElementow[aktualnyIndeks])))
  411. {
  412. tmp = tablicaElementow[indeksOjca];
  413. tablicaElementow[indeksOjca]=tablicaElementow[aktualnyIndeks];
  414. tablicaElementow[aktualnyIndeks]=tmp;
  415.  
  416. aktualnyIndeks=indeksOjca;
  417. indeksOjca/=2;
  418. }
  419. iloscElementow++;
  420. return iloscElementow;
  421. }
  422. }
  423.  
  424. template <class T>
  425. T Kopiec<T>::pop()
  426. {
  427. T doZwrotu;
  428. if (iloscElementow==0)
  429. {
  430. cerr<<"Brak elementow na kopcu!"<<endl;
  431. return doZwrotu;
  432. }
  433. doZwrotu = tablicaElementow[0];
  434. tablicaElementow[0]=tablicaElementow[iloscElementow-1];
  435. int aktualnyIndeks=0;
  436.  
  437. 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
  438. (((aktualnyIndeks+1)*2<iloscElementow-1)&&(funkcjaPorownujaca (tablicaElementow[aktualnyIndeks],tablicaElementow[(aktualnyIndeks+1)*2]))))
  439. {
  440. if (funkcjaPorownujaca(tablicaElementow[(aktualnyIndeks+1)*2-1], tablicaElementow[(aktualnyIndeks+1)*2])) //jeżeli prawe dziecko jest wieksze
  441. { // to z nim zamieniamy aktualny indeks
  442. T tmp = tablicaElementow[(aktualnyIndeks+1)*2];
  443. tablicaElementow[(aktualnyIndeks+1)*2]=tablicaElementow[aktualnyIndeks];
  444. tablicaElementow[aktualnyIndeks]=tmp;
  445. aktualnyIndeks=(aktualnyIndeks+1)*2;
  446. }
  447. else
  448. {
  449. T tmp = tablicaElementow[(aktualnyIndeks+1)*2-1];
  450. tablicaElementow[(aktualnyIndeks+1)*2-1]=tablicaElementow[aktualnyIndeks];
  451. tablicaElementow[aktualnyIndeks]=tmp;
  452. aktualnyIndeks=(aktualnyIndeks+1)*2-1;
  453. }
  454. }
  455. iloscElementow--;
  456.  
  457. T * temp = tablicaElementow;
  458. tablicaElementow = new T [iloscElementow];
  459. copy(temp, temp+iloscElementow, tablicaElementow);
  460.  
  461. delete [] temp;
  462. return doZwrotu;
  463. }
  464.  
  465. template <class T>
  466. T Kopiec<T>::top()
  467. {
  468. T doZwrotu;
  469. if (iloscElementow==0)
  470. {
  471. cerr<<"Brak elementow na kopcu!\n";
  472. return doZwrotu;
  473. }
  474. doZwrotu = tablicaElementow[0];
  475. return doZwrotu;
  476. }
  477.  
  478. template <class T>
  479. void Kopiec<T>::wypisz()
  480. {
  481. for (int i=0; i<iloscElementow; i++)
  482. {
  483. cout<<"Indeks: "<<i<<" wartosc: "<<tablicaElementow[i]<<endl;
  484. }
  485. }
  486.  
  487. template <class T>
  488. bool Kopiec<T>::empty()
  489. {
  490. if (iloscElementow==0)
  491. return true;
  492. else
  493. return false;
  494. }
  495.  
  496. #pragma endregion Kopiec
  497.  
  498.  
  499. int Carlier(char * pliki, char * pliko) {
  500. int LB, UB;
  501. bool znalezionoOptymalne = false;
  502. Permutacja permut0(pliki);
  503. Permutacja optymalna, aktualna, potomek1, potomek2;
  504. permut0.sLB=1; //i tak jest zdejmowana odrazu
  505.  
  506. Kopiec<Permutacja> kolejkaCarliera(&Permutacja::cmpsLB);
  507. UB=permut0.Schrage();
  508. LB=permut0.SchragePtm();
  509.  
  510. kolejkaCarliera.push(permut0);
  511. optymalna=permut0;
  512. while (!kolejkaCarliera.empty()) { //&&(!znalezionoOptymalne) ?
  513. aktualna=kolejkaCarliera.top();
  514. kolejkaCarliera.pop();
  515.  
  516. if (aktualna.SchragePtm() < UB){ //najlepszy możliwy jest lepszy od znalezionego UB - dzielimy problem
  517. aktualna.Schrage();
  518. if (aktualna.Cmax < UB) { //układamy wg. algorytmu Schrage. Jezeli znaleźliśmy lepsze rozwiazanie - zapisujemy je.
  519. UB=aktualna.Cmax;
  520. optymalna=aktualna;
  521. }
  522. aktualna.SciezkaKrytyczna();
  523. if(aktualna.ZadanieInterferencyjne()) {
  524. aktualna.testyEliminacyjne(UB);
  525.  
  526. potomek1=potomek2=aktualna;
  527. potomek1.listaZadan[potomek1.c].r=potomek1.rMinBloku()+potomek1.sumaPBloku();
  528. potomek2.listaZadan[potomek2.c].q=potomek2.qMinBloku()+potomek2.sumaPBloku();
  529.  
  530. potomek1.szybkiLB();
  531. potomek2.szybkiLB();
  532.  
  533.  
  534. kolejkaCarliera.push(potomek1);
  535. kolejkaCarliera.push(potomek2);
  536.  
  537. }
  538. else {
  539. znalezionoOptymalne=true;
  540. cout<<"znaleziono lokalnie optymalne: "<< aktualna.Cmax<<endl;
  541. }
  542.  
  543. }
  544. }
  545.  
  546. cout<<"Cmax znalezionego: "<<optymalna.Cmax<<endl;
  547. ofstream plikout(pliko);
  548.  
  549. //plikout<<"1 "<<optymalna.n<<endl;
  550. for(int i=0;i<optymalna.n;i++){
  551. plikout<<optymalna.listaZadan[i].nr<<" ";
  552. }
  553. plikout<<endl<<optymalna.Cmax;
  554. plikout.close();
  555.  
  556. return optymalna.Cmax;
  557. }
  558.  
  559. int main () {
  560. char pause;
  561. Carlier("in50.txt", "out50.txt");
  562. Carlier("in100.txt", "out100.txt");
  563. Carlier("in200.txt", "out200.txt");
  564.  
  565.  
  566.  
  567. cin >> pause;
  568. return 0;
  569.  
  570. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement