Terakreditasi Nomor 204/E/KPT/2022 | Vol. 4, No. 2, Juni  (2023), pp. 154-163

## Algoritma General and Test Menggunakan Metode Depth First

## Search Dalam Penentuan Jalur Rute Terpendek
Weni Lestari Putri 1 , Nanda Jarti 2
1 Fakultas Teknik, Universitas Ibnu Sina, Tiban Lama Kepuluan Riau, Indonesia
2 Fakultas Teknik, Universitas Ibnu Sina, Batu Aji  Kepuluan Riau, Indonesia E-mail: weni@uis.ac.id 1 , nandaluthan@gmail.com 2

## Abstract
General  and  Test  is  a  branch  of  knowledge  that  is  included  in  the  field  of  artificial intelligence. Success in using the system is the basic goal of artificial intelligence itself. General and test works in solving problems and finding the best solution which is used as a reference in determining the path to find the smallest value so that you can quickly go to  the  place  to  be  visited  and  can  save  time  and  money  while  traveling  to  the  location. General  and  test  has the  concept  of looking for  the  smallest  alternative  path  by  how  to find  all  the  path  values  to  be  visited,  after  being  processed  as  a  whole  for  each  path, alternative starling values will be obtained which can be used as directions. The way the General  and  test  method  works  is  to  combine  Depth  First  Search  with  a  backracking system. All solutions must be discussed in full prior to testing. The procedure for working with  this  method  must  be  carried  out  systematically  in  order  to  get  a  good  solution. General  and  test  has  a  working  principle  (1).  Generate  possible  solutions  (2).  Test whether  the  solution  is  correct  according  to  the  required  criteria.  (3).  If  a  solution  has been found then exit, but if it has not been found then the next step is to repeat the steps until you find the highest result that can be used as a reference in finding the path with the  least  or  shortest  distance.  The  problem  in  this  study  is  the  lack  of  information  in passing the smallest path because there are many paths that must be chosen to get to the destination.  The  benefit  of this  research is  to  help  the  user  in  providing  information  on the path to be passed so as to save time and costs. Alternative results are obtained that can  be  used  as  a  solution,  namely  the  A-B-G-J-M-T line  =  23+15+5+11=54  KM.  This discussion can be used as a reference by traders in finding the shortest alternative so as to save travel costs and time
Keywords: Artificial  Intelligence;  Searching,  General  and  Test,  Best  First  search method. Final Solution

## Abstrak
General  and  Test  merupakan  cabang    ilmu  yang  termasuk  kedalam  bidang  ilmu kecerdasan  buatan.  Keberhasilan  dalam  penggunaan  system  merupakan  tujuan  dasar dari  kecerdasan  buatan  itu  sendiri.  General  and  test  bekerja  dalam  menyelesaikan permasalahan  dan  mencari  solusi  terbaik  yang  dijadikan  acuan  dalam  penentuan  jalur untuk  mencari  nilai  terkecil  sehingga  cepat  menuju  tempat  yang  akan  dikunjungi  serta mampu  menghemat  waktu dan  biaya  dalam  saat perjalanan  menuju lokasi.General  and test  mempunyai  konsep  mencari  jalur  alternatif  terkecil  dengan  cara  mencari  semuan nilai  jalur  yang  akan  dikunjungi,  setelah  diproses  secara  keseluruhan  masing  masing jalur maka akan diperoleh alternatif alternatif nilai jalak yang mampu dijadikan sebagai petunjuk  arah.Cara  kerja  metode  General  and  test  ini  yaitu  menggabungkan    antara Depth First Search dengan system pelacakan mundur (backracking) semua solusi harus dibahas secara lengka sebelum dilakukan pengujian/ test.  Prosedur pengerjaan metode ini  harus  dilakukan  secara  sistematis  agar  mendapatkan  solusi  yang  baik.  General  and test  memiliki  prinsip  kerja  (1).    Bangkitkan  kemukinan  solusi    (2).  Uji  apakah    solusi tersebut  apakah solusi tersebut benar sesuai dengan  kriteria yang dibutuhkan. (3).  Jika solusi  sudah  ditemukan  maka  keluar,  namun  jika  belum  ditemukan  maka  Langkah

## BRAHMANA: Jurnal Penerapan Kecerdasan Buatan
Terakreditasi Nomor 204/E/KPT/2022 | Vol. 4, No. 2, Juni  (2023), pp. 154-163
selanjutnya  yaitu  ulangi  Langkah  sampai  menemukan  hasil  ternaik  yang  bisa  dijadikan acuan  dalam  mencari  jalur  yang  jarak  nya  paling  sedikit  atau  pendek.  Masalah  pada penelitian  ini  yaitu  kurangnya  informasi  dalam  melewati  jalur  terkecil  karena  banyak jalur  yang  harus  dipilih  untuk  sampai  ke  tempat  tujuan.  Manfaat  penelitian  ini  yaitu mambantu user dalam memberikan informasi jalur yang akan dilewati sehingga mampu menghemat  wajtu,  biaya.  Diperoleh  hasil  hasil  alternatif  yang  dapat  dijadikan  solusi yaitu  jalur  A-B-G-J-M-T=  23+15+5+11=54  KM.  Dengan  pembahasan  ini  dapat dijadikan  acuan  oleh  pedagang  dalam  mencari  alternatif  terpendek  sehingga  mampu menghemat biaya perjalanan dan waktu
Kata  Kunci: Kecerdasan  Buatan;  Searching,  General  and  Test,  Metode  Best  First search. Solusi Akhir

## 1. Pendahuluan
Artificial  Intelligence atau  AI  merupakan  salah  satu  teknologi  yang  sedang  populer saat  ini.  Berbagai  bidang  industri  sudah  memanfaatkan  teknologi  tersebut,  mulai  dari kesehatan,  keuangan,  dan  lain-  lain.  Menurut  John  Mc  Carthy,  1956,  Artificial Intelligence  adalah  untuk  mengetahui  dan  memodelkan  proses–proses  berpikir  manusia dan  mendesain  mesin  agar  dapat  menirukan  perilaku  manusia.  Cerdas,  berarti  memiliki pengetahuan  ditambah  pengalaman,  penalaran  (bagaimana  membuat  keputusan  dan mengambil tindakan), moral yang baik [1]. Tujuan dari AI untuk memecahkan persoalan dunia  nyata  (bersifat  praktis)  dan  memahami  intelijensia  (bersifat  memahami).  AI merupakan  salah  satu  bagian  ilmu  komputer  yang  mempelajari  tentang  bagaimana  cara membuat  agar  komputer  dapat  melakukan  pekerjaan  seperti  yang  dilakukan  oleh manusia.  Pada awal diciptakannya, komputer hanya difungsikan sebagai alat hitung saja. Namun  seiring  dengan  perkembangan  zaman,  maka  peran  komputer  semakin mendominasi  kehidupan  umat  manusia.  Komputer  tidak  lagi  hanya  digunakan  sebagai alat  hitung,  lebih  dari  itu,  komputer  diharapkan  untuk  dapat  diberdayakan  untuk mengerjakan  segala  sesuatu  yang  bisa  dikerjakan  oleh  manusia.  Manusia  bisa  menjadi pandai  dalam  menyelesaikan  segala  permasalahan  di  dunia  ini  karena  manusia mempunyai  pengetahuan  dan  pengalaman.  Pengetahuan  diperoleh  dari  belajar. Semakin banyak bekal pengetahuan yang dimiliki oleh seseorang tentu saja diharapkan akan lebih mampu dalam menyelesaikan permasalahan. Namun bekal pengetahuan saja tidak cukup, manusia juga diberi akal untuk melakukan penalaran, mengambil kesimpulan berdasarkan pengetahuan  dan pengalaman yang  mereka  miliki. Tanpa  memiliki kemampuan menalar yang  baik,  manusia  dengan  segudang  pengalaman  dan  pengetahuan  tidak  akan  dapat menyelesaikan  masalah  dengan  baik.  Demikian  pula,  dengan  kemampuan  menalar  yang sangat  baik,  namun  tanpa  bekal  pengetahuan  dan  pengalaman  yang  memadai,  manusia juga tidak akan bisa menyelesaikan masalah dengan baik [2].
Perkembangan  teknologi  dewasa  ini  khususnya  internet  berkembang  sangat  pesat. Hal      ini     diiringi     juga     dengan     semakin berkembangnya Teknologi  Informasi yang  dibutuhkan  oleh  pengguna  sehingga  mengakibatkan  munculnya  suatu  cabang  ilmu baru    dalam    teknologi    informasi,    yaitu  pencarian  informasi  ( information  retrieval ). Sejalan  dengan  perkembangan  teknologi,  maka  perkembangan  peralatan  juga  ikut mengambil andil yang besar untuk mendukung perkembangan pertukaran informasi yang semakin  hari  semakin  canggih.  Hampir  semua  kecanggihan  teknologi  yang  memberikan kemudahan    kepada user dalam    menemukan  apa  yang  diinginkannya.  Salah  satu kemudahan yang diberikan adalah menyediakan fasilitas searching yang digunakan untuk memberikan  kemudahan  mendapatkan  lebih  banyak  informasi  yang  berbentuk  dokumen kebutuhan menjadi sangat penting dengan semakin mudahnya memperoleh informasi dari seluruh   dunia   sebagai   akibat   perkembangan teknologi informasi dan komunikasi yang semakin  pesat.  Oleh  karena  itu,  teknik  untuk  memperoleh  dokumen  dengan  isi  yang sesuai  dengan  kebutuhan  informasi  sangat  diperlukan  [3]. Kecerdasan  buatan  dapat
Terakreditasi Nomor 204/E/KPT/2022 | Vol. 4, No. 2, Juni  (2023), pp. 154-163
menjadi  pelengkap  dari  para  manusia  untuk  dapat  mengurangi  tingkat  pengambilan keputusan yang berdasarkan keyakinan pribadi[4].
DFS  singkatan  dari Depth  First Search algoritma  pencarian  pada  sebuah  pohon  atau tree .  Pencarian  DFS  ini adalah dengan  menelusuri  satu cabang  sebuah pohon  sampai  ke bawah  (menemukan  solusi)  sebelum  melakukan backtracking .  Ilustrasi  pencarian dengan DFS seperti ditunjukkan gambar 2.1, pencarian dimulai dari  akar  (level  0)  dan pencarian dilanjutkan dengan melacak node yang berada paling kiri[5].
Gambar 1. Depth First Searching
Dalam  metode  pencarian  terbagi  menjadi  dua  jenis  yaitu  pencarian  buta  ( blind search )  dan heuristic  search. Pada  pencarian  buta  terbagi  menjadi  dua  macam  yaitu pencarian  BFS  dan  DFS.  Pada  dasarnya,  ada  dua  teknik  pencarian  dan  pelacakan  yaitu [6]: 1.  Pencarian buta ( blind search ), terdiri atas:
a. Pencarian melebar pertama ( Breadth First Search );
b. Pencarian mendalam pertama ( Depth First Search ).
2. Pencarian terbimbing ( heuristic search ).
Ada 4 hal yang harus diperhatikan menurut [7] diantaranya[7]: a. Membuat sebuah defenisi dengan tepat dan jelas;
b. Menganaisis bentuk permasalahan;
c. Mampu mempresentasikan permasalahan menggunakan konsep knowledge ;
d. Menyeleksi teknik penyelesaian masalah menggunakan teknik terbaik.
Algoritma  Depth  First  Search (DFS) Pencarian  dilakukan  pada  satu node dalam setiap  level  dari  yang  paling  kiri  dan dilanjutkan pada node sebelah kanan. Jika solusi ditemukan  maka  tidak  diperlukan  proses backtracking yaitu  penelusuran  balik  untuk mendapatkan jalur  yang diinginkan. Pada metode DFS pemakaian memori tidak  banyak karena  hanya node-node pada  lintasan  yang  akktif  saja  yang  disimpan.  Selain  itu,  jika solusi  yang  dicari  berada  pada  level  yang  dalam  dan  paling  kiri,  maka  DFS  akan menemukannya  secara  cepat  [8].  Adapun  beberapa  penelitian  yang  terkait  adalah pencarian rute terpendek dengan  menggunakan algoritma depth  first,  breath  first dan hill  climbing  (study  comparative) yang  membahas  mengenai  pencarian  rute  dengan menerapkan  tiga  algoritma  di  dalamnya  untuk  mendapat  rute  terpendek  yang  efektif (Feddy dan angraini, 2010). Mobile robot navigation using Depth First Search algorithm yang  membahas  mengenai  pergerakan  robot  sangat  dipengaruhi  oleh  nilai  dari  sensor jarak,  pengenalan node pada track juga    dipengaruhi    oleh    sensor    jarak    dengan menerapkan  algoritma Depth  First  Search (Frederick  dkk). A  appraisal  paper  on Breadth-first  search,  Depth-first  search  and  Red  black  tree yang  membahas  mengenai penerapan  algoritma bread  first  search, Depth First Search dan red black tree [6] . Hasil  penelitian  yang  dipaparkan [9] memaparkan  bahwa Algoritma Depth  First Search (DFS) digunakan pada proses pencarian yang tersedia. Hasil penelitian ini adalah
Terakreditasi Nomor 204/E/KPT/2022 | Vol. 4, No. 2, Juni  (2023), pp. 154-163
dapat membantu pemain untuk mengasah otak pemain.  Hasil penelitian [10] Sistem yang dirancang  dapat  memberikan list tampilan  lokasi  bimbingan  belajar  yang  dekat  dengan user .  Sistem  akan  menampilkan  lokasi  bimbingan  belajar  pada maps .  Untuk mendukung  hal  tersebut,  maka  akan dikembangkan  penelitian  yang  berjudul  Rancang Bangun  Sistem  Pencarian  Lokasi  Bimbingan  Belajar  Area  Pontianak  Berbasis Web Menggunakan Metode Depth First Search (DFS).

## 2. Metodologi Penelitian
Untuk menyelesaian permasalahan dalam penyelesaian kasus pencarian rute terpendek dapat  dilakukan  secara  sistematis.  Untuk  mendapatkan  hasil  yang  baik  dilakakan  tahap demi tahap.Langkah langkah tersebut dapat dilihat pada gambar dibawah ini:
Gambar 2. Metodologi Penelitian
3. Hasil Dan Pembahasan

## 3.1. Analisa Data
Proses penyelesaian algoritma ini dilakukan dengan 3 tahap yaitu :
a. Bangkitkan  semua  kemungkinan  solusi.  Solusi  bisa  berpa  keadaan    (state). Sebuah jalur  dari suatu posisi awal  ke posisi tujuan.
b. Uji,  apakah  solusi  tersebut    merupakan  solusi  yang  bisa  diterima  sesuai  dengan kriteria yang sudah ditentutukan.
c. Jika solusi ditemukan, keluar dan jika tidak maka ulangi sampai solusi ditemukan. Dibawah  ini  merupakan  kasus Generate  and  Test ,  dimana  pada  gambar  diatas diketahui jumlah jalur terdiri dari 14 jalur untuk sampai ke kota yang akan dituju, yaitu A,B,C,D,E,F,G,H,I,J,K,L,M,T,  jarak  antar  kota  dapat  dilihat  pada  gambar  diatas.  Tanah panah  merupakan    tanda  jalur  yang  bisa  dilewati.  Seorang  pedagang  makanan  ingin mengunjungi  Kota  T,  rute  awak  pedagang  tersebut  dimulai  dari  kota  A.  Konsep  dasar pedagang yaitu bagaimana cara sampai di kota A ke kota T dengan  cepat serta mampu meminilisasi biaya dan waktu.
Gambar 3. Jalur Generate and test pada jalur
3.2. Proses Penyelesaian Metode Depth First Search Permasalahan pada kasus ini yaitu: Keadaan awal   = A
Goal = T
Kriteria yang digunakan untuk pedagang  dalam  menemukan solusi dalam pemilihan rute terpendek, proses penyelesaian menggunakan fungsi heuristic jarak sebagai petunjuk arah yang akan dituju.
A. Iterasi ke 1
Hitung  semua  solusi  menggunakan    algoritma Depth  First  Search (Solusi  awal jalur yang digunakan Jalur A-B A-B-J-T= 23+18+23=64KM Uji Kriteria yang sudah digunakan Karena  jalur  A-B-J-T adalah solusi pertama yang digunakan maka solusi yang digunakan Sementara f (A-B-J-T)= 64 km
B. Iterasi ke 2
Hitung  semua  solusi  menggunakan    algoritma Depth  First  Search (Solusi  awal jalur yang digunakan Jalur A-B A-B-G-J-T= 23+15+5+23=66KM Bangkitkan  semua  solusi    menggunakan    algoritma Depth  First  Search (  Solusi kedua jalur) A-B-G-J-T= f (23+15+5+23=66KM Uji  kriteria  yang  digunakan  A-B-G-J-T=  23+15+5+23=66KM  maka  masih menggunakan solusi pertma f (A-B-J-T)= 64 km
C. Iterasi ke 3
Hitung  semua  solusi  menggunakan    algoritma Depth  First  Search (Solusi  awal jalur yang digunakan Jalur A-B A-B-G-J-M-T=23+15+5+11+5=59KM Bangkitkan  semua  solusi    menggunakan    algoritma Depth  First  Search (  Solusi kedua jalur) f( A-B-G-J-M-T)=23+15+5+11=54KM
Terakreditasi Nomor 204/E/KPT/2022 | Vol. 4, No. 2, Juni  (2023), pp. 154-163

## D. Iterasi ke 4
Hitung  semua  solusi  menggunakan    algoritma Depth  First  Search (Solusi  awal jalur yang digunakan Jalur A-B A-B-G-K-M-T=23+15+9+4+5=56KM Bangkitkan  semua  solusi    menggunakan    algoritma Depth  First  Search (  Solusi kedua jalur) A-B-G-J-M-T=23+15+5+11=54KM
E. Iterasi ke 5
Hitung  semua  solusi  menggunakan    algoritma Depth  First  Search (Solusi  awal jalur yang digunakan Jalur A-B A-B-G-H-I-K-M-T=23+15+3+7+8+4+5=65 KM Bangkitkan  semua  solusi    menggunakan    algoritma Depth  First  Search (  Solusi kedua jalur) A-B-G-K-M-T=23+15+9+4+5=56KM
F. Iterasi ke 6 Hitung  semua  solusi  menggunakan    algoritma Depth  First  Search (Solusi  awal jalur yang digunakan Jalur A-B A-B-G-H-I-L-M-T=23+15+3+7+23+7+5=75KM Bangkitkan  semua  solusi    menggunakan    algoritma Depth  First  Search (  Solusi kedua jalur A-B-G-K-M-T=23+15+9+4+5=56KM
G. Iterasi ke 7
Hitung  semua  solusi  menggunakan    algoritma Depth  First  Search (Solusi  awal jalur yang digunakan Jalur A-B A-B-G-H-I-L-T=23+15+3+7+23+6=77KM Bangkitkan  semua  solusi    menggunakan    algoritma Depth  First  Search (  Solusi kedua jalur) A-B-G-K-M-T=23+15+9+4+5=56KM
H. Iterasi ke 8 Hitung  semua  solusi  menggunakan    algoritma Depth  First  Search (Solusi  awal jalur yang digunakan Jalur A-C 21+19+5+23=68KM Bangkitkan  semua  solusi    menggunakan    algoritma Depth  First  Search (  Solusi kedua jalur) A-B-G-J-M-T=23+15+5+11=54KM
I. Iterasi ke 9 Hitung  semua  solusi  menggunakan    algoritma Depth  First  Search (Solusi  awal jalur yang digunakan Jalur A-C A-C-G-J-M-T=21+19+9+4+5= 58 KM Bangkitkan  semua  solusi    menggunakan    algoritma Depth  First  Search (  Solusi kedua jalur A-B-G-K-M-T=23+15+9+4+5=56KM
J. Iterasi ke 10 Hitung  semua  solusi  menggunakan    algoritma Depth  First  Search (Solusi  awal jalur yang digunakan Jalur A-C A-C-G-K-M-T=21+19+9+4+5=58 KM Bangkitkan  semua  solusi    menggunakan    algoritma Depth  First  Search (  Solusi kedua jalur) A-B-G-K-M-T=23+15+9+4+5=56KM
K. Iterasi ke 11
Hitung  semua  solusi  menggunakan    algoritma Depth  First  Search (Solusi  awal jalur yang digunakan Jalur A-C
Terakreditasi Nomor 204/E/KPT/2022 | Vol. 4, No. 2, Juni  (2023), pp. 154-163
A-C-G-H-I-K-M-T=21+19+3+7+8+4+5=61 KM Bangkitkan  semua  solusi    menggunakan    algoritma Depth  First  Search (  Solusi kedua jalur) A-B-G-K-M-T=23+15+9+4+5=56KM
L. Iterasi ke 12
Hitung  semua  solusi  menggunakan    algoritma Depth  First  Search (Solusi  awal jalur yang digunakan Jalur A-C Bangkitkan  semua  solusi    menggunakan    algoritma Depth  First  Search (  Solusi kedua jalur) A-B-G-J-M-T=23+15+5+11=54KM
M. Iterasi ke 13
Hitung  semua  solusi  menggunakan    algoritma Depth  First  Search (Solusi  awal jalur yang digunakan Jalur A-C A-C-G-H-I-L-T=21+19+3+7+23+6=79 KM Bangkitkan  semua  solusi    menggunakan    algoritma Depth  First  Search (  Solusi kedua jalur) A-B-G-K-M-T=23+15+9+4+5=56KM
N. Iterasi ke 14
Hitung  semua  solusi  menggunakan    algoritma Depth  First  Search (Solusi  awal jalur yang digunakan Jalur A-D A-D-H-I-K-M-T=27+11+7+8+4+5=64KM Bangkitkan  semua  solusi    menggunakan    algoritma Depth  First  Search (  Solusi kedua jalur) A-B-G-K-M-T=23+15+9+4+5=56KM
O. Iterasi ke 15
Hitung  semua  solusi  menggunakan    algoritma Depth  First  Search (Solusi  awal jalur yang digunakan Jalur A-D A-D-H-I-L-M-T=27+11+7+23+7+5=80 KM Bangkitkan  semua  solusi    menggunakan    algoritma Depth  First  Search (  Solusi kedua jalur) A-B-G-K-M-T=23+15+9+4+5=56KM
P. Iterasi ke 16
Hitung  semua  solusi  menggunakan    algoritma Depth  First  Search (Solusi  awal jalur yang digunakan Jalur A-D A-D-H-I-L-T=27+11+7+23+6=74 KM Bangkitkan  semua  solusi    menggunakan    algoritma Depth  First  Search (  Solusi kedua jalur) A-B-G-J-M-T=23+15+5+11=54KM
Q. Iterasi ke 17 Hitung  semua  solusi  menggunakan    algoritma Depth  First  Search (Solusi  awal jalur yang digunakan Jalur A-E A-E-H-I-K-M-T=29+13+7+8+4+5=66 KM Bangkitkan  semua  solusi    menggunakan    algoritma Depth  First  Search (  Solusi kedua jalur) A-B-G-K-M-T=23+15+9+4+5=56KM
R. Iterasi ke 18 Hitung  semua  solusi  menggunakan    algoritma Depth  First  Search (Solusi  awal jalur yang digunakan Jalur A-E A-E-H-I-L-M-T=29+13+7+7+5=61 KM Bangkitkan  semua  solusi    menggunakan    algoritma Depth  First  Search (  Solusi kedua jalur) A-B-G-K-M-T=23+15+9+4+5=56KM

## S. Iterasi ke 19
Hitung  semua  solusi  menggunakan    algoritma Depth  First  Search (Solusi  awal jalur yang digunakan Jalur A-E A-E-H-I-L-T=29+13+7+27+6=82 KM Bangkitkan  semua  solusi    menggunakan    algoritma Depth  First  Search (  Solusi kedua jalur) A-B-G-K-M-T=23+15+9+4+5=56KM
T. Iterasi ke 20
Hitung  semua  solusi  menggunakan    algoritma Depth  First  Search (Solusi  awal jalur yang digunakan Jalur A-F A-F-I-K-M-T=24+16+8+4+5=57 KM Bangkitkan  semua  solusi    menggunakan    algoritma Depth  First  Search (  Solusi kedua jalur) A-B-G-K-M-T=23+15+9+4+5=56KM
U. Iterasi ke 21
Hitung  semua  solusi  menggunakan    algoritma Depth  First  Search (Solusi  awal jalur yang digunakan Jalur A-F A-F-I-L-M-T=24+16+23+7+5=75 KM Bangkitkan  semua  solusi    menggunakan    algoritma Depth  First  Search (  Solusi kedua jalur) A-B-G-K-M-T=23+15+9+4+5=56KM
V. Iterasi ke 22
Hitung  semua  solusi  menggunakan    algoritma Depth  First  Search (Solusi  awal jalur yang digunakan Jalur A-F Bangkitkan  semua  solusi    menggunakan    algoritma Depth  First  Search (  Solusi kedua jalur) A-B-G-K- A-F-I-L-T=24+16+23+6= 69 KM
W. Iterasi ke 23
Hitung  semua  solusi  menggunakan    algoritma Depth  First  Search (Solusi  awal jalur yang digunakan Jalur A-F A-F-T=24+32=56 Bangkitkan  semua  solusi    menggunakan    algoritma Depth  First  Search (  Solusi kedua jalur) A-B-G-K-M-T=23+15+9+4+5=56KM

## 3.3. Alternatif Rute
Dibawah  ini  merupakan  tabel  hasil  rute  perjalanan  pedagang  yang  bisa  dijadikan sebagai rute alternatif yang dipilih sebagai panduan dalam mencari solusi.
Tabel 1. Jalur Rute Jalur Rute Nilai Jalur Alternatif Rute 1 A-B-J-T 23+18+23= 64KM 64 KM 2 A-B-G-J-T 23+15+5+23=66KM 64 KM 3 A-B-G-J-M-T 23+15+5+11=54KM 59KM 4 A-B-G-K-M-T 23+15+9+4+5=56KM 64 KM 5 A-B-G-H-I-K-M-T 23+15+3+7+8+4+5=65 KM 64 KM 6 A-B-G-H-I-L-M-T 23+15+3+7+23+7+5=75KM 54 KM 7 A-B-G-H-I-L-T 23+15+3+7+23+6=77KM 56 KM 8 A-C--J-T 21+19+5+23=68KM 56 KM 9 A-C-G-J-M-T 21+19+9+4+5= 58 KM 56 KM 10 A-C-G-K-M-T 21+19+9+4+5=58 KM 56 KM 11 A-C-G-H-I-K-M-T 21+19+3+7+8+4+5=61 KM 56 KM 12 A-C-G-H-I-L-M-T 21+19+3+7+23+7+5=75 KM 56 KM
Jalur Rute Nilai Jalur Alternatif Rute 13 A-C-G-H-I-L-T 21+19+3+7+23+6=79 KM 56 KM 14 A-D-H-I-K-M-T 27+11+7+8+4+5=64KM 56 KM 15 A-D-H-I-L-M-T 27+11+7+23+7+5=80 KM 56 KM 16 A-D-H-I-L-T 27+11+7+23+6=74 KM 56 KM 17 A-E-H-I-K-M-T 29+13+7+8+4+5=66 KM 56 KM 18 A-E-H-I-L-M-T 29+13+7+7+5=61 KM 56 KM 19 A-E-H-I-L-T 29+13+7+27+6=82 KM 56 KM 20 A-F-I-K-M-T 24+16+8+4+5=57 KM 56 KM 21 A-F-I-L-M-T 24+16+23+7+5=75 KM 56 KM 22 A-B-G-J-M-T 23+15+5+11=54KM 56 KM 23 A-F-T 24+32=56 56 KM
Dari  keseluruhan  rute  yang  di  proses  terdapat  23  rute  untuk  menuju  jalur  T.  Untuk melihat  alternatif  masing  masing  nilai  bisa  dibuat  pembagian  nilai  rute  dengan memisahkan jarak antar masing masing rute yang dapat pada Tabel 2 ini:
Tabel 2. Proses Alternatif rute Jalur  Rute Nilai Jalur 1 A-B 7 Jalur 2 A-C 6 Jalur 3 A-D 3 Jalur 4 A-E 3 Jalur
Hasil  Jalur  rute  yang  bisa  dijadikan  sebagai  alternatif  dapat  dilihat  pada  Gambar  4 berikut ini:
Gambar 4. Rute Perjalanan
Dari  hasil  di  dapat  disimpulkan  bahwa  hasil  alternatif  yang  dapat  dijadikan  solusi yaitu  jalur  A-B-G-J-M-T=  23+15+5+11=54  KM.  Sehingga  pedagang  bisa  mengambil alternatif  nilai  54  KM  jarak  yang  harus  ditempuh  untuk  menghemat  waktu  dan  biaya perjalanan yang sangat membantu pedagang dalam menemukan solusi terbaik.
Terakreditasi Nomor 204/E/KPT/2022 | Vol. 4, No. 2, Juni  (2023), pp. 154-163

## 4. Kesimpulan
Berdasarkan  hasil  pencarian  Rute  terpendek  menggunakan  konsep  Generate  and  test serta algoritma Depth First Search maka dapat disimpulkan bahwa pada kasus penelitian ini terdapat 14 jalur untuk sampai ke kota yang akan dituju, yaitu Rute Kota A, B, C, D, E,  F,  G,  H,  I,  J,  K,  L,  M,  T.  Untuk  memperoleh  alternatif  dibutuhkan  perhitungan menggunakan  algoritma Depth  First  Search dengan  cara  mencari  jalur  awal  A  dengan jalur akhir T.  Diperoleh hasil hasil alternatif yang dapat dijadikan solusi yaitu jalur A-B- G-J-M-T=  23+15+5+11=  54  KM.  Dengan  pembahasan  ini  dapat  dijadikan  acuan  oleh pedagang  dalam  mencari  alternatif  terpendek  sehingga  mampu  menghemat  biaya perjalanan dan waktu. Untuk mendapatkan hasil yang optimal dibutuhkan nilai jarak yang akurat agar bisa dijadikan acuan.Metode Depth First Search mampu menghasilkan solusi yang tepat dalam pemilihan alternatif rute terkecil.

## Ucapan Terimakasih
Terima  kasih  penulis  ucapkan  kepada  Kampus  Ibnu  Sina  Batam  yang  sudah mendukung  dan  memotivasi  sehingga  penulis  bisa  mempublikasikan  jurnal  ini  dengan baik. Dan terima kasih juga penulis ucapkan kepada penerbit publikasi ilmiah  sehingga jurnal ini bisa terbit tepat waktu.

## Daftar Pustaka
[1] M.  Sobron  dan  Lubis,  “Implementasi  Artificial  Intelligence  Pada  System Manufaktur Terpadu,” Seminar Nasional Teknik (SEMNASTEK) UISU , vol. 4, no. 1, hal. 1–7, 2021.
[2] E. Gauss-jordan, K. Karim, dan A. P. Linear, “Penerapan Algoritma Breadth First Search pada,” vol. 12, hal. 171–182, 2016.
[3] S. Lailiyah, A. Yusnita, dan T. A. Panotogomo, “Penerapan Algoritma Depth First Search Pada Sistem Pencarian Dokumen,” Snitt , hal. 174–179, 2017.
[4] I. Fauzan, “Artificial Intelligence (Ai) Pada Proses Pengawasan Dan Pengendalian Kepegawaian – Sebuah Eksplorasi Konsep Setelah Masa Pandemi Berakhir,” Civil Service , vol. 14, no. 1, hal. 31–42, 2020.
[5] N.  Juliasari  dan J.  C.  Sitompul,  “Aplikasi  Search  Engine  Dengan  Metode Depth First  Search (DFS),” Jurnal  Teknik  Informatika  Universitas  Budi  Luhur.  ISSN : 1693 -9166 , vol. 9, no. 1, hal. 9–12, 2012.
[6] A. Rismayani, “Aplikasi Berbasis Mobile untuk Pencarian Rute Angkutan Umum Kota Makassar Menggunakan Algoritma Depth First Search ,” vol. 18, no. 3, hal. 171–180, 2015.
[7] M. Febri Mayang Sari dan D. Permata Sari, “Artificial Intelegence Perbandingan Algoritma Simple Hill Climbing Dan Steepest Ascent Hill Climbing Dalam Media Pembelajaran Alfabert,” Jurnal  Sains  Komputer  &  Informatika  (J-SAKTI ,  vol.  6, no. September, hal. 1256, 2022.
[8] B. Prasetiyo dan M. R. Hidayah, “Penggunaan Metode Depth First Search (DFS) dan  Breadth  First  Search  (BFS)  pada  Strategi  Game  Kamen  Rider  Decade  Versi 0.3,” vol. 1, no. 2, hal. 161–167, 2014.
[9] A.  Y.  Prasetyo,  “Penerapan  Algoritma Depth  First  Search (DFS)  Pada  Aplikasi Game Traffic Plaze,” Jurnal Informatika , vol. 8, no. 1, hal. 33–41, 2021.
[10] K. Kristina, K. Kartono, dan U. Wardana, “Penerapan Metode Depth First Search Pada Perancangan Sistem  Pencarian Lokasi Bimbingan Belajar,” Inteksis ,  vol.  9, no. 1, hal. 1–10, 2022.