LAPORAN

DESAIN ANALISA ALGORITMA

NIM :
NAMA :
JURUSAN :
KELAS :

JURUSAN TEKNIK INFORMATIKA

FAKULTAS TEKNOLOGI INFORMASI
UNIVERSITAS ISLAM BALITAR
2020
 BAB I
PENDAHULUAN

1.1 PENGERTIAN ALGORITMA

Pengertian algoritma pemograman merupakan hal yang akan sering ditemukan

dalam perkuliahan yang berkaitan dengan ilmu komputer dimana algoritma merupakan
langkah – langkah untuk menyelesaikan masalah sedangkan pemograman adalah
kegiatan membuat program, dalam hal ini program komputer.

Algoritma menjadi salah satu mata kuliah yang selalu ada dan diajarkan bagi mahasiswa
yang mengambil perkuliahan yang berkaitan dengan ilmu komputer. Ilmu yang
mengajarkan tentang algoritma merupakan salah satu ilmu yang sangat dihandalkan pada
era perkembangan teknologi seperti saat ini dimana hampir semua elemen komputer
membutuhkan inovasi – inovasi baru untuk menyelesaikan permasalahan-permaslahan
yang nantinya membuat penggunaan komputer semakin lebih efisien dan mampu
menyelesaikan berbagai permasalahan.

Algoritma ditulis untuk membuat komputer menjadi alat yang dapat menyelesaikan
permasalahan – permasahan yang telah dihadapkan oleh para pembuatnya.
Permasalahan – permasalahan ini umumnya mencakup permasalahan – permasalahan
komputasional dari berbagai macam aspek kehidupan.
 BAB II

 Algoritma Bactracking

Algoritma Backtracking merupakan salah satu bentuk algoritma yang banyak digunakan
oleh para programmer ataupun pengguna komputer ahli untuk menyelesaikan suatu
permasalahan komputasional pada perangkat komputer yang mereka gunakan. Dalam
programming algoritma backtracking, rekursi adalah kunci dari programming backtracking.
Rekursi sendiri merupakan proses pengulangan suatu hal yang mencakup kesamaan-diri.
Penggunaan yang paling umum dari rekursi terdapat dalam kajian ilmu matematika dan
ilmu komputer.

Algoritma rekursi merupakan algoritma yang memanggil dirinya sendiri secara berulang
kali. Backtracking sebuah algoritma secara umum digunakan untuk menemukan semua
(atau beberapa) solusi terhadap sebuah permasalahan komputasional. Proses
backtracking dapat diaplikasikan hanya pada beberapa permasalahan yang mengikuti
konsep “solusi kandidat parsial” dan juga sebuah tes yang cukup relatif cepat untuk
menentukan kemungkinan apakah solusi tersebut valid atau tidak.

Backtracking tidaklah berguna untuk menyelesaikan permasalahaan seperti menentukan

sebuah nilai yang diberikan pada sebuah tabel yang tidak beraturan. Akan tetapi ketika
diaplikasikan, backtracking biasanya lebih cepat bila dibandingkan proses pemecahan
masalah brute force yang mana harus mencoba semua kandidat kemungkinannya.

Sebagai salah satu algoritma yang banyak digunakan oleh para programmer.
Backtracking merupakan sebuah alat yang penting untuk dapat menyelesaikan
permasalahan pemenuhan terbatas, seperti teka – teki silang, aritmatika verbal, sudoku
dan berbagai macam puzzle sejenisnya. Algoritma ini juga dapat digunakan untuk
menyelesaikan permasalahan komputasional seperti memecahkan kata sandi atau
password pada suatu program, membuat sistem kerja atau mekanisme kerja dari suatu
video game, ataupun sistem dasar dari suatu simulasi komputer terhadap permasalahan
di dunia nyata.

Dalam penggunaannya backtracking bergantung pada perintah yang diberikan oleh

penggunanya (prosedur kotak hitam) yang mana menentukan permasalahan untuk
diselesaikan dengan cara kandidat parsial dan bagaimana mereka dikembangkan untuk
menjadi kandidat penyelesaian maslaah secara sepenuhnya. Untuk dapat
mengimplementasikannya dengan baik anda haruslah memahami fungsi flowchart dalam
pemograman agar bisa memberikan hasil yang maksimal.

Penggunaannya Secara Umum

Penggunaan algoritma pemograman bisa digunakan di berbagai macam-macam bahasa

pemrograman. Algoritma backtracking merupakan sebuah bentuk tipikal dari algoritma
rekursif. Saat ini algoritma backtracking banyak diterapkan untuk membuat permainan
video games menjadi lebih menarik, banyak video games yang memanfaatkan
kecerdasan buatan dengan menggunakan algoritma backtracking untuk membuat
permainan lebih menarik.

Selain hal tersebut algoritma backtracking juga sangatlah berguna untuk mencari solusi
yang membutuhkan berbagai macam kombinasi jalan untuk menyelesaikan permasalahan
yang selalu berubah/ bersifat dinamis.

Untuk menyelesaikan masalah – masalah yang mempunyai kemungkinan solusi yang

kompleks, seperti permainan catur ataupun permasalahan – permasalahan sejenisnya,
sebaiknya ke dalam pohon kemungkinan diberikan batas tertentu. Hal ini dilakukan
sehingga tidak menghabiskan waktu yang sangat lama (hal ini akan bergantung pada jenis
kekuatan atau performa komputer yang digunakan untuk menyelesaikan masalahnya).
Semakin dalam pohon yang ditelusuri, maka akan semakin akurat pula jalan menuju solusi
yang ingin dicari.

Alokasi memori yang akan digunakan untuk menyimpan jalan solusi sebaiknya
menggunakan dynamic array yang mengingat sebagian besar program yang
menggunakan algortima ini menghasilkan solusi yang sedang dijelajahi (explore) menuju
ke solusi yang diharapkan.

Mengenai Algoritma Backtracking

Algoritma backtracking menghitung kumpulan kandidat parsial, yang dalam prinsipnya,

hanya dapat diselesaikan dalam berbagai cara untu kmemberikan berbagai kemungkinan
solusi terhadap permasalahan yang hendak diselesaikan. Penyelesaiannya juga dilakukan
secara bertahap dari satu sekuens kandidat kemungkinan ke kemungkinan lainnya.

Secara konseptual, setiap kandidat parsial direpresentasikan sebagai sebuah node dari
struktur pohon yang merupakan sebuah pencarian dari kandidat potensial penyelesaian
masalah. Setiap kandidat parsial merupakan sebuah turunan dari kandidat yang berbeda
dari asalnya yang memiliki langkah perpanjangan dalam penyelesaiannya, turunan dari
kandidat parsial yang tidak dapat diperpanjang lagi.

Penggunaan algoritma backtracking tidak dapat dilepaskan oleh tingkat perkembangan

komputer yang ada beberapa dekade belakangan. Dewasa ini komputer menjadi
kebutuhan bagi semua kalangan dalam berbagai bidang. Dengan kemunculannya
berbagai macam algoritma yang dapat menyelesaikan berbagai macam permasalahan –
permasalahan yang dimiliki oleh manusia dan juga kemunculan algoritma yang memiliki
fungsi – fungsi yang beragam. Tentu akan membuat perkembangan teknologi yang
semakin canggih akan menjadi mencapai berbagai aspek kehidupan manusia.

Dengan mempelejari hal ini lebih lanjut tentu akan membuat anda merasakan manfaat
mempelajari ilmu komputer. Begitu juga dengan memahami cara kerja algoritma
backtracking.  Dengan memahami potensi yang dimiliki oleh algoritma backtracking anda
dapat menghasilkan sebuah algoritma yang nantinya dapat mempermudah pekerjaan
manusia dalam menyelesaikan suatu masalah di masa depan.
  Algoritma B&B (Branch and Bound)

Algoritma B&B (Branch and Bound) adalah salah satu algoritma yang digunakan untuk
pencarian jalur. Contoh yang dibahas kali ini adalah mengenai pencarian jalur yang
melalui semua titik dengan biaya terendah.
Algoritma ini memiliki 2 prinsip, yaitu:

 Algoritma ini akan melakukan perhitungan secara rekursif, akan memecah masalah
kedalam masalah-masalah kecil, sambil tetap menghitung nilai terendah / terbaik.
Proses ini dinamakan branching
 Jika branching diterapkan secara sendirian, maka hasilnya akan tetap mencari
setiap kemungkinan yang ada. Untuk meningkatkan performa, algoritma ini akan
melakukan pencatatan biaya minimum sebagai bound dalam setiap perhitungan,
sehingga untuk calon hasil jawaban yang diperkirakan akan melebihi bound akan
dibuang karena tidak mungkin akan mencapai nilai terbaik

Diasumsikan ada 5 titik yang harus dilalui semuanya, yaitu A,B,C,D,E

semua titik tidak terhubung secara langsung dengan titik-titik lainnya, melainkan hanya
melalui jalur tertentu saja
setiap jalur juga memiliki biaya sendiri-sendiri
maka tentukan jalur yang harus diambil untuk mengelilingi semua titik yang ada
Diasumsikan data jalur yang tersedia adalah sebagai berikut
Titik awal Titik Tujuan Biaya

Titik A Titik B 10

Titik A Titik E 11

Titik B Titik A 12

Titik B Titik C 20

Titik B Titik D 6

Titik B Titik E 9

Titik C Titik B 15

Titik C Titik D 14

Titik D Titik B 7

Titik D Titik C 5

Titik E Titik C 8

Titik E Titik D 13

Jika diilustrasikan dalam gambar, maka model data awal adalah sebagai berikut
Sebelum masuk kedalam langkah-langkah pembahasan algoritma, ada beberapa
konstanta atau parameter yang harus diketahui, yaitu:
* Tentukan jumlah titik yang harus dihubungkan
Diasumsikan dalam kasus ini, jumlah titik ada 5 buah

Const jumlahTitik As Integer = 5

Langkah-langkah penggunaan algoritma ini adalah

1. Lakukan inisialisasi daftar jalur sesuai dengan data yang tersedia

Terdapat matriks berukuran [jumlah titik x jumlah titik] untuk menyimpan jalur dari masing-
masing titik
Jika tidak ada jalur diantara 2 titik, maka nilai jalurnya adalah 0

Dim daftarBiaya(,) As Double = New Double(jumlahTitik - 1, jumlahTitik - 1) { _

{0, 10, 0, 0, 11}, _
{12, 0, 20, 6, 9}, _
{0, 15, 0, 14, 0}, _
{0, 7, 5, 0, 0}, _
{0, 0, 8, 13, 0} _
}

2. Hitung rata-rata biaya pada semua data

Nilai ini nantinya akan digunakan untuk perkiraan nilai biaya apakah akan melebihi bound
atau tidak

Dim rata2 As Integer = 0

Dim count As Integer = 0
For i As Integer = 0 To jumlahTitik - 1
For j As Integer = 0 To jumlahTitik - 1
If daftarBiaya(i, j) <> 0 Then
rata2 += daftarBiaya(i, j)
count += 1
End If
Next
Next
rata2 /= count
3. Lakukan perhitungan pencarian jalur melalui semua titik yang ada
Penjelasan tentang fungsi ini akan dijelaskan pada perhitungan dibawah ini (poin 3a)

CariJalurTerbaik(jumlahTitik, rata2, daftarBiaya, jalurTerbaik, BiayaTerbaik)

Memasuki perhitungan pada fungsi CariJalurTerbaik

3a. Lakukan perhitungan pada masing-masing titik (poin 3a1 – 3a3)

For i As Integer = 0 To jumlahTitik - 1

...

3a1. Beri nilai awal calon jalur dengan nilai -1

For j As Integer = 0 To jumlahTitik - 1

calonJalur(j) = -1
Next

3a2. Lakukan perhitungan pada masing-masing titik selain titik awal (poin 3a2a – 3a2c)

For j As Integer = 0 To jumlahTitik - 1

If daftarBiaya(i, j) <> 0 Then
...

3a2a. Masukkan titik awal pada calon jalur yang sedang dihitung

calonJalur(0) = i

3a2b. Inisialisasi titik titik yang sudah dihitung dengan nilai false,
kemudian tandai titik awal dengan nilai True agar tidak dapat digunakan dalam
perhitungan selanjutnya

Dim titikTerpilih(jumlahTitik - 1) As Boolean

titikTerpilih(i) = True

Lakukan pencarian jalur dimulai dari titik awal yang terpilih

Penjelasan lebih detail tentang fungsi ini dapat dilihat pada penjelasan dibawah ini

CariJalur(jumlahTitik, rata2, daftarBiaya, jalur, biaya, titikTerpilih, calonJalur,

totalCalonJalur, 1)
Memasuki Perhitungan pada fungsi CariJalur

Jika semua titik sudah terpilih, maka bandingkan total biaya jalur ini dengan total biaya
[Link] total biaya jalur ini kurang dari total biaya terbaik, maka ambil total jalur ini
sebagai jalur terbaik

If jumlahTitikTerpilih >= jumlahTitik Then

If totalCalonJalur < biayaTerbaik Then
biayaTerbaik = totalCalonJalur
[Link](calonJalur, jalurTerbaik, jumlahTitik)
End If

Lakukan perhitungan dibawah ini apabila kondisi diatas tidak terpenuhi

Lakukan pengecekan terhadap sisa titik yang akan dihitung

Apabila perkiraan sisa titik akan melebihi bound biaya terbaik, maka hentikan perhitungan

Dim sisaTitik As Integer = jumlahTitik - jumlahTitikTerpilih

If totalCalonJalur + rata2 * sisaTitik >= biayaTerbaik Then
Return
End If

Dapatkan indeks titik yang terakhir kali dihitung untuk digunakan sebagai titik awal pada
perhitungan berikutnya

Dim idxTitikTerakhir As Integer = calonJalur(jumlahTitikTerpilih - 1)

Lakukan perhitungan pada masing-masing titik untuk titik-titik yang belum terpilih dan
memiliki jarak dengan titik terakhir

For i As Integer = 0 To jumlahTitik - 1

If titikTerpilih(i) = False AndAlso daftarBiaya(idxTitikTerakhir, i) <> 0 Then
...

Masukkan titik ini sebagai titik berikutnya pada calon jalur yang sedang dihitung
dan tandai titik ini sebagai titik yang sudah terpilih
calonJalur(jumlahTitikTerpilih) = i
titikTerpilih(i) = True

Lakukan proses percabangan / branch,

yaitu Ulangi fungsi ini menggunakan titik yang baru sebagai titik awal

CariJalur(jumlahTitik, rata2, daftarBiaya, jalurTerbaik, biayaTerbaik, titikTerpilih, _

calonJalur, totalCalonJalur + daftarBiaya(idxTitikTerakhir, i),
jumlahTitikTerpilih + 1)

Setelah semua kemungkinan cabang pada titik tersebut sudah dihitung,

maka keluarkan titik ini dari calon jalur yang sedang dihitung
dan tandai titik ini sebagai titik yang belum terpilih

calonJalur(jumlahTitikTerpilih) = -1
titikTerpilih(i) = False

Jika biaya jalur yang baru ditemukan lebih baik dari biaya jalur terbaik,
maka ambil jalur tersebut sebagai jalur terbaik

If biaya < biayaTerbaik Then

biayaTerbaik = biaya
[Link](jalur, jalurTerbaik, jumlahTitik)
End If
Jika diilustrasikan dalam gambar, maka model hasil akhirnya adalah sebagai berikut
  Pengertian DFS dan BFS

Depth-First Search (DFS)

Pencarian dilakukan pada satu node dalam setiap level dari yang paling kiri. Jika pada
level yang paling dalam, solusi belum ditemukan, maka pencarian dilanjutkan pada node
sebelah kanan. Node yang kiri dapat dihapus dari memori. Jika pada level yang paling
dalam tidak ditemukan solusi, maka pencarian dilanjutkan pada level sebelumnya.
Demikian seterusnya sampai ditemukan solusi. Jika solusi ditemukan maka tidak
diperlukan proses backtracking (penelusuran balik untuk mendapatkan jalur yang
dinginkan).

Kelebihan DFS adalah:

 Pemakain memori hanya sedikit, berbeda jauh dengan BFS yang harus menyimpan
semua node yang pernah dibangkitkan.
 Jika solusi yang dicari berada pada level yang dalam dan paling kiri, maka DFS
akan menemukannya secara cepat.

Kelemahan DFS adalah:

 Jika pohon yang dibangkitkan mempunyai level yang dalam (tak terhingga), maka
tidak ada jaminan untuk menemukan solusi (Tidak Complete).
 Jika terdapat lebih dari satu solusi yang sama tetapi berada pada level yang
berbeda, maka pada DFS tidak ada jaminan untuk menemukan solusi yang paling
baik (Tidak Optimal).

Breadth First Search(BFS)

Merupakan algoritma yang melakukan pencarian secara melebar yang mengunjungi

simpul secara preorder yaitu mengunjungi suatu simpul kemudian mengunjungi semua
simpul yang bertetangga dengan simpul tersebut terlebih dahulu. Selanjutnya, simpul yang
belum dikunjungi dan bertetangga dengan simpul-simpul yang tadi dikunjungi, demikian
seterusnya. algoritma BFS menggunakan graf sebagai media representasi persoalan,
tidak sulit untuk mengaplikasikan algoritma ini dalam persoalan-persoalan teori graf.

Cara Kerja Algoritma BFS

Dalam algoritma BFS, simpul anak yang telah dikunjungi disimpan dalam suatu antrian.
Antrian ini digunakan untuk mengacu simpul-simpul yan bertetangga dengannya yang
akan dikunjungi kemudian sesuai urutan pengantrian.

Untuk memperjelas cara kerja algoritma BFS beserta antrian yang digunakannya, berikut
langkah-langkah algoritma BFS:

1. Masukkan simpul ujung (akar) ke dalam antrian

2. Ambil simpul dari awal antrian, lalu cek apakah simpul merupakan solusi
3. Jika simpul merupakan solusi, pencarian selesai dan hasil dikembalikan.
4. Jika simpul bukan solusi, masukkan seluruh simpul yang bertetangga dengan
simpul tersebut (simpul anak) ke dalam antrian
5. Jika antrian kosong dan setiap simpul sudah dicek, pencarian selesai dan
mengembalikan hasil solusi tidak ditemukan
6. Ulangi pencarian dari langkah kedua
 BAB III

DAFTAR PUSTAKA

PIP. (2015, 10 24). Algoritma B&B (Branch and Bound). Retrieved from PIP Tools:
[Link]

Sutiono [Link]., M. M. (n.d.). Mengenal Algoritma Backtracking: Pengertian Dan Penggunaanya. Retrieved
from [Link]: [Link]

UDINUS, S. (n.d.). Pengertian DFS dan BFS. Retrieved from Student Blog UDINUS:
[Link]