## PENERAPAN POHON PELACAKAN DALAM MENCARI LINTASAN YANG DAPAT DILALUI OLEH SEEKOR SEMUT PADA BIDANG KARTESIAN DENGAN METODE BREADTH FIRST SEARCH

## Rosdianah
Mahasiswa Program Studi Teknik Informatika STMIK Budi Darma Medan Jl. Sisingamangaraja No.338 Simpang Limun Medan http : //www.stmik-budidarma.ac.id// Email : diianaa.dii@gmail.com

## ABSTRAK
Pohon  Pelacakan  adalah  suatu  metode  pelacakan  yang  dapat  diterapkan  untuk  mencari  solusi    pada bidang  ilmu Artificial  Intelligence  (AI).  Salah  satu  contoh  persoalan AI yang memerlukan penerapan pohon pelacakan adalah dalam pencarian lintasan yang dapat  dilalui  oleh  seekor  semut melalui bidang kartesian. Bidang Kartesian merupakan sistem dua dimensi sistem koordinat yang terdiri dari dua salib sumbu yang saling tegak  lurus.  Pencarian    dimulai    dari    posisi    awal  semut  sebagai    node    akar,    selanjutnya    metode    BFS mencari    solusi    dengan  mengembangkan    node    akar    ke   level-level    berikutnya,    semua    pergerakan    yang memungkinkan,    tidak    melanggar    ketentuan    dan  syarat  serta  menghasilkan    kondisi    baru  yang  dapat dikembangkan  semaksimal  mungkin.  Pencarian  berakhir  apabila  tidak  ada  lagi node  atau  kondisi  baru yang  dapat  dikembangkan.  Semua node  yang  merupakan posisi tujuan merupakan solusi. Hasil penelitian ini adalah  sebuah  perangkat  lunak  dapat  digunakan  untuk  bermain  ‘Permainan  Semut  Mencari  Permen’  pada sebuah komputer.
Kata Kunci : Pohon Pelacakan, Bidang Kartesian, Metode Breadth First Search.
I.

## Pendahuluan
1.1. Latar Belakang
Pohon  pelacakan  adalah  suatu  pohon  yang dapat diterapkan untuk menyelesaikan persoalan pada bidang  ilmu Artificial  Intelligence (AI),  dimana  akar dari  pohon  berupa  keadaan  awal  dari  permasalahan dan  cabang  (dahan)  berupa  keadaan-keadaan  yang mungkin  terjadi  dari  keadaan  sebelumnya  serta  daun merupakan keadaan akhir dari permasalahan tersebut. Keadaan-keadaan  akhir  tersebut  dapat  merupakan solusi  dari  permasalahan  ataupun  mungkin  saja  tidak ada yang dapat dijadikan solusi dari permasalahan.
Pencarian  lintasan  pada  bidang  kartesian, merupakan  permasalahan  yang  menerapkan  metode pohon  pelacakan  untuk  mencari  solusi  dengan mengembangkan node akar ke  level-level  berikutnya, semua  pergerakan  yang  mungkin,  tidak  melanggar ketentuan dan menghasilkan kondisi baru dikembangkan semaksimal mungkin. Pencarian berakhir apabila tidak ada lagi node atau kondisi baru yang  dapat  dikembangkan.  Semua node yang merupakan posisi tujuan merupakan solusi.
Bidang  Kartesian  merupakan  sistem  dua dimensi  sistem koordinat yang  terdiri  dari  dua  salib sumbu yang saling tegak lurus, biasanya sumbu X dan Y,  dimana  nantinya  bidang  kartesian  ini  salah  satu untuk  mendukung  aplikasi  di  tampilan  pemrograman Microsoft Visual Basic 6.0.

## 1.2. Rumusan Masalah
Berdasarkan  latar  belakang  pemilihan  judul, maka yang menjadi permasalahan adalah :
1. Bagaimana  penerapan  pohon  pelacakan  dapat menyelesaikan persoalan  pencarian  lintasan  yang dapat  dilalui  oleh  seekor  semut  pada  bidang kartesian.
2. Bagaimana  bentuk  lintasan-lintasan  yang  dapat dilalui oleh seekor semut.
1.3. Batasan Masalah Batasan permasalahan dalam merancang perangkat lunak ini dibatasi seperti berikut ini:
1. Besar  koordinat  kartesian  dibatasi  minimal  -10 dan  maksimal  +10  baik  untuk  sumbu  x  maupun sumbu y.
2. Ketentuan  atau  aturan  yang  dapat  ditetapkan yaitu:
a. Semut  tidak  boleh  melintasi  atau menempati posisi  rintangan  dan  rintangan  dibatasi maksimal 20 buah.
b. Semut harus melintas pada posisi-posisi yang telah  ditetapkan  dimana  posisi-posisi  yang harus dilalui dibatasi maksimal 20 buah.
c. Kuadran dapat dilalui (Kuadran I, II, III atau IV) dan pilihan bisa lebih dari satu kuadran.
d. Batasan  pergerakan  maksimum  yang  dapat dilalui semut dibatasi maksimal 20.
3. Posisi  awal,  posisi  tujuan,  posisi  rintangan  dan posisi  yang  harus  dilalui  semut  harus  berada dalam batasan koordinat kartesian.
4. Perangkat lunak akan menampilkan semua solusi- solusi yang mungkin, dapat dilalui oleh semut.
5. Jika  tidak  terdapat  solusi,  maka  perangkat  lunak akan menampilkan pesan pemberitahuan.
6. Menampilkan  simulasi  dari  solusi  pergerakan semut dari posisi awal menuju posisi tujuan.
7. Menggunakan  Metode Breadth  First  Search (BFS).
1.4. Tujuan dan Manfaat Penulisan
Tujuan yang ingin dicapai dalam penulisan  Skripsi ini adalah:
1. Untuk  merancang  suatu  perangkat  lunak  yang dapat menyelesaikan persoalan pencarian lintasan yang dapat dilalui oleh seekor semut pada bidang kartesian
2. Dapat  menampilkan  simulasi  lintasan-lintasan
yang dapat dilalui semut dari posisi awal ke posisi tujuan.
Manfaat dari penulisan Skripsi ini adalah :
1. Untuk  membantu  pemahaman  mata  kuliah Artificial  Intelligence  (AI) ,  terutama  mengenai penerapan pohon pelacakan.
2. Perangkat lunak dapat digunakan sebagai fasilitas pendukung  dalam  proses  belajar  mengajar  dan untuk  melatih  kemampuan  yang  dimiliki  penulis dalam bidang teknologi informasi sehingga dapat menambah  wawasan  dan  pengetahuan  bagi pembaca dan penulis.
2.  Landasan Teori
2.1.  Artificial Intelligence
Secara  garis  besar,  AI  terbagi  ke  dalam  dua paham  pemikiran  yaitu  AI  Konvensional  dan Kecerdasan Komputasional ( CI, Computational Intelligence ). AI konvensional kebanyakan melibatkan metoda-metoda yang sekarang diklasifikasikan sebagai  pembelajaran,  yang  ditandai  dengan  formalis dan analisis statistik. AI konvensional juga sebagai AI simbolis,  AI  logis, AI  murni  dan  AI  cara  lama ( GOFAI, Good Old Fashioned Artificial Intelligence ), Winston  dan  Prendergast  di  buku  Kristanto  (2004). Metoda-metodanya meliputi:
1. Sistem
pakar: menerapkan kapabilitas pertimbangan untuk mencapai kesimpulan.
Sebuah  sistem  pakar  dapat  memproses  sejumlah besar informasi  yang  diketahui  dan menyediakan kesimpulan-kesimpulan berdasarkan pada informasi-informasi tersebut.
2. Pertimbangan berdasar kasus.
3. Jaringan Bayesian.
4. AI  berdasar  tingkah  laku:  metoda modular pada pembentukan sistem AI secara manual.
Artificial Intelligence (AI) disebut juga dengan kecerdasan  buatan.  AI  merupakan  salah  satu  bagian ilmu  komputer  yang  mempelajari  tentang  bagaimana cara  membuat  agar  komputer  dapat  melakukan pekerjaan  seperti  yang  dilakukan  oleh  manusia.  AI umumnya  dilukiskan  sebagai  kekuatan  masa  depan yang  akan  mencoba  menggulingkan  otoritas  manusia seperti  dalam  HAL  9000,  Skynet,  Colossus  and  The Matrixatau  sebagai  penyerupaan  manusia  untuk memberikan  layanan  seperti  C-3PO,  Data,  the Bicentennial  Man,  the  Mechas  dalam  AI.  Sifat dominasi dunia AI yang tak dapat dielakkan, kadang- kadang disebut the Singularity, Paul Y. Gloess di buku Kristanto (2004 : hal 2).
Keberadaan  mesin  cerdas  mempersoalkan definisi  hidup  sebagai  organisme  lebih  dari  sekedar kategori  entitas  mandiri  yang  lebih  luas, membangun konsep kecerdasan sistemik yang bergagasan. 2.2.  Representasi Pengetahuan
Dua  bagian  terbesar  yang  membangun  AI adalah  basis  pengetahuan  dan  mekanisme  inferensi. Pangkalan  pengetahuan  berisi  fakta-fakta  tentang objek  dalam  domain  yang  ditentukan  dan  saling berhubungan  satu  sama  lain.  Seluruh  program  AI difokuskan pada domain tertentu. Pangkalan pengetahuan juga berisi pikiran, teori, prosedur praktis dan  saling  berhubungan.  Pangkalan  pengetahuan membentuk sumber sistem inteligensia dan digunakan
oleh mekanisme inferensi untuk melakukan penalaran dan menarik kesimpulan.
Mekanisme  Inferensi,  adalah  suatu  rangkaian prosedur  yang  digunakan  untuk  menguji  pangkalan pengetahuan  dengan  cara  yang  sistematik  pada  saat menjawab  pertanyaan,  memecahkan  persoalan  atau membuat  keputusan  dalam  suatu  domain,  mekanisme inferensi  melakukan  pelacakan  melalui  pangkalan pengetahuan untuk mencari jawaban dan solusinya.
Pangkalan  pengetahuan  berisi  data  struktur yang  bisa  dimanipulasi  oleh  sistem  inferensi,  yang merupakan  bagian  utama  program  AI.  Sistem inferensi menggunakan teknik pelacakan dan pencocokan pola ( pattern matching ) dalam pangkalan pengetahuan agar bisa menjawab pertanyaan, menarik kesimpulan  atau  tugas-tugas  lainnya  yang  bersifat inteligensia.
2.3.  Problem State, Space and Seacrh
State  adalah  representasi  suatu  keadaan  pada suatu  saat  ataupun  dekripsi  konfigurasi  sistem.  State space  adalah  semua  state  (keadaan)  yang  mungkin, dan  biasanya  digambarkan  sebagai  jaringan  dengan verteks  merupakan  state  dan  edge  merupakan perubahan yang mungkin.
Dekripsi formal suatu masalah adalah:
1. Definisikan state space .
2. Tentukan initial state dalam goal state .
3. Tentukan operator-operator.
Representasi state space memungkinkan definisi  formal  suatu  masalah  sebagai  persoalan mengubah  status  dengan  menggunakan  sekumpulan operator  (rule)  dan  juga  mendefinisikan  masalah sebagai  search  yaitu  mencari  lintasan  di  dalam  state space dari initial state ke goal state.
Dalam  hipotesis  sistem  simbol  Newell  dan Simon,  yang  menyatakan  bahwa  problema-problema dapat  dipecahkan  dengan  melakukan  pencarian (search)  dari  antara  pilihan-pilihan  yang  ada, terdukung oleh pandangan cara penyelesaian manusia yang bisa dilakukan. Manusia umumnya mempertimbangkan sejumlah alternatif strategi dalam menyelesaikan  suatu  problema,  dalam  permainan catur  misalnya,  seorang  pemain  mempertimbangkan sejumlah  kemungkinan  tentang  langkah-langkah berikutnya,  memilih  yang  terbaik  menurut  kriteria tertentu  seperti  kemungkinan  respon  lawannya,  atau memilih  sejumlah  langkah  menurut  suatu  strategi global yang dirancangnya. Seorang pemain catur juga memperhitungkan  pencapaian  jangka  pendek  (seperti siasat  untuk  memperoleh  keuntungan  materi  atau kualitas).  Aspek  tingkah  laku  cerdas  yang  mendasari teknik  penyelesaian  problema  seperti  dalam  catur  ini disebut  proses  pencarian  ruang  keadaan  (space  state search).
2.4.  Tekhnik Pemecahan Masalah Artificial Intelligence
Di  dalam Artificial  Intelligence (AI) dikenal ada  empat  teknik  pemecahan  masalah  menurut, Suyanto (2011 : hal 11) yaitu :
1. Searching
Suatu  masalah  dengan  teknik Searching atau pencarian,  ruang  masalah  ini  dapat  digambarkan sebagai  himpunan  keadaan  ( state )  atau
bisa  juga  sebagai  himpunan  rute  dari  keadaaan awal  ( initial  sta te)  menuju  keadaan  tujuan  ( goal state ). 2. Planning
Suatu  teknik  penyelesaian  masalah  yang  hanya bisa  digunakan  untuk  menyelesaikan  masalah- masalah  yang  dapat  didekomposisi.  Teknik  ini bisa menyelesaikan masalah besar yang mungkin tidak bisa ditangani oleh teknik searching .
3. Reasoning
Yakni  teknik  penyelesaian  masalah  dengan  cara merepresentasikan    masalah  ke  dalam  basis pengetahuan  ( knowledge  base )  menggunakan logic atau bahasa formal (bahasa yang di pahami komputer).  Dua logic pertama  digunakan  untuk masalah yang tidak memiliki kepastian, sedangkan fuzzy  logic digunakan  untuk  masalah yang tidak memiliki ketidakpastian ( uncertainty ).
4. Learning Suyanto  (2011  :  hal  153)  menyimpulkan  masalah learning ada 3 teknik metode yaitu :
a. Decision Tree Learning
b. Jaringan Syaraf Tiruan
c. Algoritma Genetika
2.5.  Metode Pencarian Breadth-First Search (BFS)
Hal terpenting dalam menentukan keberhasilan sistem yang berdasarkan AI adalah kesuksesan dalam pencarian  dan  pencocokan.  Pada  dasarnya,  terdapat  2 (dua) teknik pencarian dan pelacakan yang digunakan, yaitu:
1. Pencarian  buta  (Blind  search),  dapat  dibagi menjadi:
a. Pencarian  Melebar  Pertama  ( Breadth-First Search )
b. Pencarian  Mendalam  Pertama  ( Depth-First Search )
2. Pencarian Terbimbing ( Heuristic Search ) Metode  pencarian  yang  digunakan,  dengan melakukan metode Breadth-First Search (BFS). Pencarian  Melebar  Pertama  ( Breadth-First Search ), Pada  metode  ini,  semua node pada  level n akan dikunjungi terlebih dahulu sebelum mengunjungi node - node pada  level n +1  (level  berikutnya). Pencarian  dimulai  dari node akar  terus  ke  level  ke-1 dari kiri ke kanan, kemudian berpindah ke level-2 dan seterusnya.
Pohon
dikembangkan hingga ditemukannya solusi.
2.6.  Bidang Kartesian Menurut  Handoko  (2004).  Bidang kartesian adalah merupakan dua dimensi sistem koordinat yang terdiri  dari  dua  salib  sumbu  yang  saling  tegak  lurus, biasanya  sumbu  X  dan  Y,  seperti  digambarkan  pada gambar di bawah ini :
Gambar 1 Sistem Kartesian Sumber : Handoko, E. Yuli. System koordinat, (Surabaya : 2004)
Dari  gambar  diatas,  koordinat  mempunyai jarak pada sumbu X yang disebut absis sebesar 3 dan mempunyai jarak pada sumbu Y yang disebut  ordinat sebesar  5.  Sedangkan  d  merupakan  jarak  dari  pusat sumbu koordinat (O) ke titik.
2.7.  Pencarian Lintasan pada Bidang Kartesian
Salah  satu  permasalahan  yang  dapat  diangkat menjadi  topik  pembahasan  AI  adalah  pencarian lintasan  pada  bidang  kartesian.  Permasalahan  ini menerapkan  metode  pohon  pelacakan  untuk  mencari solusi.
Dimulai  dari  posisi  awal  sebagai  node  akar, selanjutnya  metode  BFS  mencari  solusi  dengan mengembangkan node  akar ke  level-level  berikutnya, semua  pergerakan  yang  mungkin,  tidak  melanggar ketentuan dan menghasilkan kondisi baru dikembangkan semaksimal mungkin. Pencarian berakhir apabila tidak ada lagi node atau kondisi baru yang  dapat  dikembangkan.  Semua node yang merupakan posisi tujuan merupakan solusi.
Permasalahan  ini  dapat  didekripsikan  sebagai berikut,  diketahui  seekor  semut  akan  bergerak  dari titik pusat (0,0) ke titik A(m,n) pada bidang kartesian. Semut tersebut hanya boleh membelok pada titik-titik grid  dan  selalu  melangkah  sejajar  dengan  sumbu-x atau  sumbu-y  (horizontal  atau  vertikal).  Semut tersebut  tidak  boleh  melintasi  lintasan  yang  telah pernah dilaluinya dan tidak boleh melintasi titik yang telah  pernah  dilaluinya.  Setelah  itu,  disediakan sederetan  ketentuan  yang  membatasi  pergerakan semut  tersebut.  Pertanyaannya  adalah  bagaimana bentuk  lintasan-lintasan  (yang  mungkin)  yang  dapat dilalui  oleh  semut  tersebut  dengan  menggunakan ketentuan-ketentuan yang telah ditetapkan di atas.
Sebagai  contoh, titik  yang  dituju  semut  adalah titik(m,  n)  =  (3,  2).  Aturan,  semut  hanya  boleh bergerak pada kuadran I (sumbu x positif dan sumbu y positif), pergerakan semut tidak boleh melewati batas maksimal,  x  =  3  dan  y  =  2,  maka  dengan  pohon pelacakan,  kita  dapatkan  pergerakan  yang  mungkin menuju keadaan tujuan adalah sebagai berikut:
1 2 3 4 -4 -3 -2 -1 1 2 3 -3 -2 -1 Gambar 2. Solusi Lintasan-1 1 2 3 4 -4 -3 -2 -1 1 2 3 -3 -2 -1
Gambar 3 Solusi Lintasan-2

## 3. Analisa dan Perancangan

## 3.1.  Analisa Perancangan
Pencarian  lintasan  yang  dapat  dilalui  oleh seekor  semut  pada  bidang  kartesian  dapat  dilakukan dengan  bantuan  pohon  pelacakan.  Deskripsi  dari permasalahan  ini  adalah  sebagai  berikut,  diketahui seekor  semut  akan  bergerak  dari  suatu  titik  (x,y)  ke titik  A(m,n).  Semut  hanya  boleh  membelok  atau melintas  pada  titik-titik  grid  dan  selalu  melangkah sejajar  dengan  sumbu-x  atau  sumbu-y.  Semut  tidak boleh  melintasi  lintasan  yang  telah  pernah  dilaluinya atau  melintasi  titik  yang  telah  pernah  dilaluinya. Setelah  itu,  disediakan  sederetan  ketentuan  yang membatasi pergerakan semut tersebut. Ketentuan yang membatasi adalah batas pergerakan maksimum semut yang  diperbolehkan,  posisi-posisi  rintangan  dimana semut  tidak  boleh  melintas,  posisi-posisi  dimana semut  harus  melintas  dan  semut  hanya  melintasi kuadran yang diperbolehkan untuk melintas.
Dimulai  dari  posisi  awal  sebagai  node  akar, selanjutnya metode breadth-first search (BFS) mencari solusi  dengan  mengembangkan  node  akar  ke  level- level  berikutnya,  semua  pergerakan  yang  mungkin, tidak  melanggar  ketentuan  dan  menghasilkan  kondisi baru  dikembangkan  semaksimal  mungkin.  Pencarian berakhir apabila tidak ada lagi node atau kondisi baru yang  dapat  dikembangkan.  Semua  node  yang merupakan posisi tujuan merupakan solusi.
Contoh  struktur  pohon  pelacakan  yang dikembangkan berdasarkan metode pencarian breadth - first  search (BFS)  dapat  dilihat  pada  gambar 4.
(0,0)
(1,0) (-1,0) (0,1) (0,-1) (2,0) (1,1) (1,-1) (-2,0) (-1,1) (-1,-1) (1,1) (-1,1) (0,2) (1,-1) (-1,-1) (0,-2)
Gambar 4Contoh struktur pohon pelacakan dengan metode BFS
Dari  solusi-solusi  yang  ditemukan,  terdapat solusi  yang optimum. Dalam implementasinya, solusi optimum  merupakan  langkah  penyelesaian  terpendek ( shortest path ) yang ditemukan dengan menggunakan pohon  pelacakan.  Dalam  kasus  pergerakan  semut, solusi  paling  optimum  (pergerakan  terpendek  tanpa halangan) dapat  ditentukan kriterianya. Simak contoh berikut,  apabila posisi  awal  semut adalah ( x 1 , y 1 )  dan posisi tujuan semut adalah ( x 2 , y 2 ) maka solusi paling optimum  (langkah  terpendek)  menuju  posisi  tujuan dapat  dihitung  dengan  rumus:  ( abs ( x 2 – x 1 ), abs ( y 2 – y 1 )).  Ini  artinya,  pergerakan  sepanjang  sumbu x (horizontal)  adalah  sebesar abs ( x 2 – x 1 )  langkah  dan pergerakan  sepanjang  sumbu y (vertikal)  adalah sebesar abs ( y 2 – y 1 ).
Misalkan posisi awal semut adalah (-1, -2) dan posisi  tujuan  semut  adalah  (4,  5),  maka  solusi  yang paling  optimum  adalah  solusi  yang  memiliki  kriteria sebagai berikut:
1. Pergerakan  sepanjang  sumbu x (horizontal) adalah abs (4 - (- 1)) = 5 langkah.
2. Pergerakan  sepanjang  sumbu y (vertikal)  adalah abs (5 - (- 2)) = 7 langkah.
Kriteria  solusi  paling  optimum  dapat  dilihat  pada gambar 3.2 berikut.
Posisi awal (-1,-2) Posisi tujuan (4,5) Solusi paling optimum adalah solusi yang memiliki pergerakan: X = (4- (-1) = 5 Y = (5 - (-2) = 7. Ditunjukkan oleh garis merah putus-putus

## Gambar 5 Kriteria solusi paling optimum
Posisi awal (-1,-2) Posisi tujuan (4,5) Solusi paling optimum dengan kriteria tidak dapat dicapai karena dihalang oleh rintangan. Oleh karena itu, solusi optimum adalah solusi terpendek yang dapat ditemukan oleh pohon pelacakan
Gambar 6 Solusi paling optimum terhalang oleh rintangan
4.  Algoritma dan Implementasi Algoritma perancangan perangkat lunak penerapan  pohon  pelacakan  dalam  mencari  lintasan yang  dapat  dilalui  oleh  seekor  semut  pada  bidang kartesian dengan Metode Breadth First Search (BFS) dapat dibagi menjadi 2 (dua) bagian, yaitu :
1. Algoritma Validasi Posisi.
2. Algoritma Pencarian Solusi Pergerakan Semut.
4.1. Algoritma Validasi Posisi
Fungsi  dari  algoritma  ini  adalah  untuk mengecek input posisi  awal  dan  posisi  tujuan  supaya tidak bertentangan dengan kuadran yang diperbolehkan  untuk  dilalui.  Algoritma  ini  dijalankan
sebelum  perangkat  lunak  mulai  mencari  solusi pergerakan.  Apabila  terdapat  kesalahan,  maka perangkat  lunak  akan  menampilkan  pesan  kesalahan dan  posisi  dianggap  tidak valid .  Berikut  adalah algoritma validasi posisi:
1. Jika  posisi  awal  kosong,  maka  munculkan  pesan kesalahan ‘Posisi awal belum diatur !”.
2. Jika posisi tujuan kosong, maka munculkan pesan kesalahan ‘Posisi tujuan belum diatur !”.
3. Jika X_Awal > 0 dan Y_Awal > 0 dan kuadran I tidak boleh dilalui semut, maka munculkan pesan kesalahan  ‘Posisi  awal  semut  berada  pada kuadran I. Checklist kuadran I !’.
4. Jika  X_Tujuan  >  0  dan  Y_Tujuan  >  0  dan kuadran  I  tidak  boleh  dilalui  semut,  maka munculkan  pesan  kesalahan  ‘Posisi  tujuan  semut berada pada kuadran I. Checklist kuadran I !’.
5. Jika X_Awal < 0 dan Y_Awal > 0 dan kuadran II tidak boleh dilalui semut, maka munculkan pesan kesalahan  ‘Posisi  awal  semut  berada  pada kuadran II. Checklist kuadran II !’.
6. Jika  X_Tujuan  <  0  dan  Y_Tujuan  >  0  dan kuadran  II  tidak  boleh  dilalui  semut,  maka munculkan  pesan  kesalahan  ‘Posisi  tujuan  semut berada pada kuadran II. Checklist kuadran II !’.
7. Jika X_Awal < 0 dan Y_Awal < 0 dan kuadran III tidak boleh dilalui semut, maka munculkan pesan kesalahan  ‘Posisi  awal  semut  berada  pada kuadran III. Checklist kuadran III !’.
8. Jika  X_Tujuan  <  0  dan  Y_Tujuan  <  0  dan kuadran  III  tidak  boleh  dilalui  semut,  maka munculkan  pesan  kesalahan  ‘Posisi  tujuan  semut berada pada kuadran III. Checklist kuadran III !’.
9. Jika  X_Awal  >  0  dan  Y_Awal  <  0  dan  kuadran IV  tidak  boleh  dilalui  semut,  maka  munculkan pesan  kesalahan  ‘Posisi  awal  semut  berada  pada kuadran IV. Checklist kuadran IV !’.
10. Jika  X_Tujuan  >  0  dan  Y_Tujuan  <  0  dan kuadran  IV  tidak  boleh  dilalui  semut,  maka munculkan  pesan  kesalahan  ‘Posisi  tujuan  semut berada pada kuadran IV. Checklist kuadran IV !’

## 4.2. Algoritma Pencarian Solusi Pergerakan Semut
Pencarian solusi pergerakan semut menggunakan  metode  pencarian  melebar  pertama breadth-first  search (BFS),  karena  solusi  dari permasalahan bisa lebih dari satu. Dimulai dari posisi awal  sebagai node akar,  selanjutnya  metode breadth- first search (BFS) mencari solusi dengan mengembangkan node akar ke  level-level  berikutnya, semua  pergerakan  yang  mungkin,  tidak  melanggar ketentuan dan menghasilkan kondisi baru dikembangkan semaksimal mungkin. Pencarian berakhir apabila tidak ada lagi node atau kondisi baru yang  dapat  dikembangkan.  Semua node yang merupakan posisi tujuan merupakan solusi.
Adapun  pergerakan  semut  yang  diperbolehkan adalah: 1. Bergerak ke kanan ( x + 1).
2. Bergerak ke kiri ( x – 1).
3. Bergerak ke atas ( y + 1).
4. Bergerak ke bawah ( y – 1).
5. Semua  pergerakan  semut  di  atas  legal  apabila mematuhi ketentuan-ketentuan sebagai berikut:
a. Tidak melintasi posisi titik rintangan.
b. Melintasi posisi-posisi yang telah ditentukan.
c. Tidak  melintasi  posisi  titik  yang  sudah pernah dilalui sebelumnya.
d. Tidak  melebihi  batas  pergerakan  maksimum semut ( x atau y ). e. Tidak melintasi kuadran yang tidak diperbolehkan untuk melintas. Kuadran yang dimaksud adalah kuadran I (dimana x bernilai positif  dan y bernilai  positif),  kuadran  II (dimana x bernilai  negatif  dan y bernilai positif), kuadran III (dimana x bernilai negatif dan y bernilai  negatif)  dan  kuadran  IV (dimana x bernilai  positif  dan y bernilai positif)
4.3. Implementasi Sistem
Sebagai contoh pengujian, input data perangkat lunak adalah sebagai berikut.
1. Posisi awal semut = (1, 3).
2. Posisi tujuan semut = (-3, 1).
3. Pergerakan maksimum semut = (5, 5).
4. Posisi rintangan adalah sebagai berikut:
a. Rintangan1: (-1, 4).
b. Rintangan2: (-1, 2).
c. Rintangan3: (-3, 3).
d. Rintangan4: (2, 2).
e. Rintangan5: (1, 1).
f. Rintangan6: (0, 5).
g. Rintangan7: (-2, 0).
5. Posisi  yang  harus  dilalui  semut  adalah  sebagai berikut:
a. Posisi1: (-1, 1).
b. Posisi2: (-2, 1).
6. Hanya  kuadran  I  dan  kuadran  II  yang  boleh dilalui semut.
Tampilan form input dapat dilihat pada 7.
Gambar 7  Tampilan form input pada contoh kasus
Proses  pencarian  solusi  pada form pencarian  dapat dilihat pada gambar 8.
Gambar 8 Pencarian solusi pada form pencarian
Hasil pencarian solusi adalah sebagai berikut:
Pergerakan sumbu x = 4.
Pergerakan sumbu y = 2. Merupakan solusi optimum. Gambar 9 Hasil Pencarian-1 Pergerakan sumbu x = 4. Pergerakan sumbu y = 2. Merupakan solusi optimum.
Gambar 10 Hasil Pencarian-2
Pergerakan sumbu x = 4.
Pergerakan sumbu y = 4.
Bukan solusi optimum.

## Gambar 11 Hasil Pencarian-3
Pergerakan sumbu x = 4. Pergerakan sumbu y = 4. Bukan solusi optimum.
Gambar 12  Hasil Pencarian-4
Pergerakan sumbu x = 4.
Pergerakan sumbu y = 4.
Bukan solusi optimum.
Gambar 13 Hasil Pencarian-5 5. Kesimpulan dan Saran 5.1. Kesimpulan Setelah menyelesaikan penerapan pohon pelacakan  dalam  mencari  lintasan  yang  dapat  dilalui oleh  seekor  semut  pada  bidang  kartesian  dengan Metode Breadth  First  Search (BFS),  penulis  menarik kesimpulan sebagai berikut:
1. Perangkat lunak mencari semua solusi pergerakan semut  yang  mungkin  menuju  posisi  tujuan.  Oleh karena  solusi  pergerakan  bisa  lebih  dari  satu, maka  perangkat  lunak  menggunakan  metode pencarian  melebar  pertama breadth  first  search
(BFS).
2. Perangkat lunak mensimulasikan semua pergerakan  semut  dari  posisi  awal  menuju  posisi tujuan.
3. Perangkat  lunak  merupakan  implementasi  nyata penerapan pohon pelacakan dalam mencari solusi.
5.2. Saran Penulis ingin memberikan beberapa saran yang
mungkin  dapat  membantu  dalam  pengembangan perangkat lunak ini yaitu:
1. Dipertimbangkan  untuk  menambahkan  metode pencarian lain yang terdapat dalam ilmu Artificial Intelligence (AI).
2. Dikemudian hari,  jika  judul ini  diangkat  kembali menjadi  skripsi  sebaiknya  pemrograman  harus menggunakan pemrograman JAVA.
DAFTAR PUSTAKA
1. Agnes  Heni  Triyuliana, Visual  Basic  6.0 , Penerbit  Andi dan  Madcoms, Yogyakarta, 2006.
2. Fowler.  M, UML  Distilled ,  Penerbit  Andi, Yogyakarta, 2004.
3. Kristanto. A, Kecerdasan Buatan , Penerbit Graha
Ilmu, Yogyakarta, 2004. 4. Kusumadewi.  S, Artificial   Intelligence    (Teknik dan Aplikasinya) , Penerbit Graha Ilmu,
Yogyakarta, 2003.
5. Sandi.  S, Aritificial  Intelegencia ,  Andi  Offset, Yogyakarta, 1993.
6. Sholiq, Pemodelan Sistem Informasi Berorientasi Objek Dengan UML , Penerbit Graha Ilmu, Yogyakarta, 2002.