BASIS PATH TESTING OF ITERATIVE DEEPENING SEARCH AND HELD-KARP ON PATHFINDING ALGORITHM

Abstract

This research is a continuation of previous research, where in previous research discussed about the implementation of both methods. Implementation is done using visual basic programming language. Both methods are compared based on the results obtained. While in the current study, research is more focused on the analysis of the program flow that has been made. Evaluation is done by using basis path method, there are several processes performed on the method, such as: flowgraph, independent path, cyclomatic complexity and graph matrix. In addition to the evaluation of program flow, evaluation is also done based on program performance. Performance tests are based, time, cpu and memory. Based on the evaluation using the base path, obtained flowgraph structure and independent path different, but obtained the result of CC and Graph Matrix calculation of the same between IDS and HK method is 4. Based on evaluation in terms of performance, process the program from entering data and until getting the result, the HK method takes a longer time than the IDS method. The IDS method takes 2.7 seconds while the HK method takes 2.8 seconds.

Keywords

• Held-Karp, Iterative Deepening Search, visual basic, basis path, cyclomatic complexcity, graph matrix