CODEWITHSUNDEEP
c++algorithmrecursiondynamic-programmingbacktracking
Sirupsen
Sirupsen

Reputation: 2115

Saving optimal path found with recursive backtracking

I have partially solved a problem on the UVA judge (see code below), with recursive backtracking/dynamic programming and bitmasking.

This gives the right final answer to the included test cases, however, I must also print the optimal path route, which I am unsure how to save in a recursive routine.

The problem is a travelling salesman problem, basically the problem is this:

Given n coordinates, find the shortest path between all these coordinates.

#include<iostream>
#include<cmath>
#include<climits>
#include<cstdio>
using namespace std;

#define MAX_N 10

struct Computer{
  double x;
  double y;
};

Computer computers[MAX_N];
double dist[MAX_N][MAX_N];
double DP[MAX_N][1 << MAX_N];

size_t n; 

double d(Computer a, Computer b) {
  return sqrt(pow((a.x - b.x), 2.0) + pow((a.y - b.y), 2.0)) + 16.0;
}

double recurse(int i, int switched)
{
  if(switched == (1 << n) - 1) return 0;
  if(DP[i][switched] != 0) return DP[i][switched];

  double local_min = INT_MAX;
  for(int j = 0; j < n; j++)
    if(i != j && !(switched & (1 << j)))
      local_min = min(dist[i][j] + recurse(j, switched | (1 << j)), local_min);

  return DP[i][switched] = local_min;
}

int main()
{
  for(unsigned int p = 1; cin >> n; p++) {
    if(n == 0) return 0;
    memset(DP, 0, sizeof DP);

    for(size_t i = 0; i < n; ++i) {
      Computer c; cin >> c.x >> c.y;
      computers[i] = c;
    }

    for(size_t i = 0; i < n; ++i) for(size_t j = 0; j < n; ++j)
      dist[i][j] = d(computers[i], computers[j]);

    printf("%d: %.2f\n", p, recurse(0, 1));
  }
}

Upvotes: 1

Views: 2054

Answers (2)

TemplateRex
TemplateRex

Reputation: 70506

Collecting the optimal path in one-player puzzles is a similar problem as saving the principal variation in two-player games such as chess. See this link on how to implement it.

The idea is to store a pointer to a vector/array of steps (moves in chess), and to update that array whenever your backtracking algorithm finds an improvement on the shortest path so far.

Upvotes: 1

Ben Ruijl
Ben Ruijl

Reputation: 5123

A common way of storing the path is to keep track of an additional map that stores the node the pathfinder took to get to the current point. When you've found the optimal route to the end node, you can then query this map until you are back at the starting node.

Upvotes: 1

Related Questions