Travelling Salesman Problem

Who was the two that defined the travelling salesman problem in the 1800s?

• Wallace Rowan Hamilton & Thomas Kirkman
• William Rowan Hamilton & Thomas Kirkman
• William Rowan Hamilton & Thomas Kikoman
• William Rowan Hamilton & Tomas Kirtman

It is most easily expressed as a graph describing the locations of a set of nodes?

• Merge Sort
• Travelling Salesman Problem
• Knapsack Problem
• Bucket Sort

The salesman has to visit exactly one city from each state.

• True
• False

The purpose of the Travelling Salesman Problem is to Optimize the travelling cost.

• True
• False

Algorithm that randomly select the next city from the remaining non-visited cities until all cities are visited

• Greedy
• Random Path

Its an algorithm that Selects the non-visited city that is closest to the current city

• Greedy
• 2-Opt
• Random
• Simulated Annealing

What is the name of the algorithm that finds the upper bound

• Closest Vertix
• Closest Node
• Nearest Neighbour
• Nearest Vertix

The Algorithm used to find the lower bound

• Kruskal's Algorithm
• Nearest Neighbour
• Christofide's Algorithm

Rayno lives at A and wants to visit B C D and E before returning back to A find the Upper Bound

• 77
• 76
• 91
• 88

By Deleting vertex C, find the lower bound

• 25
• 44
• 62
• 43