Tugas Kecil 3 Strategi Algoritma IF2211

Implementasi Algoritma A* untuk Menentukan Lintasan Terpendek

Daftar Isi

Kontributor
Penjelasan
Spesifikasi
Requirements
Cara Pengunaan
Alur Program
Contoh Visualisasi
Contoh Lintasan Terpendek
Laporan

Kontributor

Fabian Savero Diaz Pranoto (13519140)
Fadel Ananda Dotty (13519146)

Penjelasan

Algoritma A* (atau A star) dapat digunakan untuk menentukan lintasan terpendek dari suatu titik ke titik lain. Pada tugas kecil 3 ini, diminta menentukan lintasan terpendek berdasarakan peta Google Map jalan-jalan di kota Bandung. Dari ruas-ruas jalan di peta dibentuk graf. Simpul menyatakan persilangan jalan atau ujung jalan. Asumsikan jalan dapat dilalui dari dua arah. Bobot graf menyatakan jarak (m atau km) antar simpul. Jarak antar dua simpul dapat dihitung dari koordinat kedua simpul menggunakan rumus jarak Euclidean (berdasarkan koordinat) atau dapat menggunakan ruler di Google Map, atau cara lainnya yang disediakan oleh Google Map.

Spesifikasi

Program menerima input file graf (direpresentasikan sebagai matriks ketetanggaan berbobot), jumlah simpul minimal 8 buah.
Program dapat menampilkan peta melalui Google Maps.
Program menerima input simpul asal dan simpul tujuan.
Program dapat menampilkan lintasan terpendek beserta jaraknya antara simpul asal dan simpul tujuan.

Requirements

Flask

Cara Penggunaan

Sebaiknya menginstall flask pada virtual environment saja. Untuk membuat virtual environment sebagai berikut:

pip install virtualenv
python -m venv env

Untuk menyalakan virtual environment, dari directory utama proyek ini:

source env/Scripts/activate

Setelah itu baru dapat menginstall flask dengan command sebagai berikut:

pip install flask

Untuk menyalakan program, masukkan command sebagai berikut:

export FLASK_APP=src/main.py
flask run

Alur Program

Program akan meminta input file.

Masukkan filename:

Apabila input file sudah benar, akan memunculkan daftar node dan informasinya. Contoh:

Daftar Node: 
Name: Jl. Ahmad Yani
Latitude: -6.990485
Longitude: 110.423839
Neighbours: Jl. Pahlawan, Simpang Lima

Name: Jl. Pahlawan
Latitude: -6.997269
Longitude: 110.419265
Neighbours: Jl. Ahmad Yani, Jl. Imam Barjo, Jl. Veteran, Simpang Lima

Name: Jl. Imam Barjo
Latitude: -6.993382
Longitude: 110.42167
Neighbours: Jl. Pahlawan, Jl. Mentri Supeno

Name: Jl. Veteran
Latitude: -6.995821
Longitude: 110.414089
Neighbours: Jl. Pahlawan, Jl. Dokter Kariadi

Name: Jl. Dokter Kariadi
Latitude: -6.993414
Longitude: 110.413746
Neighbours: Jl. Veteran, Jl. Mentri Supeno

Name: Jl. Mentri Supeno
Latitude: -6.993265
Longitude: 110.419242
Neighbours: Jl. Imam Barjo, Jl. Dokter Kariadi, Jl. Pandanaran II

Name: Jl. Pandanaran II
Latitude: -6.991625
Longitude: 110.4201
Neighbours: Jl. Mentri Supeno, Jl. Pandanaran

Name: Jl. Pandanaran
Latitude: -6.988792
Longitude: 110.420099
Neighbours: Jl. Pandanaran, Simpang Lima

Name: Simpang Lima
Latitude: -6.989985
Longitude: 110.422203
Neighbours: Jl. Ahmad Yani, Jl. Pahlawan, Jl. Pandanaran

Flask akan berjalan pada http://127.0.0.1:5000/

* Running on http://127.0.0.1:5000/ (Press CTRL+C to quit)

Jalankan pada browser
Masukkan input lokasi awal dan tujuan

Masukkan rute lokasi yang ingin dicari:
Masukkan lokasi awal: Jl. Veteran
Masukkan lokasi tujuan: Simpang Lima

fabiansdp/TucilStima3