Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdlib>
- #include <iostream>
- #include <vector>
- #include <ctime>
- #include <algorithm>
- using namespace std;
- int countCaptures(vector<int> queens)
- {
- int counter = 0;
- for(int i=0; i<queens.size()-1; ++i)
- {
- for(int j=i+1; j<queens.size(); ++j)
- {
- if(i-queens[i] == j-queens[j] || i+queens[i] == j+queens[j]) counter++;
- }
- }
- return counter;
- }
- void showVector(vector<int> queens)
- {
- for(int i=0; i<queens.size(); i++) cout << queens[i] << "\t";
- cout << endl;
- }
- void showBoard(vector<int> queens)
- {
- for(int i=0; i<queens.size(); i++)
- {
- for(int j=0; j<queens.size(); j++)
- {
- if(queens[i]==j) cout << "1 ";
- else cout << "0 ";
- }
- cout << endl;
- }
- }
- int main()
- {
- srand(time(nullptr));
- int n, k, g, m;
- cout << "Podaj rozmiar planszy: ";
- cin >> n;
- cout << "Podaj licznosc populacji: ";
- cin >> k;
- g = 1;
- cout << "Podaj liczbe generacji: ";
- cin >> g;
- cout << "Podaj prawdopodobienstwo mutacji: ";
- cin >> m;
- vector<vector <int>> population(k, vector<int>(n));
- vector<vector <int>> newPopulation(k, vector<int>(n));
- vector <int> best(n);
- vector <int> captures(k,0);
- vector <int> ranking(k,0);
- bool isFound = false;
- for(int i=0; i<k; ++i)
- {
- for(int j=0; j<n; ++j)
- {
- population[i][j] = j;
- }
- random_shuffle(begin(population[i]), end(population[i]));
- }
- int capturesMax, rankSum;
- for(int i=0; i<g; i++)
- {
- best = population[0];
- capturesMax = 0;
- rankSum = 0;
- for(int j=0; j<k; j++)
- {
- captures[j] = countCaptures(population[j]);
- if(captures[j]==0)
- {
- best = population[j];
- isFound = true;
- break;
- }
- if(captures[j] > capturesMax) capturesMax = captures[j];
- if(captures[j] < countCaptures(best)) best = population[j];
- }
- if(isFound == true) break;
- for(int j=0; j<k; j++)
- {
- ranking[j] = capturesMax - captures[j] + 1;
- rankSum += ranking[j];
- }
- int roulette;
- for(int j=0; j<k; j++)
- {
- roulette = rand()%rankSum+1;
- int temp = 0;
- for(int l=0; l<k; l++)
- {
- temp += ranking[l];
- if(temp >= roulette) newPopulation[j] = population[l];
- }
- }
- for(int j=0; j<k; j++)
- {
- if(rand()%101 < m*100)
- {
- swap(newPopulation[rand()%n], newPopulation[rand()%n]);
- }
- }
- population = newPopulation;
- }
- cout << endl << endl;
- showVector(best);
- showBoard(best);
- cout << endl << "Liczba bic: " << countCaptures(best);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement