123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182 |
- #include <algorithm>
- #include <chrono>
- #include <climits>
- #include <iostream>
- #include "Reader.h"
- int center;
- Reader r;
- struct Data {
- std::vector<int> order;
- std::vector<int> vehicles;
- mutable int fitness = -1;
- Data(int size) : order(size, 0), vehicles(size, rand() % 4) {
- int counter = -1;
- for(int& i : order) {
- counter++;
- if(counter == center) {
- counter++;
- }
- i = counter;
- }
- }
- int getFitness() const {
- if(fitness != -1) {
- return fitness;
- }
- int last[4] = {center, center, center, center};
- int sum[4] = {0, 0, 0, 0};
- fitness = 0;
- for(size_t i = 0; i < order.size(); i++) {
- int v = vehicles[i];
- sum[v] += r[last[v]][order[i]];
- last[v] = order[i];
- }
- for(int i = 0; i < 4; i++) {
- sum[i] += r[last[i]][center];
- }
- int max = std::max(std::max(sum[0], sum[1]), std::max(sum[2], sum[3]));
- fitness = sum[0] + sum[1] + sum[2] + sum[3] + max * 4;
- return fitness;
- }
- void mutate() {
- if(rand() & 1) {
- vehicles[rand() % vehicles.size()] = rand() % 4;
- } else {
- int a = rand() % vehicles.size();
- int b = rand() % vehicles.size();
- if(b <= a) {
- std::swap(a, b);
- }
- int oldB = order[b];
- for(int i = b; i > a; i--) {
- order[i] = order[i - 1];
- }
- order[a] = oldB;
- oldB = vehicles[b];
- for(int i = b; i > a; i--) {
- vehicles[i] = vehicles[i - 1];
- }
- vehicles[a] = oldB;
- }
- fitness = -1;
- }
- void print() const {
- for(int i : order) {
- std::cout << i << " ";
- }
- std::cout << "| ";
- for(int i : vehicles) {
- std::cout << i << " ";
- }
- std::cout << "| " << getFitness() << "\n";
- }
- void prettyPrint() const {
- for(int i = 0; i < 4; i++) {
- std::cout << i << ": " << r.getName(center) << " -> ";
- for(size_t k = 0; k < order.size(); k++) {
- if(vehicles[k] == i) {
- std::cout << r.getName(order[k]) << " -> ";
- }
- }
- std::cout << r.getName(center) << "\n";
- }
- }
- bool operator<(const Data& other) const {
- return getFitness() < other.getFitness();
- }
- };
- std::vector<Data> population;
- static void init() {
- for(int i = 0; i < 1000; i++) {
- population.push_back(Data(r.getSize() - 1));
- }
- for(Data& data : population) {
- for(int i = 0; i < 40; i++) {
- data.mutate();
- }
- }
- }
- static void sort() {
- std::sort(population.begin(), population.end());
- }
- static void findCenter() {
- int min = INT_MAX;
- int index = 0;
- for(int i = 0; i < r.getSize(); i++) {
- int sum = 0;
- for(int k = 0; k < r.getSize(); k++) {
- sum += r[i][k];
- }
- if(sum < min) {
- index = i;
- min = sum;
- }
- }
- center = index;
- }
- long getNanos() {
- return std::chrono::high_resolution_clock::now().time_since_epoch().count();
- }
- int main(int argAmount, char** args) {
- long start = -getNanos();
- if(r.read("romaniaroads.pl")) {
- return 0;
- }
- if(argAmount >= 2) {
- int c = atoi(args[1]);
- if(c < 0 || c >= r.getSize()) {
- std::cout << c << " is not a valid center\n";
- return 0;
- }
- center = c;
- } else {
- findCenter();
- }
- start += getNanos();
- long loop = -getNanos();
- init();
- sort();
- for(int gens = 0; gens < 500; gens++) {
- size_t half = population.size() / 2;
- for(size_t i = half; i < population.size(); i++) {
- int parent = rand() % half;
- population[i] = population[parent];
- population[i].mutate();
- }
- sort();
- }
- for(size_t i = 10; i > 0; i--) {
- population[i - 1].print();
- }
- population[0].prettyPrint();
- std::cout << "center is " << r.getName(center) << "\n";
- loop += getNanos();
- std::cout << "Start: " << start / 1'000'000 << "ms\n";
- std::cout << "Loop: " << loop / 1'000'000 << "ms\n";
- return 0;
- }
|