Apakah teman-teman sudah pernah menggunakan Google Maps untuk mencari jalan? Misalkan kita hendak pergi ke Bekasi dari Serpong. Google Maps akan memberikan saran mengenai jalan paling cepat yang bisa kita tempuh, lengkap dengan perkiraan waktu tempuhnya. Selain itu Google Maps juga bisa memberikan beberapa alternatif jalan lainnya. Nah, dalam video ini, kita akan latihan mengenai cara mencari jalan yang paling cepat seperti Google Maps, dengan menggunakan pendekatan Object Oriented Programming.

Ini adalah contoh peta yang disederhanakan sebagai soal untuk latihan kali ini. Misalkan kita memiliki 6 buah titik, yaitu S sebagai titik start, dan G sebagai titik Goal atau tujuan. Dan diantaranya ada 4 buah titik A, B, C, D. Apabila dua buah titik terhubung dengan garis, artinya kita bisa berpindah dari titik yang satu ke titik yang lain, dan angka pada garis menunjukkan waktu yang diperlukan untuk berpindah. Misalkan dari titik S, kita bisa pindah ke A dalam waktu 2 satuan, dan kita bisa pindah ke B dalam waktu 3 satuan. Pada video ini kita akan menulis script untuk menentukan rute mana yang paling cepat untuk berpindah dari titik S ke titik G.

Algoritma yang akan kita gunakan adalah Depth First Search. Pertama kita mulai dari titik S. Lalu kita tentukan rute yang bisa kita tempuh dari S, yaitu titik A dengan waktu 2 dan titik B dengan waktu 3.

Kemudian kita pindah ke titik A. Kita tentukan lagi rute yang bisa kita tempuh dari titik A, yaitu titik C dengan waktu 6 dan titik D dengan waktu 5. Dari titik A bisa menuju titik S, namun tidak kita masukkan ke diagram karena kita sudah pernah melewati titik S.

Kita lanjutkan ke titik C. Kembali lagi kita tentukan rute yang bisa dijalani berikutnya yaitu titik B dan titik G.

Kita lanjutkan ke titik B. Dan dari titik B bisa dilanjutkan ke D. Dan kemudian kita berhasil menemukan titik G.

Kalau kita sudah mencapai titik G, artinya kita sudah mendapatkan rute yang bisa ditempuh, yaitu dari 'S' ke 'A', lalu ke 'C', 'B', 'D' dan 'G'. Waktu tempuhnya tinggal kita tambahkan di masing-masing perjalanan, yaitu 2 + 6 + 3 + 1 + 7, totalnya 19.

Berhubung kita sudah mencapai pencarian di titik paling bawah, maka kita lakukan backtracking ke D, lalu ke B, dan ke C. Berhubung titik C memiliki rute alternatif yang belum diperiksa, maka kita lanjutkan pencarian ke G.

Dan sekali lagi disini kita mencapai titik G. Dengan rute yang ditempuh 'SACG', dan total waktu yang diperlukan 9.

Selanjutnya kita lakukan backtracking ke C. Lalu ke A. Dan kita periksa lagi alur alternatif D.

Disini kita tambahkan rute yang bisa kita lalui dari titik D, yaitu 'B' dan 'G'.

Dari sini teman-teman sudah terbayang ya alur kerja dari Depth First Search. Kalau pencarian ini dilanjutkan hingga memeriksa semua titik, maka kita akan mendapatkan semua rute yang bisa kita lalui untuk mencapai titik 'G'. Nantinya kita tinggal memiliki rute dengan waktu yang paling kecil.

Sebelum kita lanjutkan ke penulisan script, kita mesti mengingat dahulu bahwa script terdiri dari 3 buah bagian besar ya. Yaitu input, proses dan output. Tadi barusan kita bahas bahwa proses yang akan kita tulis adalah algoritma Depth First Search. Sedangkan outputnya akan mengembalikan 2 buah nilai, yaitu titik-titik mana yang perlu kita lewati untuk berpindah dari S ke G. Semua titik ini kita tuliskan dalam satu buah string. Nilai kedua yang dikembalikan adalah jumlah waktu yang diperlukan untuk menempuh jarak tersebut. Berhubung kita mengembalikan dua buah nilai sekaligus, maka kita menggunakan tipe data array.

Nah, yang menjadi masalah disini adalah bagian input. Karena inputnya berupa peta seperti ini. Kita harus mengubah petanya menjadi tipe data yang bisa dimengerti oleh script, dan bisa dengan mudah kita gunakan pada proses. Untungnya tipe data array pada PHP sangat flexible, sehingga cocok untuk kita gunakan disini.

Sebagai contoh, kita lihat titik S. Dari S bisa menuju A dengan waktu 2 satuan, dan bisa menuju B dengan waktu 3 satuan. Kita terjemahkan menjadi variable S yang menampung array dengan index 'A' dan nilai 2, kemudian ada index 'B' dengan nilai 3. Nama variable s adalah titik awalnya, yaitu S. Sedangkan index 'A' adalah titik yang bisa dituju A, dengan nilai 2. Kemudian ada lagi index 'B' dengan nilai 3.

Kita lihat contoh lain ya. Dari titik A, kita bisa menuju ke titik S, C dan D. Maka peta ini kita terjemahkan menjadi variable $a, yang menyimpan array dengan index 'S' nilai 2, kemudian index 'C' nilai 6 dan index 'D' nilai 5.

Berhubung kita memiliki 6 buah titik. Daripada setiap titik disimpan dalam satu variable, lebih baik semua titik kita simpan dalam satu array. Jadinya array 2 dimensi. $map['S'] merepresentasikan variable $s yang kita bahas sebelumnya. Kemudian $map['A'] merepresentasikan variable $a yang barusan kita bahas. Dan index lainnya menunjukkan titik-titik lainnya.

Ini adalah source code awal dari latihan kita. Kita memiliki array $map yang menggambarkan titik-titik pada peta dan rute tempuhnya. Yang perlu kita tulis disini adalah kode untuk kelas RouteFinder. Pada constructor kita memasukkan peta yang hendak dijelajahi. Kemudian kita membuat method findFastestRoute untuk mencari rute tercepat untuk berpindah dari titik 'S' ke 'G'.

Algoritma yang digunakan adalah Depth First Search, yang sudah pernah kita bahas pada video Permutasi. Bagi teman-teman yang lupa, bisa membuka kembali videonya untuk belajar cara menuliskan kodenya menggunakan recursive. Kali ini kita akan menuliskan kembali algoritma tersebut, namun menggunakan pendekatan Object Oriented Programming. Pause terlebih dahulu video ini dan coba kerjakan pada komputer masing-masing. Kita akan kembali untuk membahas solusi dari masalah ini.

Kita coba praktek coding ya. Disini sudah ada file RouteFinder.php, yang didalamnya ada kelas RouteFinder. Pertama kita buat dahulu constructornya ya. public function __construct. Dengan parameter yang menggunakan fitur promotion, private array $map. Isi functionnya kosong saja. Namun dengan menggunakan promotion, artinya kita sudah mengangkat parameter $map menjadi property.

Kemudian kita buat public function findFastestRoute dengan parameter string $source dan string $destination. Di dalamnya kita coba saja var_dump nilai dari property $this->map. Setelah itu kita return. Kita coba jalankan. Dan kode sudah berjalan dengan benar ya.

Selanjutnya kita buat function search yang akan melakukan Depth First Search secara rekursif. Berhubung cara penggunaan function ini rumit, lebih baik kita buat dalam bentuk private, jadi hanya kita sendiri yang menggunakan function tersebut. Parameter yang dibutuhkan adalah string $currentPosition untuk menampung titik posisi sekarang, int $currentTime untuk menampung waktu yang diperlukan untuk berpindah ke posisi sekarang, string $route untuk mencatat rute perjalanan yang telah ditempuh oleh depth first search, dan int $totalTime untuk menyimpan total waktu yang diperlukan untuk menempuh perjalanan. Function mengembalikan hasil void. Kita beri nilai default pada $currentTime = 0, kemudian $route = '', dan $totalTime = 0.

Agar function search dapat berfungsi dengan baik, kita perlu 2 buah property. Kita tambahkan dahulu pada kelasnya. Yang pertama adalah private string $destination untuk menyimpan titik tujuan. Dan yang kedua adalah private array $result untuk menyimpan hasil pencarian.

Kita kembali ke function findFastestRoute. Pertama kita inisialisasi dahulu nilai property yang diperlukan. Kita simpan nilai parameter $destination ke dalam property $this->destination. Kemudian kita inisialisasi nilai property $this->result menjadi array kosong. Kemudian kita panggil method search dengan argument $source. Setelah itu kita var_dump nilai dari property $result.

Kita lanjutkan untuk mengisi method search. Method ini akan kita panggil secara rekursif ya. Pertama kita lakukan dahulu perhitungan yang diperlukan di dalam method. Kita tambahkan $route dengan $currentPosition. Kemudian kita tambahkan nilai $totalTime dengan $currentTime.

Nah, kemudian ingat ya di dalam recursive, apa lagi yang paling penting? Yang paling pentingnya adalah base condition. Yaitu kondisi dimana kita keluar dari recursive. Kalau tidak ada base condition, bisa-bisa nantinya function kita dijalankan secara berulang-ulang tanpa henti.

Base condition dari fungsi ini adalah apabila kita telah berhasil mencapai tujuan. Jadi kondisinya adalah $currentPosition === $this->destination. Apa yang mesti kita lakukan kalau sudah mencapai tujuan? Kita harus mencatat hasilnya ke dalam property $result. Berhubung $result berbentuk array, maka untuk menambahkan hasil di bagian akhir array, kita panggil function array_push. Argument pertama adalah $this->result. Sedangkan argument kedua adalah array yang isinya variable $route dan $totalTime. Jadi index ke 0 adalah rutenya, sedangkan index ke-1 adalah waktunya. Setelah push kita return ya.

Selanjutnya kita mencari rute mana saja yang bisa kita lalui, agar kita bisa memanggil kembali function search secara recursive. Ingat ya, rute disimpan dalam property $this->map dalam bentuk array 2 dimensi. Untuk mengambil rute apa saja yang bisa dilalui oleh titik $currentPosition, kita bisa menggunakan sintaks foreach, dengan argument $this->map[$currentPosition]. Kemudian kita ikuti dengan kata kunci as dan variable $position => $time. $position akan mengandung nilai titik berikutnya yang bisa kita kunjungi, sedangkan $time adalah waktu yang diperlukan.

Dari sini kita bisa memanggil search untuk iterasi berikutnya, dengan argument $position, $time, $route dan $totalTime. Namun perlu diingat lagi ya, kita hanya boleh memeriksa rute yang belum pernah kita kunjungi. Artinya nilai dari $position masih belum ada di dalam $route.

Kita tambahkan dahulu if. Kemudian untuk memeriksa hal ini, maka kita bisa menggunakan function str_contains($route, $position). Fungsi ini mengembalikan nilai true apabila $position sudah ada di dalam $route. Sedangkan yang kita perlukan adalah $position yang belum ada di dalam $route. Oleh karena itu kita tambahkan simbol ! di depan function untuk menggunakan hasil kebalikannya.

Kita simpan dan coba jalankan. Kita mendapatkan hasil array yang isinya ada 8 ya. Artinya ada 8 rute untuk berpindah dari 'S' ke 'G'. Kita lihat rute pertama adalah 'SACBDG' dengan nilai 19. Sesuai dengan slide tadi ya. Sedangkan rute kedua adalah 'SACG' dengan nilai 9, sesuai dengan slide juga.

Selanjutnya kita mesti mengganti var_dump($this->result) menjadi rute dengan waktu yang paling kecil saja. Kita ganti kodenya menjadi return $this->getFastestRoute(). Lalu kita buat fungsi barunya, private function getFastestRoute(): array.

Di dalam method ini kita akan mengambil nilai dari array property $this->result dengan nilai waktu yang paling kecil. Pada awal method kita lalukan validasi terlebih dahulu agar method tidak error. Apabila count($this->result) === 0, maka kita kembalikan ['', 0].

Lalu kita inisialisasi nilai awal dari rute dan waktu. Ingat lagi ya, $this->result adalah array 2 dimensi. Pada dimensi kedua, kita menyimpan nilai rute pada index 0 dan nilai waktu pada index 1. Kita ambil dahulu nilai rute dan waktu dari array pertama.

    $route = $this->result[0][0];
    $time = $this->result[0][1];

Kemudian kita panggil foreach($this->result as row). Kita bandingkan apakah waktu pada row lebih kecil dari nilai variable $time. Apabila iya, maka kita ganti nilai $route dan $time dengan nilai dari row.

Dan pada bagian akhir function, kita kembalikan nilai $route dan $time dalam bentuk array. Kemudian pada method findFastestRoute bisa kita tambahkan pengembalian nilainya dalam bentuk array. Kita simpan dan jalankan. Sekarang kita hanya mendapatkan satu buah array ya. Rute tercepat adalah SBCG dengan nilai total waktunya 7.

Sebenarnya sampai disini latihan kita sudah selesai. Namun agar kode dalam kelas kita bisa berjalan lebih bagus, kita tambahkan validasi lagi ya. Alasan utamanya adalah karena method search ini ditulis secara recursive. Kita harus memastikan argument-nya jangan menyebabkan error yang menyebabkan perulangan tanpa henti.

Pertama kita harus periksa dahulu apakah nilai parameter $source adalah benar. Nilai dari $source ini harus ada di salah satu index dari array $map. Harus salah satu dari huruf 'S', 'G', atau 'A', 'B', 'C', D'. Kita harus menghasilkan error apabila $source diisi dengan huruf lain, misalkan 'Z'.

Kita kembali ke method findFastestRoute. Pada bagian paling awal function, kita tambahkan validasi

    if(!$this->isValidSource($source)){
      echo 'Source tidak valid' . PHP_EOL;
      die;
    }

Die berarti kita langsung menghentikan eksekusi kode. Semua kode yang berada setelah die sudah tidak dijalankan lagi untuk mencegah error yang berkelanjutan.

Kemudian kita tambahkan private function isValidSource dengan parameter string $source dan hasil bool. Di dalamnya kita return !empty($this->map[$source]). Artinya kita periksa apakah array map dengan index $source, apakah tidak kosong? Kalau tidak kosong maka kita kembalikan nilai true, alias tidak error ya.

Kita coba jalankan. Saat ini tidak error ya. Namun kalau kita ganti argument pertama menjadi huruf 'Z', maka keluar error 'Source tidak valid'.

Kemudian kita mesti memeriksa nilai dari $destination. Disini lebih sulit dibandingkan source. Karena kalau kita lihat dari isi array $map. Yang mesti kita periksa adalah index dari array pada dimensi yang kedua ini. Jadi kita mesti loop dahulu ke semua isi array dimensi pertama. Lalu kita periksa apabila ada $destination di salah satu index array dimensi kedua, maka kita kembalikan nilai true. Apabila tidak ada sama sekali, maka kita kembalikan nilai false.

Kita copy paste function isValidSource ya. Namun kita ganti namanya menjadi isValidDestination, dan parameternya menjadi $destination. Di dalamnya kita lakukan dahulu perulangan foreach($this->map as $position). Kemudian kita periksa apabila !empty($position[$destination]), maka kita kembalikan nilai true. Di luar loop kita kembalikan nilai false.

Kemudian kita kembali ke method findFastestRoute. Kita tambahkan lagi validasi untuk destination.

    if(!$this->isValidDestination($destination)){
      echo 'Destination tidak valid' . PHP_EOL;
      die;
    }

Kita simpan dan coba jalankan. Tidak error ya. Namun kalau kita ganti destinasi menjadi huruf 'Z', maka keluar error Destination tidak valid.

Script kita sudah kelar sepenuhnya. Selain untuk mencari jalan dari 'S' ke 'G', kelas ini juga bisa digunakan untuk mencari jalan dari titik lain. Misalkan dari 'A' ke 'B'. Terus terang materi algoritma yang digunakan disini memang lebih sulit ya, karena kita banyak menggunakan array 2 dimensi. Jadi teman-teman mesti mengerti betul mengenai bagaimana kita mengatur struktur dari data kita. Nantinya teman-teman bisa explore lagi bagaimana cara kita mengakses array, dan dibandingkan lagi dengan bagaimana struktur dari data array-nya agar benar-benar bisa mengerti mengenai kode yang kita tulis dalam video ini. Apabila ada bagian yang kurang mengerti, bisa ulangi videonya atau bisa bertanya ke saya.

Dengan menggunakan fasilitas tanya jawab, maka Anda bisa bertanya dan akan dijawab langsung oleh instruktur kursus.

Anda belum terdaftar pada kursus ini sehingga tidak bisa mengajukan pertanyaan.