click here to see this page in dynamic views.
kliknij tutaj aby zobaczyć tę stronę w widoku dynamicznym.
algorithms, AI, image processing, robotics, automatition, hardcore lifestyle and traveling.
Saturday, December 22, 2012
Friday, December 21, 2012
Heap C++ implementation / Kopiec C++
Implementacja kopca w C++ oraz metod dla tej stuktury, dostępny jest również słownik pozwalający na orientownie się w hierarchii pierwotnej kopca gdy zaburzona zostanie jego struktura np. poprzez dodanie nowych elementów etc.
Heap C++ implementation with dictionary.
English ver in comments...
Heap C++ implementation with dictionary.
English ver in comments...
/*****************************************************************************/ /* Heap C++ implementation, methods n algorithms + dictionary showing index */ /* of an element. Polish n English menu's versions available */ /* compile: g++ -Wall -pedantic heap.cpp */ /* how to use: ./a.out -> n do whatever u want */ #include <iostream> //#define PL #define ENG using namespace std; /*****************************************************************************/ /*! * \brief Object * \param value - wartosc liczbowa * \param key - klucz */ class Object { public: int value; int key; Object() { //srand((int)time(0)); //value=rand()%(10); value=0; } ~Object(){} }; /**/ /*****************************************************************************/ /*****************************************************************************/ /*! * \brief Heap * \param Tab - tablica wartosci kopca * \param Dictionary - slownik * \param n - takie n */ class Heap { public: Object *Tab; int n; int *Dictionary; /*! * \brief Tworzy tablice obiektow rozmiaru size * oraz slownik pozwalajacy na lokaalizacje * elementow kopca gdy jego porzadek zostanie * zaburzony * */ Heap(int size) { n=size; Tab=new Object[size+1]; Dictionary=new int[size+1]; for(int i=1;i<=size+1;i++) { Tab[i].key=i; } for(int i=1;i<size+1;i++) { Dictionary[i]=Tab[i].key; } } ~Heap(){cout<<"boom!!! free machines's brain"<<endl; delete[] Tab; delete Dictionary;} /*! * \brief Ustawia wartosc tablicy o danym kluczu */ void ChangeKElement(int k,int v) { Tab[Dictionary[k]].value=v; } /*! * \brief Wypisuje wartosci kopca */ void PrintHeap() { cout<<"Heap:"<<endl<<endl;; for(int i=1;i<n+1;i++) { cout<<Tab[i].value<<endl; } } /*! * \brief Wypisuje wartosci kluczy */ void PrintKeys() { cout<<"Keys:"<<endl<<endl;; for(int i=1;i<n+1;i++) { cout<<Tab[i].key<<endl; } } /*! * \brief Wypisuje slownik */ void PrintDictionary() { cout<<"Dictionary:"<<endl<<endl;; for(int i=1;i<n+1;i++) { cout<<Dictionary[i]<<endl; } } /*! * \brief Naprawia kopiec iteracyjnie */ void FixHeapIt() { int p,d,tmp_w,tmp_k; for(int i=2;i<=n;i++) { d=i; p=d/2; tmp_w=Tab[i].value; tmp_k=Tab[i].key; while((p>0)&&(Tab[p].value>tmp_w)) { Tab[d].value=Tab[p].value; Tab[d].key=Tab[p].key; Dictionary[Tab[p].key]=d; d=p; p=d/2; Tab[d].value=tmp_w; Tab[d].key=tmp_k; Dictionary[tmp_k]=d; } } } /*! * \brief tzw swap - zamiana elementow */ void siup(int *ptr1, int *ptr2) { int tmp=*ptr1; *ptr1=*ptr2; *ptr2=tmp; } /*! * \brief Naprawia kopiec rekurencyjnie */ void FixHeapRe(int i) { int star_wars=i; if(((2*i)<n+1) && (Tab[2*i].value<Tab[star_wars].value)) star_wars=2*i; if(((2*i+1)<n+1) && (Tab[2*i+1].value<Tab[star_wars].value)) star_wars=2*i+1; if(star_wars!=i) { siup(&Tab[star_wars].value,&Tab[i].value); siup(&Tab[star_wars].key,&Tab[i].key); siup(&Dictionary[Tab[star_wars].key],&Dictionary[Tab[i].key]); FixHeapRe(star_wars); } } /*! * \brief Buduje kopiec */ void BuildHeap() { for (int i=n+1;i>0;i--) { FixHeapRe(i); } } /*! * \brief Wypisuje proste menu */ void PrintMenu() { char opt='?'; #ifdef ENG while(opt!='q') { cout<<" "<<endl; cout<<"p - print heap"<<endl; cout<<"& - print keys"<<endl; cout<<"# - print dictionary"<<endl; cout<<"z - change value of key's element"<<endl; cout<<"r - fix heap"<<endl; cout<<"q - quit"<<endl; cin>>opt; switch(opt) { case 'p': cout<<"--------"<<endl; PrintHeap(); opt='?'; break; case '&': cout<<"--------"<<endl; PrintKeys(); opt='?'; break; case '#': cout<<"--------"<<endl; PrintDictionary(); opt='?'; break; case 'z': cout<<"object's key: "<<endl; int k1,w1; cin>>k1; cout<<"object's value: "<<endl; cin>>w1; ChangeKElement(k1,w1);opt='?'; break; case 'r': cout<<"fixed:"<<endl; BuildHeap(); PrintHeap(); opt='?'; break; case 'q': cout<<"maskotky's toy says hasta la vista!"<<endl;break; } #endif #ifdef PL while(opt!='q') { cout<<" "<<endl; cout<<"p - wypisz kopiec"<<endl; cout<<"& - wypisz klucze"<<endl; cout<<"# - wypisz slownik"<<endl; cout<<"z - zamien wartosc elementu o danym kluczu"<<endl; cout<<"r - napraw kopiec"<<endl; cout<<"q - zakoncz"<<endl; cin>>opt; switch(opt) { case 'p': cout<<"--------"<<endl; PrintHeap(); opt='?'; break; case '&': cout<<"--------"<<endl; PrintKeys(); opt='?'; break; case '#': cout<<"--------"<<endl; PrintDictionary(); opt='?'; break; case 'z': cout<<"klucz: "<<endl; int k1,w1; cin>>k1; cout<<"wartosc: "<<endl; cin>>w1; ChangeKElement(k1,w1);opt='?'; break; case 'r': cout<<"naprawiony:"<<endl; BuildHeap(); PrintHeap(); opt='?'; break; case 'q': cout<<"maskotky's toy says hasta la vista"<<endl; break; } #endif } } }; /**/ /*****************************************************************************/ int main() { cout<<"\nhello, this is heap toy!"<<endl; Heap My_Heap(8); //kopiec ma 8 elementow // ustawienie elementow kopca My_Heap.ChangeKElement(1,4); My_Heap.ChangeKElement(2,3);My_Heap.ChangeKElement(3,7); My_Heap.ChangeKElement(4,9);My_Heap.ChangeKElement(5,8); My_Heap.ChangeKElement(6,5);My_Heap.ChangeKElement(7,2); My_Heap.ChangeKElement(8,1); // //My_Heap.BuildHeap(); //My_Heap.PrintHeap(); //My_Heap.PrintKeys(); //My_Heap.PrintDictionary(); My_Heap.PrintMenu(); return 0; }
Monday, December 17, 2012
NEH algorithm C++ implementation / implementacja algorytmu NEH
Implementacja algorytmu NEH z akceleracją w C++.
NEH algorithm with acceleration, C++ implementation.
The program has 3 functions: data reading, data writting and NEH algorithm solving problem function based on read data file. The program displays time. Compilation: Microsoft Visual C++ 2010 Express.
NEH algorithm with acceleration, C++ implementation.
The program has 3 functions: data reading, data writting and NEH algorithm solving problem function based on read data file. The program displays time. Compilation: Microsoft Visual C++ 2010 Express.
////////////////////////////////////////////////////////////////////////// // program posiada 3 funkcje: // wczytywania danych, zapisywania danych, rozwiazywania problemu // przeplywowego algorytmem NEH z akceleracja // posiada rowniez funkcje pomocnicze oraz odpowiednie struktury danych // program wyswietla czas dzialania algorytmu, zmienna cmax nie wyswietlana // dla kolejnych instancji przechowuje cmax // kompilacja: Microsoft Visual Studio 2010 #include<iostream> #include<fstream> #include<vector> #include<list> #include<stdio.h> #include<algorithm> #include<cstdlib> #include<Windows.h> #define INSTANCE_AMOUT 120 #pragma warning(disable: 4996) using namespace std; struct JobsData { int no; int time; }; struct AllData { int **Tab_Job; int jobs; //liczba zadan int machines; //liczba maszyn list<JobsData> Jobs_List; //lista zadan posiada nr zadania i calkowity czas potrzebny do spedzenia na maszynach vector<int>solution; // tablica uszeregowan czasow zadan }; bool compare(const JobsData& _jd1, const JobsData& _jd2) { return _jd1.time > _jd2.time; } int clear_matrix(int **Tab,int x, int y); void print_matrix(int **Tab, int x, int y); ///////////////////////////////////////////////// // zamien vector'y void swap_V(int &x,int &y); // ///////////////////////////////////////////////// ///////////////////////////////////////////////// // funkcja wczytuje dane z odpowiedniego pliku // bench_fs.txt // PRE: AllData - wskaznik na strukture danych // z elementami niezbednymido wykonania // algorytmu, // pFile - wskaznik na otwarty plil // POST: brak // void GetData(AllData *D, FILE *pFile); // ///////////////////////////////////////////////// ///////////////////////////////////////////////// // funkcja wczytuje dane z odpowiedniego pliku // bench_fs.txt // PRE: AllData - wskaznik na strukture danych // z tablica wynikowa solution // pFileOut - wskaznik na plik do zapisu // POST: brak // void ToFile(AllData *W, FILE *pFileOut); // ///////////////////////////////////////////////// //////////////////////////////////////////////// // funkcja implementujaca algorytm NEH // z akceleracja // PRE: AllData - wskaznik na strukture danych // z elementami niezbednymi do wykonania // algorytmu NEH // POST: brak void DoNEH_acc(AllData *N); // //////////////////////////////////////////////// ////////////////////////////////////////////////////////////////////////// // main int main() { __int64 start, stop, freq; AllData *ins = new AllData[INSTANCE_AMOUT]; FILE *pFile; pFile=fopen("bench_fs.txt","r"); for(int instance = 0; instance < INSTANCE_AMOUT; instance++) // for dla kolejnych instancji { GetData(ins,pFile); //wczytaj dane z pliku ins++; } fclose(pFile); ins=ins-INSTANCE_AMOUT; QueryPerformanceCounter((LARGE_INTEGER*)&start); for(int instance = 0; instance < INSTANCE_AMOUT; instance++) { DoNEH_acc(ins); //uszereguj je NEH'em ins++; } QueryPerformanceCounter((LARGE_INTEGER*)&stop); QueryPerformanceFrequency((LARGE_INTEGER*)&freq); cout<<" "<<endl; cout<<"time: " << ((double)(stop-start))/freq << "s" << endl; ins=ins-INSTANCE_AMOUT; FILE *pFileOut; pFileOut=fopen("data_out.txt","w"); for(int instance = 0; instance < INSTANCE_AMOUT; instance++) { ToFile(ins,pFileOut); //zapisz dane do pliku ins++; } fclose(pFileOut); getchar(); return 0; } // koniec main ////////////////////////////////////////////////////////////////////////// ///////////////////////////////////////////////// // GetData void GetData(AllData *D, FILE *pFile) { int E_time;//suma czasow jednego zadania na wszystkich maszynach int time; //czas zadania na maszynie int nvm;//pomijana char iname[6];//nazwa instancji w pliku JobsData Job; //dane zadania if(pFile == NULL){fprintf(stderr,"Blad: Nie podano uchwytu do pliku\n");exit(-1);} fscanf(pFile,"%s",iname); fscanf(pFile,"%d",&D->jobs); fscanf(pFile,"%d",&D->machines); D->Tab_Job = new int * [D->machines]; // i-zadan na j-maszynach for (int j = 0; j < D->machines; j++){ D->Tab_Job[j] = new int[D->jobs]; } for(int i = 0; i < D->jobs; i++) { E_time = 0; for(int j = 0; j < D->machines; j++) { fscanf(pFile,"%d",&nvm); fscanf(pFile,"%d",&time); E_time = E_time + time; D->Tab_Job[j][i] = time; } Job.no = i+1; Job.time = E_time; D->Jobs_List.push_back(Job); } } // koniec funkcji GetData ///////////////////////////////////////////////// ///////////////////////////////////////////////// // ToFile void ToFile(AllData *W, FILE *pFileOut) { for(int i = 0; i < W->jobs; i++) { fprintf(pFileOut,"%d ", W->solution[i]); } fprintf(pFileOut,"\n"); } // koniec ToFile ///////////////////////////////////////////////// ///////////////////////////////////////////////////////////////////// // NEH z akceleracja void DoNEH_acc(AllData *N) { int max, min; int _dict = 0; int new_job; int cmax; int tmp_job; vector<int>max_vect; N->solution.clear(); N->Jobs_List.sort(compare); //mam uszeregowane zadania ze zgledu na czas N->solution.push_back(N->Jobs_List.front().no);// dodaje do tablicy 1 element posortowanej listy zadan N->Jobs_List.pop_front(); // sciagam ten element z listy, na liscie o jedno zadanie mniej int **E = new int*[N->machines+1]; //tworze macierz E for (int i = 0; i < N->machines+1; i++) { E[i] = new int[N->jobs]; } int **Q= new int*[N->machines+1]; //tworze macierz Q for (int i = 0; i < N->machines+1; i++) { Q[i] = new int[N->jobs]; } int **F= new int*[N->machines+1]; //tworze macierz F for (int i = 0; i < N->machines+1; i++) { F[i] = new int[N->jobs]; } int **F_Q= new int*[N->machines+1]; //tworze macierz F for (int i = 0; i < N->machines+1; i++) { F_Q[i] = new int[N->jobs]; } clear_matrix(E,N->machines+1,N->jobs); // clear_matrix(Q,N->machines+1,N->jobs); // wypelniam je zerami clear_matrix(F,N->machines+1,N->jobs); // clear_matrix(F_Q,N->machines+1,N->jobs); /////////////////////////////////////////////////////////////////////// // poczatek petli dla kazdego zadania while(N->Jobs_List.size() != 0) { max_vect.clear(); for(int i=0; i < (int)N->solution.size(); i++) ////////////////////////////////////////////////////////////////////////////////// matrix E { for(int j=0; j < N->machines; j++)// w pierwszej kolumnie { E[j+1][i+1] = max(E[j][i+1],E[j+1][i]) + N->Tab_Job[j][N->solution[i]-1]; } } for(int i = (int)N->solution.size()-1; i >= 0; i--) ////////////////////////////////////////////////////////////////////////////////// matrix Q { for(int j = N->machines-1; j >= 0; j--)// w pierwszej kolumnie { Q[j][i] = max(Q[j+1][i],Q[j][i+1]) + N->Tab_Job[j][N->solution[i]-1]; } } new_job = N->Jobs_List.front().no; // sciagam nowe zadanie N->Jobs_List.pop_front(); // for(int i=0; i < (int)N->solution.size()+1; i++) ////////////////////////////////////////////////////////////////////////////////// matrix F { for(int j=0; j < N->machines; j++)// w pierwszej kolumnie { F[j+1][i] = max(E[j+1][i],F[j][i]) + N->Tab_Job[j][new_job-1]; } } for(int i=0; i < (int)N->solution.size()+1; i++) ////////////////////////////////////////////////////////////////////////////////// matrix F_Q { for(int j=0; j < N->machines; j++)// w pierwszej kolumnie { F_Q[j][i] = Q[j][i]+F[j+1][i]; } } for(int i=0; i < (int)N->solution.size()+1; i++) // znajduje maxa poszczegolnych kolumn w macierzy F+Q { max = 0; for(int j=0; j < N->machines; j++) { if(F_Q[j][i] > max) {max = F_Q[j][i];} } max_vect.push_back(max); } min=999999; for(int i=0; i < (int)max_vect.size(); i++) { if(max_vect[i]<min){ min = max_vect[i]; _dict = i;} // _slownik_it zeby znac indeks na ktory mam wstawic to zadanie } cmax = min; N->solution.push_back(0); for(int i = _dict; i < (int)N->solution.size(); i++) { swap_V(N->solution[i],tmp_job); } N->solution[_dict] = new_job; } //koniec while } // koniec funkcji // ///////////////////////////////////////////////////////////////////// ///////////////////////////////////////////////////////////////////// // funkcje dodatkowe void swap_V(int &x,int &y) //swap4vector { int temp; temp=x; x=y; y=temp; } int clear_matrix(int **Tab,int x, int y) { for(int i = 0; i < x; i++) for(int j = 0; j < y; j++) Tab[i][j]=0; return 0; } void print_matrix(int **Tab, int x, int y) { for(int i = 0; i < x; i++){ for(int j = 0; j < y; j++) {cout<<Tab[i][j];} cout<<" "<<endl;} } // /////////////////////////////////////////////////////////////////////
co?/what?
Posty będą zamieszczane w języku polskim i angielskim.
Będą one dotyczyły zagadnień związanych z poniższymi tematami:
-algorytmy,
-sztuczna inteligencja,
-przetwarzanie obrazów,
-robotyka,
-automatyka,
-hardcore lifestyle i inne.
========================================================================
Posts will be published in Polish and English (maybe;)) and will follow underground, mainstream, ready solutions in:
-algorithms,
-artificial intelligence,
-image processing,
-robotics,
-automatition n control engeneering,
-hardcore lifestyle and traveling.
-algorytmy,
-sztuczna inteligencja,
-przetwarzanie obrazów,
-robotyka,
-automatyka,
-hardcore lifestyle i inne.
========================================================================
Posts will be published in Polish and English (maybe;)) and will follow underground, mainstream, ready solutions in:
-algorithms,
-artificial intelligence,
-image processing,
-robotics,
-automatition n control engeneering,
-hardcore lifestyle and traveling.
Subscribe to:
Posts (Atom)