$35
Project 2: TSP – Search with BFS and DFS
· Learning objectives:
o Search Techniques for graphs
o BFS and DFS algorithms
· Background
o A Traveling Salesperson Problem (TSP) is an NP-complete problem. A salesman is given a list of cities and a cost to travel between each pair of cities (or a list of city locations). The salesman must select a starting city and visit each city exactly one time and return to the starting city. His problem is to find the route (also known as a Hamiltonian Cycle) that will have the lowest cost.
For this lab we are looking at a special case of TSP in which not all cities are connected and the salesperson only needs to find the best path to a target city not visit all cities.
· Problem
o For the given dataset (11PointDFSBFS.tsp), starting at the first city (city 1) find the shortest path to the goal city (city 11).
o Implement Breadth First Search (BFS) and Depth First Search (DFS) algorithms
o Visit cities in numerical order if you need to break a tie. You can hardcode connected edges into your algorithm for this problem, see table below
Table 1: Cities connected by a one way path of Euclidian distance (left = from, top = to).
pt
1
2
3
4
5
6
7
8
9
10
11
1
x
x
x
2
x
3
x
x
4
x
x
x
5
x
x
6
x
7
x
x
8
x
x
x
9
x
10
x
· Deliverables
o Project report (3-4 pages) describing results of your experiments and your implementation. Which algorithm was faster in finding the target city? How long did it take (time and transitions)?
o Well-commented source code for your project. You can use any language you like, but I reserve the right to ask you to demo performance of your algorithm on a new dataset.
o You don’t have to include a GUI with visual representation of the solutions for this project, but it might be useful for your future TSP related projects in this course.