Travelling city problem using depth first search

We know travelling salesman problem is a fully observable, static and deterministic problem. It can be solved by depth first search approach. Depth first search has an advantage that it uses limited amount of memory. But the disadvantage is that it does not solve problems optimally. The solution we got might not be optimal one. Also depth first search may end up in infinite loops in a tree if it doesn’t find an solution. Let us try depth first search on a travelling salesman problem

Here is the map of Uttara Kannada

UttaraKannada

Here are the 11 cities that are connected to each other. A travelling salesman needs to travel from one city to another. Suppose a travelling salesman needs to find way from one city to another  and asks a question to computer, how will it find out the path from one city to another? The intelligent agent program running in a computer can answer it , based on the available information about cites and how they are connected to each other. In this program intelligent agent uses depth first search to find solution to the salesman’s problem.

Here is how the cities are connected to each other

Bhatkal -> Honnavar, Siddapur

Honnavar- > Bhatkal, Siddapur, Kumta

Kumta -> Honnavar, Ankola, Sirsi, Siddapur

Siddapur -> Honnavar, Bhatkal,Sirsi, Kumta

Sirsi -> Kumta, Siddapur, Yellapur, Mundagod

Yellapur -> Ankola, Joida, Haliyal, Mundagod, Sirsi

Mundagod -> Yellapur, Sirsi, Haliyal

Haliyal -> Yellapur, Mundagod, Joida

Joida -> Yellapur, Haliyal, Karwar

Karwar -> Ankola, Joida

Ankola -> Yellapur, Kumta, Karwar

 

Depth first first search traverses through each tree first. It uses the stack data structures to store the nodes. The last node that was checked for goal city will be checked for paths for other cities. The child nodes are created for those cities and added to stack.  Depth first search can go deeper in its iterations with very less burden on memory. In PHP stack is implemented by a special data structure special stack

push($value) is used for pushing value into the stack and pop() is used for popping value from the stack.

You can see from the program here that depth first uses less memory compared to breadth first search. Here is the code to depth first search in PHP