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

  • I Gede Surya Rahayuda STMIK STIKOM Bali
  • Ni Putu Linda Santiari STMIK STIKOM Bali

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.
 

Downloads

Download data is not yet available.

References

[1] I. G. S. Rahayuda and N. P. L. Santiari, “Implementasi dan Perbandingan Metode Iterative Deepening Search dan Held-Karp pada Manajemen Pengiriman Produk,” SISFO, vol. 7 No. 2, 2018.
[2] D. Zai, “Simulasi Rute Terpendek Lokasi Pariwisata Di Nias Dengan Metode Breadth First Search Dan Tabu Search,” J InFact, vol. 1, pp. 30–41, 2016.
[3] S. Sukiswo, “Evaluasi Kinerja Algoritma Penjadwalan Weighted Round Robin Pada Wimax,” TRANSMISI, vol. 10, no. 2, pp. 58–64, 2008.
[4] T. S. Aziz and I. Alfi, “Penerapan Algoritma Alpha Beta Pruning Sebagai Kecerdasan Buatan Pada Game Pawn Battle,” Institut Teknologi Sepuluh Nopember, 2016.
[5] S. R. Wulandari, Y. Purwanto, and B. Irawan, “Evaluasi Algoritma Pencarian Jalur Pada Aplikasi e-iTRIP Guna Menentukan Rute Pariwisata Kota Bandung Berbasis Perangkat Mobile Android,” in Seminar Nasional Aplikasi Teknologi Informasi (SNATI), 2012.
[6] J. Sophia and N. Rama, “Improving the Proactive Routing Protocol using Depth First Iterative Deepening Spanning Tree in Mobile Ad Hoc Network,” Int. J. Electr. Comput. Eng. IJECE, vol. 7, no. 1, pp.
316–323, 2017.
[7] I. G. S. Rahayuda and N. P. L. Santiari, “Penerapan Pemrograman Dinamis Pada Manajemen Pengiriman Produk Menggunakan Metode Held Karp,” EProc. KNSI STIKOM Bali, pp. 513–518, 2017.
[8] I. G. S. Rahayuda and N. P. L. Santiari, “Implementasi dan Perbandingan Metode Iterative Deepening Search dan Held-Karp pada Manajemen Pengiriman Produk,” J SISFO Inspirasi Prof Sist Inf Inst. Teknol
Sepuluh Nop, vol. 7, 2017.
[9] Y. I.-U. M. Kudus, “Pengujian Sistem Informasi Pengelolaan Pelatihan Kerja Upt. BLK Kabupaten Kudus dengan Metode Whitebox Testing,” Speed-Sentra Penelit. Eng. Dan Edukasi, vol. 9, no. 3, 2017.
[10]Selvia Lorena Br Ginting, “Evaluasi Algoritma CB* Untuk Konstruksi Struktur Bayesian Network Dalam Data Mining,” presented at the Konferensi Nasional Sistem dan Informatika 2008, Bali, 15 November, vol. Vol. 9, No. 3, pp. 233– 239.
[11]S. Tanaka and K. Tierney, “Solving realworld sized container pre-marshalling problems with an iterative deepening branch-and-bound algorithm,” Eur. J. Oper. Res., vol. 264, no. 1, pp. 165–180,
2018.
[12]M. Naumov, A. Vrielink, and M. Garland, “Parallel Depth-First Search for Directed Acyclic Graphs,” in Proceedings of the Seventh Workshop on Irregular Applications: Architectures and Algorithms, 2017, p. 4.
[13]M. M. Asadi, H. Mahboubi, J. Habibi, A. G. Aghdam, and S. Blouin, “Connectivity Assessment of Random Directed Graphs with Application to Underwater Sensor Networks,” IEEE Trans. Control Syst. Technol., vol. 25, no. 4, pp. 1457–1464, 2017.
[14]T. S. Aziz and I. Alfi, “Penerapan Algoritma Alpha Beta Pruning Sebagai Kecerdasan Buatan Pada Game Pawn Battle,” Institut Teknologi Sepuluh Nopember, 2016.
[15]J. Pinto and A. Fern, “Learning partial policies to speedup MDP tree search via reduction to IID learning,” J. Mach. Learn. Res., vol. 18, no. 1, pp. 2179–2213, 2017.
[16]H. Vamja, “Comparative Analysis of Different Path Finding Algorithms to Study Limitations and Progress,” Int J Emerg Technol Adv Eng, vol. 7, no. 9, pp. 68–75, 2017.
[17]H. Honainah, “Optimasi Neural Network Untuk Mendeteksi Penyakit Diabetes Dengan Algoritma Genetika,” J. Tek. Inform., vol. 6, no. 01, 2017.
[18]G. Goisque and C. Rapine, “Polynomial time algorithm for multi-level in series capacitated lot-sizing problems with constant batch size,” in International Workshop on Lot Sizing 2016, 2016.
[19]R. Palani Kumar, “Internal and External Measures of Code Quality Impact on Refactoring,” SSRG Int. J. Civ. Eng. – ICCREST’17, pp. 70–72, 2017.
[20]K. Maheswaran and A. Aloysius, “An Analysis of Object Oriented Complexity Metrics,” 2017.
[21]A. Becker, E. Fox-Epstein, P. N. Klein, and D. Meierfrankenfeld, “Engineering an Approximation Scheme for Traveling Salesman in Planar Graphs,” in LIPIcsLeibniz International Proceedings in Informatics, 2017, vol. 75.
[22]C. Chekuri, “Approximating the Held-Karp Bound for Metric TSP in Nearly-Linear Time,” ArXiv Prepr. ArXiv170204307, 2017.
[23]M. Zia, Z. Cakir, and D. Z. Seker, “A New Spatial Approach for Efficient Transformation of Equality-Generalized TSP to TSP,” in Free and Open Source Software for Geospatial (FOSS4G) Conference Proceedings, 2017, vol. 17, p.5.
[24]D. J. Moylett, N. Linden, and A. Montanaro, “Quantum speedup of the traveling-salesman problem for boundeddegree graphs,” Phys. Rev. A, vol. 95, no. 3, pp. 1–12, 2016.
[25]T. Moore, “Implementing the Held-Karp Lower Bound Algorithm in Python,” 2015.
[26]Rohit and Purnendra Kumar, “A Survey for the Quality Assessment of Object Oriented Software,” Int. J. Inf. Futur. Res., vol. Vol. 4, No. 9, pp. 7700–7705, 2017.
[27]C. Chekuri and K. Quanrud, “Approximating the Held-Karp Bound for Metric TSP in Nearly-Linear Time,” ArXiv Prepr. ArXiv170204307, 2017.
[28]Niveth Vijay K and Vipin Kumar K S, “Automated Test Path Generation using Genetic Algorithm,” Int. J. Eng. Res. Technol. IJERT, vol. 6, no. 7, 2017.
Published
2017-12-05
How to Cite
RAHAYUDA, I Gede Surya; SANTIARI, Ni Putu Linda. BASIS PATH TESTING OF ITERATIVE DEEPENING SEARCH AND HELD-KARP ON PATHFINDING ALGORITHM. Jurnal Ilmiah Kursor, [S.l.], v. 9, n. 2, dec. 2017. ISSN 2301-6914. Available at: <http://kursorjournal.org/index.php/kursor/article/view/129>. Date accessed: 30 nov. 2021. doi: https://doi.org/10.28961/kursor.v9i2.129.
Section
Articles