[T2.1] Backtracking Algorithm

[jvdcf]

In this approach, you are asked to develop a backtracking algorithmic approach to the TSP for a graph starting and ending the node tour on node labelled with the zero-identifier label. You are expected to use the small graphs to validate this approach and to observe that for the larger graphs this approach is not really feasible. To this extent, you are suggested to plot the execution time (or other performance metrics you find significant) to illustrate the feasibility or not of this approach for larger graphs.

[jvdcf]

Implementation:

/**
 * @brief Backtracking algorithm to solve the Travelling Salesman Problem
 * @details Boundings:
 * - If the current cost is already higher than the best cost, stop exploring this path
 * - If the current path reaches a vertex that has already been visited, stop exploring this path
 * @note Time Complexity: O(n!) where n is the number of vertices
 * @param g Graph with the vertices, edges and weights
 * @param p The current possibility to be explored
 * @param bestCost A reference to the best cost found so far (updated with the result)
 * @return A pair with the cost of the best path and the path itself
 */
std::pair<unsigned, std::vector<unsigned>> backtracking(Graph<unsigned>& g, const Possibility& p, double& bestCost) {
  // Base cases
  if (p.possibleEdges.empty()) {
    if (p.path.size() == g.getNumVertex() + 1) {
      if (p.cost < bestCost) bestCost = p.cost;
      return {p.cost, p.path};    // Hamiltonian cycle complete
    } else {
      return {UINT_MAX, p.path};  // Invalid path
    }
  }

  // Bounding
  if (p.cost >= bestCost) return {UINT_MAX, p.path};

  Edge<unsigned>* e = p.possibleEdges.front();
  std::queue<Edge<unsigned>*> possibleEdges = p.possibleEdges;
  double cost = p.cost;
  std::vector<unsigned> path = p.path;
  Possibility next;

  // Left choice: add edge to path
  double leftCost = cost + e->getWeight();
  auto leftPath = path;
  leftPath.push_back(e->getDest()->getInfo());
  auto leftPossibleEdges = generatePossibleEdges(g, e->getDest(), leftPath);
  next = {leftCost, leftPossibleEdges, leftPath};
  auto leftResult = backtracking(g, next, bestCost);

  // Right choice: skip edge
  auto rightPossibleEdges = possibleEdges;
  rightPossibleEdges.pop();
  next = {cost, rightPossibleEdges, path};
  auto rightResult = backtracking(g, next, bestCost);

  // Select best choice
  if (leftResult.first <= rightResult.first) return leftResult;
  else return rightResult;
}

Auxiliar functions:

#define START_NUMBER 0

struct Possibility {
  double cost;                                // Current cost of all edges selected until now
  std::queue<Edge<unsigned>*> possibleEdges;  // Edges that can be selected if this edge is ignored (the first edge is the one being considered)
  std::vector<unsigned> path;                 // Path of vertices selected until now
};

std::queue<Edge<unsigned>*> generatePossibleEdges(Graph<unsigned>& g, Vertex<unsigned>* v, const std::vector<unsigned>& path) {
  std::queue<Edge<unsigned> *> possibleEdges;
  if (path.size() == g.getNumVertex()) {  // If all vertices have been visited, add edge to start
    for (Edge<unsigned> *e: v->getAdj()) {
      if (e->getDest()->getInfo() == START_NUMBER) {
        possibleEdges.push(e);
        break;
      }
    }
  } else {
    for (Edge<unsigned> *e: v->getAdj()) { // Add all edges that their destination vertex hasn't been visited yet
      if (std::find(path.begin(), path.end(), e->getDest()->getInfo()) != path.end()) continue;
      possibleEdges.push(e);
    }
  }
  return possibleEdges;
}

---

Example of execution (da2324_p07: ex.8)

Graph<unsigned> createGraph(const unsigned int **dists, unsigned int n) {
  Graph<unsigned> g;
  for (unsigned i = 0; i < n; i++)
    g.addVertex(i);
  for (unsigned i = 0; i < n; i++) {
    for (unsigned j = 0; j < n; j++) {
      if (i == j) continue;
      g.addEdge(i, j, dists[i][j]);
    }
  }
  return g;
}

const unsigned int n = 4;
const unsigned int dists[n][n] = {{0, 10, 15, 20}, {10, 0, 35, 25}, {15, 35, 0, 30}, {20, 25, 30, 0}};

Graph<unsigned> g = createGraph(dists, n);
Vertex<unsigned>* start = g.findVertex(START_NUMBER);

std::queue<Edge<unsigned>*> possibleEdges = generatePossibleEdges(g, start, {0});
Possibility p = {0, possibleEdges, {0}};
double bestCost = UINT_MAX;

auto result = backtracking(g, p, bestCost);
// result.first = 80;
// result.second = {0, 1, 3, 2, 0};