Matlamat kertas kerja ini adalah untuk mencari dan mengira jarak yang singkat
dari satu nod yang lain dengan cara yang paling berkesan. 3 algoritma (algoritma A *,
algoritma Dijkstra dan algoritma Greedy) dan 2 konsep (Pencarian Dua Arah dan
perancangan semula) akan diterokai dan simulasi. Penanda aras untuk perbandingan
keberkesanan setiap algoritma dengan teliti ditakrifkan dengan niat mencari algoritma
yang terbaik dalam persekitaran yang direka. Semua simulasi Matlab dilakukan dalam
2D, 300x300 piksel imej dengan hanya satu permulaan yang tetap dan nod akhir. Bagi
kaedah Dua Arah Mencari, ia ditetapkan untuk berhenti apabila kawasan pencarian dari
titik permulaan dan kawasan mencari titik akhir bertemu. Selain itu, bagi maksud simulasi
menggunakan konsep perancangan semula, peta asal akan dimasukkan dengan 4 dinding
dan 39 Ruang putih. Sebanyak 4 eksperimen akan dilakukan untuk membandingkan sama
ada 2 konsep digabungkan sebenarnya meningkatkan prestasi pencarian 3 algoritma itu,
iaitu Pencarian Satu Arah tanpa perancangan semula, Pencarian Satu Arah dengan
perancangan semula, Pencarian Dua Arah tanpa perancangan semula dan Pencarian Dua
Arah Mencari dengan perancangan semula. Setiap keputusan akan dimasukkan dengan
perbincangan tentang persamaan dan perbezaan keputusan setiap algoritma. Secara
ringkasnya, jumlah Nod Dicari untuk Pencarian Dua Arah dengan perancangan semula
mempunyai pengurangan keseluruhan (28%, 37% dan 51%) berbanding jumlah Nod
Dicari untuk Pencarian Dua Arah tanpa perancangan semula. Di samping itu, jumlah
masa algoritma ditunjukkan mempunyai pengurangan sebanyak 73,69%, 64% dan 4.62%
berdasarkan simulasi peta kedua. Begitu juga jika dibandingkan antara Pencarian Dua
Arah dengan perancangan semula dan Pencarian Satu Arah dengan perancangan semula,
penurunan sebanyak 41.08%, 25.57% dan 14.41% ke atas jumlah masa algoritma dapat
dilihat. Oleh itu, dalam projek tahun akhir ini, algoritma optimum untuk digunakan adalah
A * algoritma dengan kaedah Cari dwiarah dan kaedah perancangan semula termasuk
semasa proses pencarian. Kod lengkap termasuk dalam Lampiran untuk tujuan
kebolehulangan.
_______________________________________________________________________________________________________
The main concern is to find and calculate the shortest distance from one node to
another in the most efficient way. 3 algorithms (A* algorithm, Dijkstra algorithm and
Greedy algorithm) and 2 concepts (Bidirectional Searching and Replanning) are explored
and simulated. The benchmark for comparing the effectiveness of each algorithm are
thoroughly defined with the intention of finding the best algorithm in the designed
environment. All Matlab simulations are done in a 2D, 300x300 image pixel with only a
fixed start and an end node. For the Bidirectional Searching method, it is set to stop when
the searching area from starting point and the searching area of end point are met. Next,
for the purposes of simulating using Replanning concept, the original map is introduced
with 4 walls and 39 whitespaces. A total of 4 experiments are done to compare whether
the 2 concepts combined do actually improve the searching performance of the 3
algorithms, namely, Unidirectional Searching without Replanning, Unidirectional
Searching with Replanning, Bidirectional Searching without Replanning and
Bidirectional Searching with Replanning. Each result of the simulations is included with
a discussion of the similarities and difference of the results of each algorithm. In summary,
the total Nodes Searched of Bidirectional Searching with Replanning has an overall
reduction (28%, 37% and 51%) when compared to total Nodes Searched of Bidirectional
Searching without Replanning. In addition, the algorithm total time is shown to have
decrement of 73.69%, 64% and 4.62% based on the second map simulations. Likewise,
when comparing between Bidirectional Searching with Replanning and Unidirectional
Searching with Replanning, a decrease of 41.08%, 25.57% and 14.41% on algorithm total
time can be seen. Thus, in this final year project, the optimum algorithm to use is A*
algorithm with Bidirectional Searching method and Replanning method included during
the searching process. The complete code is included in Appendix for reproducibility
purposes.
Simulation of path optimisation algorithms / Sim Choon Yee