Depth First Search Algorithm In Solving the Shortest Route Using the Concept of Generate and Test

Abstract

Depth First Search Algorithm is a search process to find the right solution that requires short memory and time in finding the Goal. The problem in this research is the difficulty of salesmen to find alternative short routes to arrive at the final node as consideration for finding solutions. The purpose of this study is to find the shortest path so that salesmen can easily and quickly get to the final solution by saving time and mileage. The Generate And Test concept consists of combining the Depth first search algorithm with the backward tracking process. All processes must be completed before the testing process is carried out. If the General And Test process is carried out sequentially or systematically, it will get the best value in finding a solution, the weakness if the search process is large or extensive then the search process takes a very long time. How it works Generatr and test, namely 1. Generate possible solutions in the form of state states with the concept of a one-position path to the destination path. 2. Test, select whether the solution can be accepted according to the existing criteria 3. If the solution has got the Goal then the search is stopped, if not then the process is continued until finding a solution. The final result of testing the shortest route is A-B-E-J-P-S-U = 25+21+24+24+17+18=129