Traveling Salesman in Constrained Env | Dataford Interview Questions

Describe your approach to solving the Traveling Salesman Problem in a resource-constrained environment.

Implement an exact solver for a complete directed graph. Given an n x n cost matrix, return the minimum cost of a tour that starts at city 0, visits every city exactly once, and returns to city 0. Use a bitmask dynamic programming approach suitable for n <= 20.

Function: tsp_min_cost(distances) Input is a square matrix of nonnegative numbers. Return a number.

Constraints

1 <= n <= 20
distances is an n x n square matrix
distances[i][j] is a nonnegative number
distances[i][i] may be zero and is never required for a multi-city transition
The graph is complete, so every city-to-city cost is defined
The tour must start and end at city 0

Function Signature

def tsp_min_cost(distances):

Your question is Traveling Salesman in Constrained Env. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem

Describe your approach to solving the Traveling Salesman Problem in a resource-constrained environment.

Function: tsp_min_cost(distances) Input is a square matrix of nonnegative numbers. Return a number.

Constraints

1 <= n <= 20
distances is an n x n square matrix
distances[i][j] is a nonnegative number
distances[i][i] may be zero and is never required for a multi-city transition
The graph is complete, so every city-to-city cost is defined
The tour must start and end at city 0

Function Signature

def tsp_min_cost(distances):

Your question is Traveling Salesman in Constrained Env. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.