Review Jurnal Luar

Tugas Review Paper Kecerdasan Buatan Metode Searching

Nama Kelompok : Taufiqul Hafizh K.A Mohammad Sulfi Al Basit Satria Azam Madani

(A11.2016.09825) (A11.2016.09827) (A11.2016.09852)

UNIVERSITAS DIAN NUSWANTORO FAKULTAS ILMU KOMPUTER 2019

Paper 1 Judul

Pathfinding in Strategy Games and Maze Solving Using A* Search Algorithm Jurnal Al-Mansour University College, Baghdad, Iraq Volume & Halaman Vol.4 dan 12 halaman Tahun 2016 Penulis Nawaf Hazim Barnouti, Sinan Sameer Mahmood Al-Dabbagh, Mustafa Abdul Sahib Naser Reviewer -Taufiqul Hafizh KA (A11.2016.09825) -Mohammad Sulfi Al Basit (A11.2016.09827) -Satria Azam Madani (A11.2016.09852) Tanggal 1 April 2019 Tujuan Penelitian

Subjek Penelitian Metode Penelitian Definisi Algorithm A*

Langkah-langkah pencarian A*

Hasil Penelitian

A* search algorithm is used to find the shortest path between the source and destination on image that represents a map or a maze. (algoritma pencarian A * digunakan untuk menemukan jalur terpendek antara sumber dan tujuan pada gambar yang mewakili peta atau labirin) Peta atau Labirin Algorithm A* A* is a generic search algorithm which can be used to find solutions for several problems, pathfinding basically to be one of them. This algorithm brings together feature of uniform-cost search and heuristic search. (A * adalah algoritma pencarian generik yang dapat digunakan untuk menemukan solusi untuk beberapa masalah, merintis jalan pada dasarnya menjadi salah satunya. Algoritma ini menyatukan fitur pencarian seragambiaya dan pencarian heuristik.) 1. Let’s P is the source node. 2. Assign g , h , and f values to P . 3. Add the source node to the open list. 4. Repeat the following steps:  Look for the node which has the lowest f on the open list. Refer to this node as the current node.  Switch it to the closed list.  For each reachable node from the current node 5. Tracing backwards from the destination node to the source node. That is the path. The system overall performance is acceptable and able to find the shortest path between two points on the image. More than 85% images can find the shortest path between the selected two points.( Kinerja keseluruhan sistem dapat diterima dan dapat menemukan jalur terpendek antara dua titik pada gambar. Lebih dari 85% gambar dapat menemukan jalur terpendek antara dua titik yang dipilih.)

Kelebihan Penelitian

Maka dapat disimpulkan bahwa keunggulan Algoritma A* adalah : 1. Lebih lambat dalam mencari jalur optimum,tapi hasil yang diberikan lebih akurat. 2. Penggunaan algoritma A* cocok diaplikasikan ke dalam aplikasi permainan yang membutuhkan pencarian jalan

Paper 2 Judul

Shortest path and vehicle trajectory aided map-matching for low frequency GPS data Jurnal Transport Studies Group, Department of Civil and Building Engineering, Loughborough University, Leicestershire LE11 3TU, United Kingdom Volume & Halaman Vol.55 dan 12 halaman Tahun 2015 Penulis Mohammes Quddus and Simon Washington Reviewer -Taufiqul Hafizh KA (A11.2016.09825) -Mohammad Sulfi Al Basit (A11.2016.09827) -Satria Azam Madani (A11.2016.09852) Tanggal 1 April 2019 Tujuan Penelitian

Subjek Penelitian Metode Penelitian Definisi A*

Langkah-langkah pencarian A*

this paper develops a new weight-based shortest path and vehicle trajectory aided map-matching (stMM) algorithm that enhances the map-matching of low frequency positioning data on a road map. The well-known A∗ search algorithm is employed to derive the shortest path between two points while taking into account both link connectivity and turn restrictions at junctions. (makalah ini mengembangkan algoritme pencocokan jalur berbantuan terpendek berbasis lintasan dan kendaraan berdasarkan berat (stMM) baru yang meningkatkan pencocokan peta data posisi frekuensi rendah pada peta jalan. Algoritma pencarian A known yang terkenal digunakan untuk mendapatkan jalur terpendek antara dua titik sambil memperhitungkan konektivitas tautan dan mengubah batasan di persimpangan) lintasan dan kendaraan berdasarkan berat (stMM) A* Algorithm A* is a generic search algorithm which can be used to find solutions for several problems, pathfinding basically to be one of them. This algorithm brings together feature of uniform-cost search and heuristic search. (A * adalah algoritma pencarian generik yang dapat digunakan untuk menemukan solusi untuk beberapa masalah, merintis jalan pada dasarnya menjadi salah satunya. Algoritma ini menyatukan fitur pencarian seragambiaya dan pencarian heuristik.) 1. Let’s P is the source node. 2. Assign g , h , and f values to P . 3. Add the source node to the open list. 4. Repeat the following steps:



Hasil Penelitian

Kelebihan Penelitian

Look for the node which has the lowest f on the open list. Refer to this node as the current node.  Switch it to the closed list.  For each reachable node from the current node 5. Tracing backwards from the destination node to the source node. That is the path. An efficient A∗ shortest path search algorithm was employed to derive the shortest path between two consecutive GPS fixes. Both link features (i.e. connectivity) and turn restrictions at junctions were taken into account while deriving the shortest path using the A∗ algorithm. In addition to the input currently used in existing map-matching algorithms such as the proximity and the bearing difference, two additional weights related to the shortest path distance and the heading difference of vehicle trajectory were introduced to enhance map-matching of low frequency positioning data. (Algoritma pencarian jalur terpendek A efficient yang efisien digunakan untuk mendapatkan jalur terpendek antara dua perbaikan GPS secara berurutan. Kedua fitur tautan (mis. Konektivitas) dan pembatasan belokan di persimpangan diperhitungkan saat menurunkan jalur terpendek menggunakan algoritma A ∗. Selain input yang saat ini digunakan dalam algoritma pencocokan peta yang ada seperti kedekatan dan perbedaan bantalan, dua bobot tambahan yang terkait dengan jarak lintasan terpendek dan perbedaan tajuk lintasan kendaraan diperkenalkan untuk meningkatkan pencocokan peta dari data posisi frekuensi rendah.) Maka dapat disimpulkan baahwa keunggulan Metode A* adalah : 1. Lebih lambat dalam mencari jalur optimum,tapi hasil yang diberikan lebih akurat. 2. Penggunaan algoritma A* cocok diaplikasikan ke dalam aplikasi permainan yang membutuhkan pencarian jalan

Paper 3 BFS-4K: An Efficient Implementation of BFS for Kepler GPU Architectures Jurnal IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS Volume & Halaman Vol.26 N0.7 dan 14 halaman Tahun 2015 Penulis Federico Busato and Nicola Bombieri Reviewer -Taufiqul Hafizh KA (A11.2016.09825) -Mohammad Sulfi Al Basit (A11.2016.09827) -Satria Azam Madani (A11.2016.09852) Tanggal 1 April 2019 Judul

Tujuan Penelitian

Subjek Penelitian Metode Penelitian Definisi Algorithm BFS

Langkah-langkah pencarian BFS

Hasil Penelitian

Kelebihan Penelitian

The paper presents different strategies implemented in BFS-4K to deal with the potential workload imbalance and thread divergence caused by any actual graph non-homogeneity. The paper presents the experimental results conducted on several graphs of different size and characteristics to understand how the proposed techniques are applied and combined to obtain the best performance from the parallel BFS visits. (Makalah ini menyajikan berbagai strategi yang diterapkan dalam BFS-4K untuk menangani potensi ketidakseimbangan beban kerja dan divergensi benang yang disebabkan oleh grafik non-homogenitas aktual. Makalah ini menyajikan hasil eksperimen yang dilakukan pada beberapa grafik dengan ukuran dan karakteristik yang berbeda untuk memahami bagaimana teknik yang diusulkan diterapkan dan dikombinasikan untuk mendapatkan kinerja terbaik dari kunjungan BFS paralel) graphics processing units (GPUs) Algorithm BFS BFS is one of the most import graph algorithms. It is used in several different contexts such as image processing, state space searching, network analysis, graph partitioning, and automatic theorem proving (BFS adalah salah satu algoritma grafik yang paling banyak diimpor. Ini digunakan dalam beberapa konteks yang berbeda seperti pemrosesan gambar, pencarian ruang negara, analisis jaringan, partisi grafik, dan pembuktian teorema otomatis) 1. Masukkan simpul ujung (akar) ke dalam antrian. 2. Ambil simpul dari awal antrian, lalu cek apakah simpul merupakan solusi. 3. Jika simpul merupakan solusi, pencarian selesai dan hasil dikembalikan.. 4. Jika simpul bukan solusi, masukkan seluruh simpul yang bertetangga dengan simpul tersebut (simpul anak) ke dalam antrian. 5. Jika antrian kosong dan setiap simpul sudah dicek, pencarian selesai dan mengembalikan hasil solusi tidak ditemukan. 6. Ulangi pencarian dari langkah kedua. This paper presented BFS-4K, a parallel implementation of BFS for Kepler GPU architectures. BFS-4K implements different techniques to deal with the potential workload imbalance and thread divergence caused by any actual graph non-homogeneity (Makalah ini menyajikan BFS-4K, implementasi paralel BFS untuk arsitektur GPU Kepler. BFS-4K menerapkan teknik berbeda untuk menangani ketidakseimbangan beban kerja potensial dan divergensi ulir yang disebabkan oleh grafik nonhomogenitas aktual) Maka dapat disimpulkan bahwa keunggulan Algoritma BFS adalah : 1. Tidak akan menemui jalan buntu.

2. Menjamin ditemukannya solusi (jika solusinya memang ada) dan solusi yang ditemukan pasti yang paling baik. 3. Jika ada satu solusi maka bread-first search akan menemukannya Paper 4 Judul

Complete Solution of Eight Puzzle Problem using BFS in CUDA Environment Jurnal IEEE International WIE Conference on Electrical and Computer Engineering(WIECON-ECE) Volume & Halaman Vol.- dan 5 halaman Tahun 2015 Penulis Masuma Sultana dan Rathindra Nath Dutta Reviewer -Taufiqul Hafizh KA (A11.2016.09825) -Mohammad Sulfi Al Basit (A11.2016.09827) -Satria Azam Madani (A11.2016.09852) Tanggal 1 April 2019 Tujuan Penelitian

Subjek Penelitian Metode Penelitian Definisi Algorithm BFS

Langkah-langkah pencarian BFS

Hasil Penelitian

Objective of this work is to find the complete solution of eight puzzle problem i.e. examining all the permutations for solvability (Tujuan dari pekerjaan ini adalah untuk menemukan solusi lengkap dari delapan masalah puzzle yaitu memeriksa semua permutasi untuk solvabilitas) Puzzle Algorithm BFS BFS is one of the most import graph algorithms. It is used in several different contexts such as image processing, state space searching, network analysis, graph partitioning, and automatic theorem proving (BFS adalah salah satu algoritma grafik yang paling banyak diimpor. Ini digunakan dalam beberapa konteks yang berbeda seperti pemrosesan gambar, pencarian ruang negara, analisis jaringan, partisi grafik, dan pembuktian teorema otomatis) 1. Masukkan simpul ujung (akar) ke dalam antrian. 2. Ambil simpul dari awal antrian, lalu cek apakah simpul merupakan solusi. 3. Jika simpul merupakan solusi, pencarian selesai dan hasil dikembalikan.. 4. Jika simpul bukan solusi, masukkan seluruh simpul yang bertetangga dengan simpul tersebut (simpul anak) ke dalam antrian. 5. Jika antrian kosong dan setiap simpul sudah dicek, pencarian selesai dan mengembalikan hasil solusi tidak ditemukan. 6. Ulangi pencarian dari langkah kedua. To find out complete solution of eight puzzle problem on the GPU using the CUDA programming model (Untuk menemukan solusi lengkap dari delapan masalah puzzle pada GPU menggunakan model pemrograman CUDA)

Kelebihan Penelitian

Maka dapat disimpulkan bahwa keunggulan Algoritma BFS adalah : 1. Tidak akan menemui jalan buntu. 2. Menjamin ditemukannya solusi (jika solusinya memang ada) dan solusi yang ditemukan pasti yang paling baik. 3. Jika ada satu solusi maka bread-first search akan menemukannya.

Paper 5 Power-Efficient Breadth-First Search with DRAM Row Buffer Locality-Aware Address Mapping Jurnal High Performance Graph Data Management and Processing Workshop. Volume & Halaman Vol.- dan 8 halaman Tahun 2016 Penulis Satoshi Imamura, Yuichiro Yasui, Koji Inoue, Takatsugu Ono, Hiroshi Sasaki, and Katsuki Fujisawa. Reviewer -Taufiqul Hafizh KA (A11.2016.09825) -Mohammad Sulfi Al Basit (A11.2016.09827) -Satria Azam Madani (A11.2016.09852) Tanggal 1 April 2019 Judul

Tujuan Penelitian

Subjek Penelitian Metode Penelitian Definisi Algorithm BFS

Langkahlangkah pencarian BFS

In this work, we focus on the power efficiency of DRAM and investigate the memory access pattern of a state-of-the-art BFS implementation using a cycle-accurate processor simulator. (Dalam pekerjaan ini, kami fokus pada efisiensi daya DRAM dan menyelidiki pola akses memori dari implementasi BFS yang canggih dengan menggunakan simulator prosesor yang akurat.) Daya Algorithm BFS Breadth-first search (BFS) is one of the most representativealgorithmsforsuchapplications;therefore,manyresearchers have tuned it to maximize performance. (Breadth-first search (BFS) adalah salah satu aplikasi yang paling representatif untuk aplikasi ini, oleh karena itu, banyak peneliti telah menyetelnya untuk memaksimalkan kinerja) 1. Masukkan simpul ujung (akar) ke dalam antrian. 2. Ambil simpul dari awal antrian, lalu cek apakah simpul merupakan solusi. 3. Jika simpul merupakan solusi, pencarian selesai dan hasil dikembalikan.. 4. Jika simpul bukan solusi, masukkan seluruh simpul yang bertetangga dengan simpul tersebut (simpul anak) ke dalam antrian. 5. Jika antrian kosong dan setiap simpul sudah dicek, pencarian selesai dan mengembalikan hasil solusi tidak ditemukan.

Hasil Penelitian

Kelebihan Penelitian

6. Ulangi pencarian dari langkah kedua. The results reveal that the conventional address mapping schemes of modern memory controllers do not efficiently exploit row buffers in DRAM. Thus, we propose a new scheme called per-row channel interleaving and improve the DRAM power efficiency by 30.3% compared to a conventional scheme for a certain simulator setting. (Hasilnya mengungkapkan bahwa skema pemetaan alamat konvensional dari pengontrol memori modern tidak secara efisien mengeksploitasi buffer baris dalam DRAM. Dengan demikian, kami mengusulkan skema baru yang disebut saluran per-baris interleaving dan meningkatkan efisiensi daya DRAM sebesar 30,3% dibandingkan dengan skema konvensional untuk pengaturan simulator tertentu) Maka dapat disimpulkan bahwa keunggulan Algoritma BFS adalah : 1. Tidak akan menemui jalan buntu. 2. Menjamin ditemukannya solusi (jika solusinya memang ada) dan solusi yang ditemukan pasti yang paling baik. 3. Jika ada satu solusi maka bread-first search akan menemukannya.