PENERAPAN METODE HEURISTIK (ALGORITMA IDA* DAN B&B) DALAM PEMECAHAN N-Queen Problem
-
Novi Penna(1)
Universitas Nusa Cendana
-
Sebastianus Adi Santoso Mola(2*)
Universitas Nusa Cendana
http://orcid.org/0000-0002-1698-0758
-
Meiton Boru(3)
Universitas Nusa Cendana
(*) Corresponding Author
Abstract
N-Queen problem is a problem which a N-Queen pawn in is place chess with n x n size. N-Queen pawn is a put in such away in chess board with under condition that the queen pawns do not attack each other. The attacking movement of N-Queen problem is similar to the way of the queen pawn attacking in chess. Commonly the queen pawn moves horizontally to left and right, forward and backward vertically and also diagonally, so there are no queen pawns in a line of horizontal, vertical and diagonal.
Heuristical searching is one of the method which can be used to solve the game of N-Queen problem selectively, by giving solution of the shortest time channel efficiently in order to able the user to solve this game well, fast and relevantly. Some algorithms that use heuristic is Iterative Deepening algorithm A* (IDA*) and Branch and Bound (B&B) algorithm. The used heuristic function is by seeing the numbers of boxes which are empty and the number of queen which is not be put in board yet.
The aim of making this final project to implement the solving of N-Queen problem using heuristic searching (B&B and IDA*). From this implementation could be seen that IDA* and B&B algorithm is able to give channel in solving N- Queen problem. After a repetition of test by using 19 sheet of data, it is shown the comparison of result between IDA* algorithm and B&B algorithm which IDA* algorithm result the shorter channel in solving N-Queen problem based on the node 61%, and time 41% which better than B&B algorithm.
Downloads
References
[2] Anwar, Muhammad Nasrul. 2010. 8 Puzzle dengan menggunakan algoritma Iterative Deepening Search (IDS), http://journal.amikom.ac.id/index.php/TI/article/download/3808/1553, diakses tanggal 12 Desember 2013.
[3] Booch, Grady. 1999. Visual Modeling With Rational Rose 2000 and UML. Addison-Wesley. New Jersey.
[4] Jogiyanto. 1999. Analisis dan Desain Sisem Informasi. Andi Offset. Yogyakarta.
[5] Kadir, Abdul. 2003. Pengenalan Sistem Informasi. Andi Offset. Yogyakarta.
[6] Kusumadewi, Sri. 2003. Artificial Intelegent. Graha Ilmu. Yogyakarta.
[7] Kusumadewi, Sri. 2007. Kecerdasan Buatan (Teknik dan Aplikasinya). Graha Ilmu. Yogyakarta.
[8] Munir, Rinaldi. 2004. Algoritma Branch and Bound. Bahan Kuliah ke-11 IF2251 Strategi Algoritmik. https://www.google.com/webhp?sourceid=chrome-instant&ion=1&espv=2&ie=UTF8#q=rinaldi+munir+algoritma+branch+and+bound+bahan+kuliah+ke+11+IF2251+strategi+algoritmik, diakses tanggal 02 Februari 2014.
[9] Pertiwi, Nursyamsiah. dkk. 2006. Penerapan Algoritma BFS, DFS, DLS dan IDS Dalam Pencarian Solusi Water Jug Problem, https://www.google.com/webhp?sourceid=chrome-instant&ion=1&espv=2&ie=UTF-8#q=nursyamsiah+pertiwi+penerapan+algoritma+bfs,+dfs,,dfs+dan+ids+dalam+pencarian+solusi+water+jug+problem&spell=1, diakses tanggal 02 Februari 2014.
[10] Rumbaugh, James, dkk. 1999. The Unified Modeling Languange Reference Manual. Addison-Wesley. New Jersey.
[11] Setiawan, Christian Yulius. 2008. Implementasi Metode Algoritma IDA* untuk Pencarian Jalur Terpendek Dengan Studi Kasus Yellow Pages Kota Bandung Menggunakan Teknologi WAP. Bandung.
[12] Suyanto. 2011. Artificial Intelligence. Bandung. Informatika.
[13] Tandoe, Arie. 2012. Penerapan Pohon dengan Algoritma Branch and Bound Dalam Menyelesaikan N-Queen Problem, Makalah IF2091 Struktur Diskrit–SemI Tahun 2011/2012. http://informatika.stei.itb.ac.id/~rinaldi.munir/Matdis/2011-2012/Makalah2011/Makalah-IF2091-2011-074.pdf, diakses tanggal 05 Februari 2014.
Copyright (c) 2018 Jurnal Komputer dan Informatika
This work is licensed under a Creative Commons Attribution 4.0 International License.
The author submitting the manuscript must understand and agree that if accepted for publication, authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution (CC-BY) 4.0 License that allows others to share the work with an acknowledgment of the work’s authorship and initial publication in this journal.
