git.sesse.net Git - tsp/blob - tsp.cpp

   1 #include <assert.h>
   2 #include <stdio.h>
   3 #include <string.h>
   4
   5 #include <vector>
   6 #include <string>
   7 #include <map>
   8 #include <set>
   9 #include <algorithm>
  10
  11 using namespace std;
  12
  13 #define INFINITY 10000
  14
  15 vector<string> places;
  16 set<string> places_set;
  17 map<pair<string, string>, int> sparse_dist;
  18
  19 int* dist;
  20
  21 void check_name_inserted(char* name)
  22 {
  23         if (places_set.count(name) == 0) {
  24                 places_set.insert(name);
  25                 places.push_back(name);
  26         }
  27 }
  28
  29 void make_matrix()
  30 {
  31         int num_places = places.size();
  32         dist = new int[num_places * num_places];
  33
  34         for (int i = 0; i < num_places; ++i) {
  35                 dist[i * num_places + i] = 0;
  36         }
  37
  38         for (int i = 0; i < num_places; ++i) {
  39                 for (int j = i + 1; j < num_places; ++j) {
  40                         int d = INFINITY;
  41
  42                         pair<string, string> comb = make_pair(places[i], places[j]);
  43                         if (sparse_dist.count(comb) != 0) {
  44                                 d = sparse_dist[comb];
  45                         }
  46                         comb = make_pair(places[j], places[i]);
  47                         if (sparse_dist.count(comb) != 0) {
  48                                 d = sparse_dist[comb];
  49                         }
  50                         dist[i * num_places + j] = d;
  51                         dist[j * num_places + i] = d;
  52                 }
  53         }
  54 }
  55
  56 void print_matrix()
  57 {
  58         int num_places = places.size();
  59         for (int i = 0; i < num_places; ++i) {
  60                 printf("%d: %s\n", i, places[i].c_str());
  61         }
  62         for (int i = 0; i < num_places; ++i) {
  63                 for (int j = 0; j < num_places; ++j) {
  64                         printf("%5d ", dist[i * num_places + j]);
  65                 }
  66                 printf("\n");
  67         }
  68 }
  69
  70 void floyd_warshall()
  71 {
  72         int num_places = places.size();
  73
  74         for (int k = 0; k < num_places; ++k) {
  75                 for (int i = 0; i < num_places; ++i) {
  76                         for (int j = 0; j < num_places; ++j) {
  77                                 dist[i * num_places + j] =
  78                                         min(dist[i * num_places + j],
  79                                             dist[i * num_places + k] + dist[k * num_places + j]);
  80                         }
  81                 }
  82         }
  83 }
  84
  85 int *cache;
  86 int cache_size;
  87 int best_cost;
  88 int finish_mask;
  89
  90 void init_tsp()
  91 {
  92         int num_places = places.size();
  93         cache_size = (1 << num_places);
  94         cache = new int[cache_size * num_places];
  95
  96         for (int i = 0; i < cache_size * num_places; ++i) {
  97                 cache[i] = -1;
  98         }
  99
 100         best_cost = INFINITY;
 101         finish_mask = (1 << num_places) - 1;
 102 }
 103
 104 int tsp(int node_num, int visited_mask, int cost_so_far)
 105 {
 106         int num_places = places.size();
 107         if (cache[node_num * cache_size + visited_mask] != -1) {
 108                 return cache[node_num * cache_size + visited_mask];
 109         }
 110         if (cost_so_far > best_cost) {
 111                 return INFINITY;
 112         }
 113
 114         if (visited_mask == finish_mask) {
 115                 return 0;
 116 /*
 117                 cost_so_far += dist[node_num * num_places + 0];
 118                 cache[node_num * cache_size + visited_mask] = dist[node_num * num_places + 0];
 119                 if (cost_so_far < best_cost) {
 120                         best_cost = cost_so_far;
 121                 }
 122                 return dist[node_num * num_places + 0]; */
 123         }
 124
 125         int best_this_cost = INFINITY;
 126         for (int i = 0; i < num_places; ++i) {
 127                 if (visited_mask & (1 << i)) {
 128                         continue;
 129                 }
 130
 131                 int cost = dist[node_num * num_places + i]
 132                     + tsp(i, visited_mask | (1 << i), cost_so_far + dist[node_num * num_places + i]);
 133                 if (cost < best_this_cost) {
 134                         best_this_cost = cost;
 135                 }
 136         }
 137
 138         cache[node_num * cache_size + visited_mask] = best_this_cost;
 139         return best_this_cost;
 140 }
 141
 142 void backtrack(int node_num, int visited_mask)
 143 {
 144         int num_places = places.size();
 145         if (visited_mask == finish_mask) {
 146                 return;
 147         }
 148
 149         int best_node = 0;
 150         int best_this_cost = INFINITY;
 151         for (int i = 0; i < num_places; ++i) {
 152                 if (visited_mask & (1 << i)) {
 153                         continue;
 154                 }
 155
 156                 int cost = dist[node_num * num_places + i] +
 157                     cache[i * cache_size + (visited_mask | (1 << i))];
 158                 assert(cost != -1);
 159                 if (cost < best_this_cost) {
 160                         best_node = i;
 161                         best_this_cost = cost;
 162                 }
 163         }
 164
 165         printf("%s [%d] [%d to %d costs %d]\n", places[best_node].c_str(), best_this_cost, node_num, best_node, dist[node_num * num_places + best_node]);
 166         backtrack(best_node, visited_mask | (1 << best_node));
 167 }
 168
 169 int main(void)
 170 {
 171         for ( ;; ) {
 172                 char name1[256];
 173                 char name2[256];
 174                 int dist;
 175
 176                 if (scanf("%s %s %d", name1, name2, &dist) != 3) {
 177                         break;
 178                 }
 179
 180                 check_name_inserted(name1);
 181                 check_name_inserted(name2);
 182                 sparse_dist.insert(make_pair(make_pair(name1, name2), dist));
 183         }
 184
 185         make_matrix();
 186         print_matrix();
 187         printf("\n");
 188         floyd_warshall();
 189         print_matrix();
 190
 191         init_tsp();
 192         tsp(0, 1, 0);
 193         printf("fg [%d]\n", best_cost);
 194         backtrack(0, 1);
 195 }