TSP is a problem described in graph theory: the cities are defined as nodes in a graph, and edges is a road from one city to another. Traveling salesman wants to visit all the cities, but use the shortest path for that.

The solution exists is graph is connected (meaning that each city is connected by the road with each other, not necessarily direct road, but might be from other cities), and graph follows triangle rule, which means that the direct road between 2 cities is always shorter that going transit through some other city.

Helpful Answer?

Yes | No

Inappropriate?

To comment on this question, Sign In with Facebook or Sign Up

You might also be interested in: Interview Questions, Innovative Software Developer Interview Questions, BMW Interview

BMW Overview (BMW)

Edit

Website www.bmwgroup.com

HQ Munich, Germany

Industry

Automobile Manufacturing

Size

91,000+ Employees, $80B+ Revenue

Competitors

Volkswagen, Toyota, Daimler

Interviews by Company

Salaries by Company

Tags are like keywords that help categorize interview questions that have something in common.

About Us | Feedback | Help

Glassdoor ® is a registered trademark of Glassdoor, Inc.

Overview

Salaries

Reviews

Interviews

Photos

Jobs

Connections

11 Interview Reviews |

Interview Question for Innovative Software Developer at BMW:

What is travel salesman problem? What is the criteria for a unique optimal solution to exist?

Answers & Comments (1)

Flag this {0} as inappropriate

Thank you!

Oops!