Graph theory seeks to address different situations or problems in a business application or organisational setups. TSP (Traveling Salesman Problem) is usually considered NP-hard (nondeterministic polynomial time) in solving decision problems. This is because there are more than one possible action or directions when deciding to traverse through every city or vertex in a given graph to return to the original. Taking some journey down the historical lane, the TSP problem was formulated in1800s by an Irish mathematician W.R Hamilton and his British counterpart Thomas Kirkman. 

Combinatorial Optimisation Problem

TSP belongs to a large class known as combinatorial optimisation problems. Combinatorial optimisation is aimed at discovering the best object (or city in a map situation) from a finite set of objects (or list of cities). The best solution or decision in selecting the route between objects or cities is believed to be discrete or at least reduced to discrete. Hence, the problem becomes NP-hard as the ultimate goal of most combinatorial optimisation problems seeks to find an efficient way of allocating resources such as time or money depending on the scenario. 

The difficulty of the Traveling Salesman problem in Artificial Intelligence

Solving TSP is considered to be computationally challenging even in modern times. It becomes quite challenging when a salesman desires to find the shortest route through several cities to safely return home. Regardless of the challenges, some algorithms and methods have been modified or designed to solve this problem. The popular Depth First Search (DFS) and Breadth-First Search (BFS) algorithms are two possible ways for tackling TSP. 

Continue reading →