Monday, November 10, 2014

UVa Problem 116 - Unidirectional TSP

Problem:

Solution:

Another classic dynamic programming algorithm - Viterbi. When you read the Wikipedia link, it talks a lot about its application in Hidden Markov Model, or convolutional code, don't be scared with those. In abstract, Viterbi is nothing but just finding a shortest path in a trellis, a graph that can be divided into layer such that it has no intra layer links and connect only to intermediate layer.

A trick I used is to find the shortest path from the right hand side to the left hand side, so that I can simply traverse the parent pointers to get the back the forward path directly.

Code:

#include "stdafx.h"

// http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=52

#include "UVa116.h"

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long int64;

int UVa116()
{
while (true)
{
int num_rows;
int num_cols;
cin >> num_rows;
if (cin.eof())
{
break;
}
cin >> num_cols;
vector<vector<int> > input;
input.resize(num_rows);
for (int r = 0; r < num_rows; r++)
{
input[r].resize(num_cols);
for (int c = 0; c < num_cols; c++)
{
cin >> input[r][c];
}
}

vector<int64> best_cost;
vector<int64> next_best_cost;
vector<vector<int> > next;

best_cost.resize(num_rows);
next_best_cost.resize(num_rows);
next.resize(num_rows);

// The virtual last column has no cost associated with it
for (int r = 0; r < num_rows; r++)
{
next_best_cost[r] = 0;
next[r].resize(num_cols);
}

for (int c = num_cols - 1; c >= 0; c--)
{
for (int r = 0; r < num_rows; r++)
{
int previous_row = (r == 0) ? num_rows - 1 : r - 1;
int next_row = (r + 1) % num_rows;
int64 previous_cost = next_best_cost[previous_row];
int64 current_cost = next_best_cost[r];
int64 next_cost = next_best_cost[next_row];
int64 best_next_cost = min(previous_cost, min(current_cost, next_cost));
best_cost[r] = input[r][c] + best_next_cost;
int next_min = -1;
bool first = true;

if (best_next_cost == previous_cost)
{
if (first)
{
next_min = previous_row;
first = false;
}
else
{
next_min = min(previous_row, next_min);
}
}
if (best_next_cost == current_cost)
{
if (first)
{
next_min = r;
first = false;
}
else
{
next_min = min(r, next_min);
}
}
if (best_next_cost == next_cost)
{
if (first)
{
next_min = next_row;
first = false;
}
else
{
next_min = min(next_row, next_min);
}
}
next[r][c] = next_min;
}
for (int r = 0; r < num_rows; r++)
{
next_best_cost[r] = best_cost[r];
}
#if LOG
cout << "Col: " << c << endl;
for (int r = 0; r < num_rows; r++)
{
cout << best_cost[r] << " " << next[r][c] << endl;
}
cout << "---" << endl;
#endif
}

bool first = true;
int64 best_row_cost = -1;
int best_row_index = 0;
for (int r = 0; r < num_rows; r++)
{
if (first)
{
best_row_cost = best_cost[r];
best_row_index = r;
first = false;
}
else if (best_cost[r] < best_row_cost)
{
best_row_cost = best_cost[r];
best_row_index = r;
first = false;
}
}
int best_row = best_row_index;
for (int c = 0; c < num_cols; c++)
{
if (c != 0)
{
cout << " ";
}
cout << (best_row + 1);
best_row = next[best_row][c];
}
cout << endl << best_row_cost << endl;
}
return 0;
}