8

BAB 2

LANDASAN TEORI

2.1 Algoritma

2.1.1 Definisi Algoritma

Algoritma berasal dari kata Algoris dan Ritmis, kata-kata tersebut berasal dari

seorang ahli matematika, Mohammed Ibn-Musa Al-Khawarizmi, yang merupakan

bagian dari royal court, Baghdad. Algoritma adalah sebuah prosedur yang terstruktur

dan dituliskan secara sistematis untuk menyelesaikan sebuah tugas, dimana

memberikan initial state (keadaan awal), dan akan terminate di akhir (end state)

dengan bantuan komputer.

Menurut Microsoft Press Computer and Internet Dictionary 1997,1998,

definisi algoritma adalah Urutan langkah logis tertentu untuk memecahkan suatu

masalah. Sedangkan dari Algoritma dan Struktur Data dengan C, C++, dan Java oleh

Moh. Sjukani, algoritma adalah Alur pemikiran dalam menyelesaikan suatu

pekerjaan yang dituangkan secara tertulis. Dari dua definisi diatas dapat disimpulkan

bahwa algoritma harus mengikuti suatu urutan aturan tertentu dan tidak boleh

melompat-lompat, dan algoritma seseorang dengan yang lain dapat berbeda-beda

karena mempunyai alur pikir yang berbeda-beda pula, serta Algoritma dapat berupa

kalimat, gambar atau tabel tertentu.

Dalam matematika dan komputasi, algoritma atau algoritme, merupakan

kumpulan perintah untuk menyelesaikan suatu masalah. Perintah-perintah ini dapat

diterjemahkan secara bertahap dari awal hingga akhir. Masalah tersebut dapat berupa

9

apa saja, dengan catatan untuk setiap masalah, ada kriteria kondisi awal yang harus

dipenuhi sebelum menjalankan algoritma. Algoritma akan dapat selalu berakhir

untuk semua kondisi awal yang memenuhi kriteria, dalam hal ini berbeda

dengan heuristik. Algoritma sering mempunyai langkah pengulangan (iterasi) atau

memerlukan keputusan (logika Boolean dan perbandingan) sampai tugasnya selesai.

2.1.2 Jenis-Jenis Algoritma

Beberapa paradigma yang digunakan dalam menyusun suatu

algoritma akan dipaparkan dibagian ini. Masing-masing paradigma dapat

digunakan dalam banyak algoritma yang berbeda, yaitu :

• Divide and Conquer, paradigma untuk membagi suatu permasalahan

besar menjadi permasalahan-permasalahan yang lebih kecil.

Pembagian masalah ini dilakukan terus menerus sampai ditemukan

bagian masalah kecil yang mudah untuk dipecahkan.

• Dynamic programming, paradigma pemrograman dinamik akan sesuai

jika digunakan pada suatu masalah yang mengandung sub-struktur

yang optimal, dan mengandung beberapa bagian permasalahan yang

tumpang tindih. Paradigma ini sekilas terlihat mirip dengan

paradigma Divide and Conquer, sama-sama mencoba untuk membagi

permasalahan menjadi sub permasalahan yang lebih kecil, tapi secara

intrinsik ada perbedaan dari karakter permasalahan yang dihadapi.

• Metode serakah, sebuah algoritma serakah mirip dengan

sebuah pemrograman dinamik, bedanya jawaban dari submasalah

tidak perlu diketahui dalam setiap tahap dan menggunakan pilihan

"serakah" apa yang dilihat terbaik pada saat itu.

10

2.1.3 Kompleksitas Algoritma, Waktu, Dan Masalah

Kompleksitas dari suatu algoritma merupakan ukuran seberapa

banyak komputasi yang dibutuhkan algoritma tersebut untuk mendapatkan

hasil yang diinginkan. Algoritma yang dapat memperoleh hasil yang

diinginkan dalam waktu yang singkat memiliki kompleksitas yang rendah,

sementara algoritma yang membutuhkan waktu yang lama untuk memperoleh

hasil tersebut mempunyai kompleksitas yang tinggi.

Biasanya kompleksitas algoritma dinyatakan secara asimptotik dengan

notasi big-O. Jika kompleksitas waktu untuk menjalankan suatu algoritma

dinyatakan dengan T(n), dan memenuhi T(n) ≤ C(f(n)) untuk n ≥ n0,

maka kompleksitas dapat dinyatakan dengan T(n) = O(f(n)).

Salah satu ukuran biaya dalam pengeksekusian sebuah algoritma

adalah lamanya waktu yang diperlukan. Pengukuran waktu yang diperlukan

dalam mengeksekusi suatu algoritma dinamakan kompleksitas waktu

algoritma tersebut (Liu, C.L, 1995, p272).

Dua buah algoritma yang berbeda dapat digunakan memecahkan

masalah yang sama dan mungkin saja, mempunyai kompleksitas waktu yang

sangat berbeda (Liu, C.L, 1995, p274). Kompleksitas waktu algoritma terbaik

untuk memecahkan masalah tersebut dinamakan sebagai kompleksitas waktu

suatu masalah (Liu, C.L, 1995, p277).

Ada dua buah klasifikasi permasalahan (Leahy, Billy., 2000, p21-24),

yaitu sebagai berikut :

1. Permasalahan yang dapat dipecahkan (decidable / solvable problem)

permasalahan yang termasuk klasifikasi ini adalah semua jenis

permasalahan yang mempunyai algoritma solusi, walaupun kadang kala

11

tidak praktis. Dari segi komputasi, permasalahan dalam klasifikasi ini

dapat dibedakan menjadi tiga kategori, yaitu :

1. Permasalahan Tractable (mudah dari segi komputasi)

Suatu masalah dikatakan tractable, jika masalah tersebut dapat

dipecahkan oleh suatu algoritma yang efisien. Contohnya,

masalah penentuan bilangan terbesar di antara n bilangan,

penentuan lintasan terpendek antara dua buah vertex di dalam

sebuah graph, dan lain sebagainya.

2. Permasalahan Intractable (sukar dari segi komputasi)

Suatu masalah dikatakan intractable, jika tidak ada algoritma

yang efisien untuk memecahkan masalah tersebut.

3. Permasalahan NP-Complete (NP singkatan dari Non-

Deterministik Polinomial)

Suatu masalah dikatakan NP-Complete apabila masalah itu

telah berhasil dibuktikan termasuk dalam masalah intractable.

Contohnya, permasalahan pewarnaan graph.

2. Permasalahan yang tidak dapat dipecahkan (undecidable / unsolvable

problem)

permasalahan yang termasuk dalam klasifikasi ini adalah semua

permasalahan yang tidak mempunyai aloritma solusi, maksudnya adalah

tidak dapat dilakukan perhitungan, atau tidak dapat diperoleh jawaban

dalam waktu terbatas. Contohnya, permasalahan unbounded tiling.

12

2.2 Definisi Optimasi

Optimasi secara umum adalah untuk memaksimalkan atau mengoptimalkan

sesuatu hal yang bertujuan untuk mengelola sesuatu yang dikerjakan, sehingga

optimasi bisa dikatakan kata benda yang berasal dari kata kerja, dan optimasi bisa

dianggap baik sebagai ilmu pengetahuan dan seni menurut tujuan yang ingin

dimaksimalkan. (Dunia optimasi, optimasi, 2011)

Optimasi (Wikipedia, optimasi, 2012) adalah suatu proses untuk mencapai

hasil yang ideal atau optimal (nilai efektif yang dapat dicapai). Dalam disiplin

matematika, optimasi merujuk pada studi permasalahan yang mencoba untuk

mencari nilai minimum dan maksimum dari suatu fungsi nyata. Untuk mencapai nilai

minimum dan maksimum tersebut, secara sistematis dilakukan pemilihan integer

atau bilangan nyata yang akan memberikan solusi yang optimal.

Sedangkan menurut Kamus Besar Bahasa Indonesia, optimasi adalah

prosedur yang digunakan untuk membuat sistem atau desain yang fungsional atau

seefektif mungkin dengan menggunakan teknik aplikasi matematika.

Dalam matematika dan ilmu komputer, sebuah masalah optimasi adalah

masalah untuk menemukan solusi terbaik dari semua solusi. Masalah optimasi dapat

dibagi menjadi dua kategori tergantung pada apakah variabel yang kontinyu atau

diskrit. Masalah optimasi dengan variabel diskrit dikenal sebagai masalah optimasi

kombinatorial . Dalam masalah optimasi kombinatorial, kami sedang mencari sebuah

benda seperti grafik integer, permutasi atau dari himpunan berhingga (atau mungkin

dihitung tak terbatas).

13

2.3 Gambaran Umum tentang Label Kertas Atau Plastik

2.3.1 Definisi Label

Dalam membuka sebuah usaha, adanya label pada produk yang

dihasilkan sangatlah penting. Pada produk pakaian, makanan, minuman,

elektronik, dan sebagainya, peran label sangat membantu produsen

mengenalkan produk yang dihasilkan kepada para konsumen. Sehingga para

konsumen dapat mengetahui produk yang ingin digunakannya.

Menurut Wikipedia, label adalah sepotong kertas, polymer, kain,

logam, atau bahan lain yang ditempelkan pada wadah atau benda yang

dicetak sebagai informasi produk, alamat, dan lain-lain. Label juga dapat

langsung dicetak pada wadah atau benda. Sedangkan, pelabelan adalah setiap

komunikasi tertulis, elektronik, atau gambar pada kemasan atau terpisah dari

label terkait.

Dalam sistem online komputer, label (tag) adalah kata kunci non

hierarki atau tidak bertingkat yang tugasnya adalah menunjukkan potongan-

potongan informasi (seperti petunjuk internet, gambar digital, atau file

komputer). Label merupakan jenis metadata yang membantu untuk

menjelaskan suatu hal dan memungkinkan hal tersebut ditemukan ketika

melakukan pencarian (browsing).

Gambar 2.1 Macam-macam label kertas

14

Tujuan utama dari label sebagai daya tarik calon pelanggan untuk

mengetahui sebuah produk dan membuat produk terkesan unik. Label sebuah

produk juga sebagai pencitraan dari sebuah perusahaan yang menghasilkan

produk tersebut, menyampaikan pesan perusahaan kepada konsumen, serta

membedakan produknya dengan produk dari perusahaan lainnya. Fungsi dari

label adalah menyajikan identitas perusahaan dan identitas produk.

2.3.2 Aturan Pembuatan Label Kemasan

Merancang atau mendesain label kemasan sangatlah tergantung pada

kreativitas para desainernya, baik ukuran, bentuk, maupun corak warnanya.

Namun demikian ada hal-hal yang harus diperhatikan dalam membuat label

kemasan yaitu :

1. Label tidak boleh menyesatkan, apa saja yang tercantum dalam sebuah

label baik berupa kata-kata, kalimat, nama, lambang, logo, gambar

dan lain sebagainya harus sesuai dengan produk yang ada di

dalamnya.

2. Memuat informasi yang diperlukan label sebaiknya cukup besar

(relatif terhadap kemasannya), sehingga dapat memuat informasi atau

keterangan tentang produknya.

3. Hal-hal yang seharusnya ada atau tercantum dalam label produk

makanan adalah sebagai berikut :

a. Nama produk

Nama Produk adalah nama dari makanan atau produk pangan

yang terdapat di dalam kemasan misalnya dodol nanas, keripik

pisang, keripik singkong dan lain sebagainya.

15

b. Cap / Trade mark bila ada

Suatu usaha sebaiknya memiliki cap atau trade mark atau merek

dagang. Cap berbeda dengan nama produk dan bisa tidak

berhubungan dengan produk yang ada di dalamnya misalnya

dodol nanas cap “Panda”, Kecap Ikan cap “Wallet”, dsb.

c. Komposisi / daftar bahan yang digunakan

Komposisi atau daftar bahan merupakan keterangan yang

menggambarkan tentang semua bahan yang digunakan dalam

pembuatan produk makanan tersebut. Cara penulisan komposisi

bahan penyusun dimulai dari bahan mayor atau bahan utama atau

bahan yang paling banyak digunakan sampai yang terkecil.

d. Netto atau volume bersih

Netto atau berat bersih dan volume bersih menggambarkan bobot

atau volume produk yang sesungguhnya. Apabila bobot produk

berarti bobot produk yang sesungguhnya tanpa bobot bahan

pengemas.

e. Nama pihak produksi

Nama pihak produksi adalah nama perusahaan yang membuat atau

mengolah produk makanan tersebut.

f. Distributor atau pihak yang mengedarkan bila ada

Dalam kemasan juga harus mencantumkan pihak-pihak tertentu

seperti pengepak atau importir bila ada.

g. Nomor Registrasi Dinas Kesehatan

Nomor registrasi ini sebagai bukti bahwa produk tersebut telah

teruji dan dinyatakan aman untuk dikonsumsi.

16

h. Kode Produksi

Kode produksi adalah kode yang menyatakan tentang batch

produksi dari produk pada saat pembuatan yang isinya tanggal

produksi dan angka atau hurup lainnya yang mencirikan dengan

jelas produk tersebut.

i. Keterangan kadaluarsa

Keterangan kadaluarsa adalah keterangan yang menyatakan umur

produk yang masih layak untuk dikonsumsi. Menurut Julianti dan

Nurminah (2006), keterangan kadaluarsa dapat ditulis :

• Best before date : produk masih dalam kondisi baik dan

masih dapat dikonsumsi beberapa saat setelah tanggal yang

tercantum terlewati.

• Use by date : produk tidak dapat dikonsumsi, karena

berbahaya bagi kesehatan manusia (produk yang sangat

mudah rusak oleh mikroba) setelah tanggal yang tercantum

terlewati.

j. Logo halal

Untuk produk-produk yang telah mendapatkan sertifikasi “halal”

dari MUI harus mencantumkan logo halal yang standard disertai

dengan nomor sertifikasinya.

k. Keterangan Lainnya

Selain yang telah diuraikan di atas masih ada lagi keterangan-

ketrangan lain yang perlu dicantumkan dalam label kemasan

makanan yang bermaksud memberi petunjuk, saran, atau yang

lainnya demi keamanan konsumen.

17

4. Tulisan atau keterangan yang ada

Tulisan atau keterangan yang ada pada label harus jelas dan mudah di

baca, tidak dikaburkan oleh warna latar belakang atau gambar lainnya.

5. Jumlah warna yang digunakan

Banyaknya warna yang digunakan dalam label akan berpengaruh

terhadap biaya cetak, semakin banyak banyak warna yang digunakan,

tentunya akan semakin besar biaya yang harus dikeluarkan.

6. Jenis cetakan yang dikehendaki

Desain yang kita buat akan dicetak pada media apa? Plastik, kertas,

aluminium foil, atau lainnya. Apakah akan dicetak dengan sablon atau

menggunakan mesin modern.

2.3.3 Macam – Macam Label

Terdapat 3 (tiga) macam label menurut Stanton (1994), yaitu:

1. Brand Label

Label ini memuat merk, gambar, atau produsen dari produk yang

dicantumkan dalam kemasan produk. Informasi tersebut penting bagi

konsumen sehingga mereka dapat membedakan suatu produk dengan

produk lainnya.

2. Descriptive Label

Label ini memberikan informasi mengenai bahan baku, persentase

kandungan, nilai kalori/gizi, cara penggunaan/konsumsi, tanggal

pembuatn, tanggal kedaluarsa dll.

18

3. Grade Label

Label ini menginformasikan kepada konsumen tentang penilaian

kualitas produk.

2.4 Pencarian

Pencarian (Munir, 2009) merupakan kegiatan mendefinisikan ruang masalah

untuk masalah yang dihadapi. Ruang masalah ini dapat digambarkan sebagai

himpunan keadaan (state) atau bisa juga sebagai himpunan rute dari keadaan awal

(initial state) menuju keadaan tujuan (goal state).

Ada dua metode pencarian (searching), yaitu :

1. Blind atau un-informed search (pencarian buta atau tidak berbekal

informasi)

2. Heuristic atau informed search (pencarian dengan berbekal informasi)

2.5 Gambaran Umum Peletakan Posisi Label

Peletakan posisi label menggunakan metode A* heuristic dengan cara

matematis menempatkan label dengan berbagai macam pola dua dimensi pada

sebuah bin atau alas dasar, dalam kasus ini seperti kertas atau plastik. Tujuan dari

program peletakan posisi label ini adalah meminimalkan penggunaan kertas atau

plastik untuk menampung sejumlah pola label yang dibutuhkan.

Nilai dari sebuah pola adalah pasti, tidak nol, dan memiliki nilai yang positif

akan mempermudah cara dan melakukan perhitungan untuk menempatkannya dalam

bin atau pada kasus ini sebuah alas kertas atau plastik. Bin adalah ukuran yang pasti

dari kertas atau plastik sebagai alas dasar untuk penempatan sejumlah pola label.

19

Terdapat banyak variasi dalam masalah optimasi peletakkan posisi label ini,

seperti linear packing, packing by weight, packing by cost, dan lain sebagainya.

Karena masalah ini termasuk ke dalam NP-Hard, maka algoritma yang diketahui

efisien adalah heuristic. Penggunaan heuristic bertujuan untuk mendapatkan hasil

yang baik dalam kebanyakan kasus, tetapi mungkin saja buka sebagai optimasi yang

paling optimal. Heurisitic adalah sebuah algoritma yang mungkin saja menemukan

solusi yang baik, tetapi tidak ada bukti bahwa solusinya tidak bisa menjadi buruk

secara tidak masuk akal dan tidak ada argumen tentang hal ini bahwa hal seperti ini

mungkin saja terjadi.

2.6 NP-Hard

Menurut Wikipedia (2013), dalam teori “computational complexity”, NP

(Non-deterministic Polynomial time) adalah sekumpulan permasalahan yang dapat

dipecahkan menggunakan polynomial time – non-deterministic turing machine.

Turing machines merupakan symbol abstrak dasar yang memanipulasi alat dimana

dapat disesuaikan untuk mensimulasi logika dari komputer yang secara mungkin

dapat dikonstruksi.

Hal ini dikemukakan pada tahun 1936 oleh Alan Turing, polynomial time

adalah permasalahan waktu komputasi (ukuran berapa banyak langkah yang

digunakan perangkat keras atau sistem perangkat lunak dalam pengkomputasi-

pemrosesan informasi). Polynomial adalah sebuah pernyataan yang terbentuk dari

satu atau lebih variable dan konstanta, dan hanya menggunakan penjumlahan,

pengurangan, serta perkalian.

20

Sebuah kelas yang kompleks dari decision problems di mana pada dasarnya

lebih sulit dari pada masalah yang biasa diselesaikan dengan non-deterministic turing

machine dalam polynomial time. Terdapat tiga kelas permasalahan(problem), yaitu :

• P adalah kumpulan “yes/no” problem yang bisa dipecahkan dalam waktu

polynomial. Jadi bisa dikatakan bahwa P adalah kumpulan permasalahan

yang bisa dipecahkan secara cepat.

• NP adalah sekumpulan “yes/no” problem diikuti dengan property : jika

“yes” maka ada pembuktian dari fakta itu yang bisa dicek dalam waktu

polynomial. Jadi bisa dikatakan bahwa NP adalah sekumpulan

permasalahan di mana bisa dikatakan “yes”, jika terdapat solusinya.

• Co-NP adalah kebalikan dari NP, jika jawaban dari permasalahan co-NP

adalah “no” maka ada pembuktian dari fakta itu yang bisa dicek dalam

waktu polynomial.

Gambar 2.2 Hubungan antara P, NP, dan co-NP

2.7 Metode Pencarian Heuristic

Menurut Munir (2009), heuristic berasal dari sebuah kata kerja Yunani,

heuriskein yang berarti mencari atau menemukan. Dalam dunia pemrograman,

sebagian orang menggunakan kata heuristic sebagai lawan kata dari algoritmik,

dimana kata heuristic ini diartikan sebagai proses yang mungkin dapat

21

menyelesaikan suatu masalah tetapi tidak ada jaminan bahwa solusi yang dicari

selalu dapat ditemukan.

Heuristic memperbaiki proses pencarian solusi walaupun tidak harus sampai

mengatasi kasus terburuk (worst case scenario). Heuristic ini mengembangkan

efisiensi dalam proses pencarian, namun dengan kemungkinan mengorbankan

kelengkapan (completeness). Algoritma ini biasanya mencari solusi yang dekat

dengan solusi yang terbaik dan proses pencariannya cepat dan mudah. Fungsi

heuristic h(n) adalah perkiraan biaya termurah dari node n ke node tujuan. Fungsi

heuristic melambangkan cost yang akan dikeluarkan agent, jika memilih node

tertentu.

Heuristic adalah sebuah algoritma yang mungkin saja menemukan solusi

yang baik tetapi tidak ada bukti bahwa solusinya tidak bisa menjadi buruk secara

tidak masuk akal, dan tidak ada argument tentang ini bahwa hal ini mungkin saja bisa

terjadi.

Fungsi heuristic yang sempurna akan membuat algoritma A* langsung

menuju final node tanpa harus mencari ke arah lain. Sehingga jika fungsi heuristic-

nya terlalu underestimate akan menyebabkan algoritma ini beranggapan bahwa ada

rute yang lebih baik dari rute yang ada. Untuk fungsi heuristic yang underestimate,

bila nilainya terlalu rendah akan menyebabkan algoritma ini seperti algoritma

Dijkstra yang mencari kesegala arah yang mungkin. Hal ini dikarenakan tidak

cukupnya informasi mengenai masalah yang dihadapi, sehingga menyebabkan

algoritma A* melakukan pencarian lebih banyak dan lebih lama.

22

2.8 Best First Search

2.8.1 Pengertian Best First Search

Best First Search merupakan sebuah metode yang

membangkitkan simpul dari simpul sebelumnya. Best first search

memilih simpul baru yang memiliki biaya terkecil diantara semua

leaf nodes (simpul-simpul pada level terdalam) yang pernah

dibangkitkan. Penentuan simpul terbaik dilakukan dengan

menggunakan sebuah fungsi yang disebut fungsi

evaluasi f(n). fungsi evaluasi best first search dapat berupa biaya

perkiraan dari suatu simpul menuju ke goal atau gabungan antara

biaya sebenarnya dan biaya perkiraan tersebut.

Pada setiap langkah proses pencarian terbaik pertama, kita

memilih node-node dengan menerapkan fungsi heuristik yang

memadai pada setiap node yang kita pilih dengan menggunakan

aturan-aturan tertentu untuk menghasilkan penggantinya. Fungsi

heuristic merupakan suatu strategi untuk melakukan proses

pencarian ruang keadaan suatu problema secara selektif, yang

memandu proses pencarian yang kita lakukan sepanjang jalur yang

memiliki kemungkinan sukses paling besar.

Ada beberapa istilah yang sering digunakan pada metode

best first search, yaitu:

1. Start node adalah sebuah terminology untuk posisi awal

sebuah pencarian.

2. Curret node adalah simpul yang sedang dijalankan dalam

algoritma pencarian jalan terpendek.

23

3. Suksesor adalah simpul-simpul yang yang akan diperiksa

setelah current node.

4. Simpul (node) merupakan representasi dari area

pencarian.

5. Open list adalah tempat menyimpan data simpul yang

mungkin diakses dari starting node maupun simpul yang

sedang dijalankan.

6. Closed list adalah tempat menyimpan data simpul yang

juga merupakan bagian dari jalur terpendek yang telah

berhasil didapatkan.

7. Goal node yaitu simpul tujuan.

8. Parent adalah curret node dari suksesor.

2.8.2 Langkah-Langkah Algoritma Best First Search

Pertama kali, dibangkitkan node A. Kemudian semua suksesor

A dibangkitan, dan dicari harga paling minimal. Pada langkah 2,

node D terpilih karena harganya paling rendah, yakni 1. Langkah 3,

semua suksesor D dibangkitkan, kemudian harganya akan

dibandingkan dengan harga node B dan C. Ternyata harga node B

paling kecil dibandingkan harga node C, E, dan F. Sehingga B

terpilih dan selanjutnya akan dibangkitkan semua suksesor B.

Demikian seterusnya sampai ditemukan node tujuan. Ilustrasi

algoritma best first search dapat dilihat pada gambar 2.3 dibawah

ini.

24

Gambar 2.3 Langkah-Langkah Algoritma Best First Search

Untuk mengimplementasikan algoritma pencarian ini,

diperlukan dua buah senarai, yaitu: OPEN untuk mengelola node-

node yang pernah dibangkitkan tetapi belum dievaluasi dan CLOSE

untuk mengelola node-node yang pernah dibangkitkan dan sudah

dievaluasi. Algoritma selengkapnya adalah sebagai berikut :

1. OPEN berisi initial state dan CLOSED masih kosong.

2. Ulangi sampai goal ditemukan atau sampai tidak ada di

dalam OPEN.

a. Ambil simpul terbaik yang ada di OPEN.

b. Jika simpul tersebut sama dengan goal, maka

sukses.

c. Jika tidak, masukkan simpul tersebut ke dalam

CLOSED.

d. Bangkitkan semua aksesor dari simpul tersebut.

25

e. Untuk setiap suksesor kerjakan:

i. Jika suksesor tersebut belum pernah

dibangkitkan, evaluasi suksesor tersebut,

tambahkan ke OPEN, dan catat parent.

ii. Jika suksesor tersebut sudah pernah

dibangkitkan, ubah parent-nya jika jalur

melalui parent ini lebih baik daripada jalur

melalui parent yang sebelumnya.

Selanjutnya perbarui biaya untuk suksesor

tersebut dan nodes lain yang berada di level

bawahnya.

2.8.3 Algoritma Yang Menggunakan Metode Best First Search

Algoritma yang menggunakan metode best first search,

yaitu:

a. Greedy Best First

Greedy Best First adalah algoritma best first yang paling

sederhana dengan hanya memperhitungkan biaya perkiraan

(estimated cost) saja, yakni f(n) = h(n). Biaya yang

sebenarnya (actual cost) tidak diperhitungkan. Dengan hanya

memperhitungkan biaya perkiraan yang belum tentu

kebenarannya, maka algoritma ini menjadi tidak optimal.

26

b. A*

A* adalah algoritma best first search yang

menggabungkan Uniform Cost Search dan Greedy Best First

Search. Biaya yang diperhitungkan didapat dari biaya

sebenarnya ditambah dengan biaya perkiraan. Dalam notasi

matematika dituliskan sebagai f(n)= g(n) + h(n). Dengan

perhitungan biaya seperti ini, algoritma A* adalah

complete dan optimal.

2.9 Metode A* Heuristic

Metode A* adalah salah satu contoh dari metode best first search. Metode A*

dikembangkan pada tahun 1968 oleh Peter Hart, Nils Nilsson, dan Bertram Raphael,

mereka juga menyebut metode tersebut dengan sebutan algoritma A, dengan metode

ini dan fungsi heuristic yang tepat menghasilkan sebuah hasil yang optimal, yaitu

A*.

Dalam ilmu komputer, A* (dibaca : A star) adalah sebuah graph atau metode

tree search yang digunakan untuk mencari jalan dari sebuah node awal ke node

tujuan yang telah ditentukan, metode ini mengunakan “estimasi heuristic” h(n) pada

setiap node untuk mengurutkan setiap node n berdasarkan estimasi rute terbaik yang

melalui node tersebut.

Metode A* hanya membangun rute yang mungkin digunakan untuk mencapai

tujuan. Untuk mengetahui rute mana yang memungkinkan mengarah ke titik akhir,

A* menggunakan estimasi heuristik jarak dari sembarang node ke node tujuan.

Prinsip algoritma ini adalah mencari jalur terpendek dari sebuah simpul awal

(starting point) menuju simpul tujuan dengan memperhatikan harga (F) terkecil.

27

Secara umum, Depth First Search (DFS) dan Breadth First Search (BFS)

adalah dua kasus spesial dari metode A*. Algoritma Dijkstra’s merupakan kasus

spesial dari A*, dimana h(n) = 0, untuk semua n.

2.9.1 Pseudocode Algoritma A*

Gambar 2.4 Pseudocode algoritma A* (Patel, 2011)

Beberapa terminologi dasar yang terdapat pada algoritma ini adalah starting

point, simpul (nodes), A, open list, closed list, harga (cost), dan rintangan

(unwalkable).

• Starting point adalah sebuah terminologi posisi awal sebuah benda.

• A adalah simpul yang sedang dijalankan algortima pencarian jalan terpendek.

• Simpul adalah petak-petak kecil sebagai representasi dari area pathfinding.

Bentuknya dapat berupa persegi, lingkaran, maupun segitiga.

28

• Open list adalah tempat menyimpan data simpul yang mungkin diakses dari

starting point maupun simpul yang sedang dijalankan.

• Closed list adalah tempat menyimpan data simpul sebelum A yang juga

merupakan bagian dari jalur terpendek yang telah berhasil didapatkan.

• Harga (F) adalah nilai yang diperoleh dari penjumlahan nilai G, jumlah nilai

tiap simpul dalam jalur terpendek dari starting point ke A, dan H, jumlah nilai

perkiraan dari sebuah simpul ke simpul tujuan.

• Simpul tujuan yaitu simpul yang dituju.

• Rintangan adalah sebuah atribut yang menyatakan bahwa sebuah simpul tidak

dapat dilalui oleh A.

Algoritma A* dapat dijelaskan dengan pseudocode dibawah ini :

1. Masukan node awal ke open list

2. Loop Langkah – langkah di bawah ini :

a. Cari node n dengan nilai f(n) yang paling rendah dalam open list.

Node ini sekarang menjadi current node.

b. Keluarkan current node dari open list dan masukan ke close list.

c. Untuk setiap tetangga dari current node lakukan berikut :

• Jika tidak dapat dilalui atau sudah ada dalam close list,

abaikan.

• Jika belum ada di open list. Buat current node parent dari

node tetangga ini. Simpan nilai f, g, dan h dari node ini.

• Jika sudah ada di open list, cek bila node tetangga ini lebih

baik, menggunakan nilai g sebagai ukuran. Jika lebih baik

ganti parent dari node ini di open list menjadi current

node, lalu kalkulasi ulang nilai g dan f dari node ini.

29

d. Hentikan loop jika :

• Node goal telah ditambahkan ke openlist, yang berarti rute

telah ditemukan.

• Belum menemukan node goal sementara open list kosong

atau berarti tidak ada rute.

3. Simpan rute. Secara ‘backward’, urut mulai dari node goal ke parent-nya

terus sampai mencapai node awal sambil menyimpan node ke dalam

sebuah array. (http://grobvater.blogspot.com/2011/03/pathfinding-

algoritma-pencarian-rute.html)

Dalam masalah pencarian rute dimana metode A* sering digunakan, A*

secara bertahap membangun semua rute yang mengarah mulai dari titik awal

sampai akhirnya mencapai titik akhir. Metode A* hanya membangun rute yang

mungkin digunakan untuk mencapai tujuan. Untuk mengetahui rute mana yang

memungkinkan mengarah ke titik akhir, A* menggunakan estimasi heuristic jarak

dari sembarang node ke node tujuan. Dalam kasus pencarian rute, ini bisa jadi

sama dengan jarak lurus antara dua titik, dimana biasanya merupakan perkiraan

dari jarak jalan.

2.9.2 Fungsi A* Heuristic

Fungsi adalah aturan yang menugaskan sebuah output untuk tiap-tiap

input yang diberikan. Aturan mendefinisikan suatu fungsi dapat

dispesifikasikan oleh suatu formula, relasi, atau tabel yang mendaftar output

terhadap input. Pola terpenting dari suatu fungsi adalah ia bersifat

deterministic, yakni selalu menghasikan output yang sama dari input yang

30

sama. Input sering disebut argumen fungsi, sedangkan output disebut nilai

fungsi.

Fungsi heuristic digunakan untuk mengevaluasi keadaan-keadaan

problema individual dan menentukan seberapa jauh hal tersebut dapat

digunakan untuk mendapatkan solusi yang diinginkan.

Menurut Amit. J. Patel (2003, p1), heuristic merupakan aturan-aturan

untuk memilih cabang-cabang yang memiliki kemungkinan mengarah pada

pemecahan masalah. Heuristic dapat membantu menunjukkan arah yang tepat

bagi suatu algoritma, tetapi mungkin juga gagal dalam memberikan petunjuk

kepada algoritma tersebut.

h(x) bagian dari f(x) fungsi harus menjadi heuristik diterima, yaitu

tidak harus melebih-lebihkan jarak ke tujuan. Jadi, untuk aplikasi

seperti routing , h(x) mungkin mewakili garis lurus jarak ke tujuan, karena itu

adalah fisik yang mungkin jarak terkecil antara dua titik atau node.

Jika heuristik h memenuhi kondisi tambahan untuk setiap sisi ( x,

y ) dari grafik (di mana d menunjukkan panjang tepi itu),

maka h disebut monoton, atau konsisten . Dalam kasus seperti itu, A* dapat

dilaksanakan dengan lebih efisien-berbicara kasar, tidak ada node perlu

diproses lebih dari sekali (lihat ditutup ditetapkan di bawah) dan A* setara

dengan menjalankan algoritma Dijkstra dengan mengurangi biaya d '(x, y): =

d (x, y) - h (x) + h (y).

Seperti pencarian breadth-first , A * adalah lengkap dan akan selalu

menemukan solusi jika ada. Jika heuristik fungsi h adalah diterima , artinya tidak

pernah overestimates biaya minimal sebenarnya mencapai tujuan, maka A * itu

sendiri diterima (atau optimal ) jika kita tidak menggunakan satu set tertutup. Jika

31

suatu himpunan tertutup digunakan, maka h juga harus monoton (atau konsisten )

untuk A* menjadi optimal. Ini berarti bahwa untuk setiap pasangan node yang

berdekatan x dan y , di mana d (x, y) menunjukkan panjang tepi antara mereka, kita

harus memiliki:

Hal ini memastikan bahwa untuk setiap jalur X dari node awal untuk x :

di mana L adalah fungsi yang menunjukkan panjang jalan, dan Y adalah

jalur X diperluas untuk mencakup y . Dengan kata lain, tidak mungkin untuk

mengurangi (jarak total sejauh + perkiraan jarak yang tersisa) dengan memperluas

jalan untuk memasukkan node tetangga. (Hal ini analog dengan pembatasan bobot

tepi nonnegatif dalam algoritma Dijkstra .) monotonicity menyiratkan diterimanya

ketika perkiraan heuristik pada setiap node tujuan itu sendiri adalah nol, karena

(membiarkan P = (f, v 1 , v 2 , ..., v n , g) menjadi jalan terpendek dari node f untuk

tujuan terdekat g ):

A * juga efisien secara optimal untuk setiap heuristik h , yang berarti bahwa

tidak ada algoritma yang optimal mempekerjakan heuristik yang sama akan

memperluas node kurang dari A *, kecuali ketika ada beberapa solusi parsial di

mana h tepatnya memprediksi biaya jalur yang optimal. Bahkan dalam kasus ini,

untuk setiap grafik ada ada beberapa urutan memutuskan hubungan dalam antrian

prioritas seperti bahwa A * memeriksa paling sedikit mungkin node.

Sedangkan kriteria diterimanya menjamin jalur solusi optimal, itu juga

berarti bahwa A* harus memeriksa semua jalan sama berjasa untuk

menemukan jalur yang optimal. Hal ini dimungkinkan untuk mempercepat

pencarian dengan mengorbankan optimalitas dengan relaksasi kriteria

32

diterimanya. Seringkali kita ingin terikat relaksasi ini, sehingga kami dapat

menjamin bahwa jalan solusi tidak lebih buruk daripada (1 + ε) kali jalan

solusi optimal. Ini jaminan baru ini disebut sebagai ε -diterima.

Ada sejumlah ε algoritma diterima:

• Tertimbang A*. Jika h (n) adalah fungsi heuristik diterima,

dalam versi tertimbang dari A* pencarian satu menggunakan h w (n) = ε

h (n) , ε> 1 sebagai fungsi heuristik, dan melakukan pencarian A * seperti

biasa (yang akhirnya terjadi lebih cepat daripada menggunakan h a sejak

kurang node diperluas). Jalan maka ditemukan oleh algoritma pencarian dapat

memiliki biaya paling ε kali dari jalur biaya termurah dalam grafik.

• Static Bobot menggunakan biaya fungsi f (n) = g (n) + (1 + ε)

h (n) .

• Dinamis Bobot menggunakan biaya fungsi f (n) = g (n) + (1 +

ε w (n)) h (n) , di mana , dan di

mana d(n) adalah kedalaman pencarian dan N adalah panjang diantisipasi dari

jalur solusi.

• Sampel Pembobotan Dinamis menggunakan sampling node

untuk estimasi yang lebih baik dan debias kesalahan heuristik.

• . menggunakan dua fungsi heuristik. Yang pertama adalah

daftar FOCAL, yang digunakan untuk memilih node calon, dan yang

kedua h F digunakan untuk memilih node yang paling menjanjikan dari daftar

FOCAL.

33

• A ε Memilih node dengan fungsi A f (n) + B h F (n) , di

mana A dan B adalah konstanta. Jika tidak ada node dapat dipilih, algoritma

akan mundur dengan fungsi C f (n) + D h F (n) , di mana C dan D adalah

konstanta.

• A* upaya untuk mempromosikan eksploitasi mendalam-

pertama dengan memilih node baru ini diperluas. Alpha * menggunakan

fungsi biaya f α (n) = (1 + w α (n)) f (n) , di

mana , di mana λ dan Λ adalah

konstanta dengan , π (n) adalah induk dari n, dan ñ adalah paling baru

memperluas simpul.

kompleksitas waktu dari A* tergantung pada heuristik. Dalam kasus

terburuk, jumlah node diperluas adalah eksponensial dalam panjang dari

solusi (jalan terpendek), tetapi polinomial ketika ruang pencarian adalah

pohon, ada negara tujuan tunggal, dan fungsi heuristik h memenuhi Kondisi

berikut:

di mana h * adalah heuristik

optimal, biaya yang tepat untuk mendapatkan dari x ke tujuan. Dengan kata

lain, kesalahan h tidak akan tumbuh lebih cepat daripada logaritma dari

"heuristik yang sempurna" h * yang mengembalikan jarak yang benar

dari x ke tujuan.

A* mempertahankan sebagian dari solusi, sebagai contoh jalur pada

graph dimulai dari node awal, dan akan disimpan dalam sebuah queue yang

34

disebut priority queue. Prioritas yang diberikan ke sebuah jalur n ditentukan

oleh fungsi :

f(n) = g(n) + h(n)

Dimana, g(n) adalah nilai cost dari path yang telah ditemukan, yaitu

berat atau bobot dari jalur antar node yang telah dilalui. h(n) adalah estimasi

heuristic dari nilai cost paling minimal yang digunakan atau didapat untuk

menapai goal dari n. semakin besar nilai f(n), maka semakin besar

prioritasnya.

Pada kasus ini, fungsi f(n) = g(n) + h(n) didefinisikan sebagai berikut:

• g(n) adalah heuristic luas

g(n) = width_pola * height_pola

Perhitungan ini untuk menentukan pola label mana yang akan

diletakkan pertama kali.

• h(n) adalah fungsi heuristic

h(n) = (((kel_alas – batas_alas) + (kel_pola – batas_alas)) –

pola_dempet) + nilai_tambahan

nilai h(n) pertama dibandingkan dengan h(n) yang lainnya,

hingga ditemukan nilai h(n) yang paling minimal.

o kel_alas = keliling alas kertas atau plastik

o batas_alas = pola label yang terkena pembatas alas

o kel_pola = keliling pola label

o pola_dempet = pola label yang saling berdempetan

o nilai_tambahan = pemberian nilai tambah agar tidak

saling bersinggungan/berdempetan.

35

2.9.3 Perbandingan Fungsi A* Heuristic

Beberapa fungsi heuristic yang umum digunakan pada algoritma

pathfinding A* adalah sebagai berikut :

1. Manhattan Distance

Manhattan distance adalah fungsi heuristic standar untuk

algoritma A*. Digunakan pada aplikasi yang memiliki 4 arah

gerakan (tidak dapat bergerak diagonal). Rumus manhattan

distance :

h(n) = d * (abs(xn – xgoal) + abs(yn – ygoal))

Dimana :

• d adalah nilai biaya. d didapat dari nilai minimum cost

perpindahan antar node.

• xn adalah koordinat x dari node pertama pada grid.

• xgoal adalah koordinat x dari final node.

• yn adalah koordinat y dari node pertama pada grid.

• ygoal adalah koordinat y dari final node.

Berikut adalah kelebihan dari penggunaan fungsi heuristic

manhattan distance :

• Semua jalur-jalur dapat ditemukan (masalah dapat

dipecahkan).

• Hal ini disebabkan karena pada setiap penambahan nilai

g(n), pada perhitungan nilai heuristic-nya terjadi pula

perubahan pada nilai d-nya. Sehingga dengan penambahan

nilai g(n), tidak mempengaruhi pencarian jalur.

36

• Dengan menggunakan fungsi heuristic manhattan

distance, didapatkan nilai iterasi dan jumlah langkah yang

paling kecil dibanding dengan menggunakan fungsi

heuristic yang lainnya.

2. Straight Line Distance

Straight line distance adalah fungsi heuristic yang digunakan

pada aplikasi yang dapat bergerak ke segala arah/sudut. Rumus

straight line distance :

h(n) = sqrt((xn – xgoal)2 + (yn – ygoal)

2)

Dimana :

• xn adalah koordinat x dari node pertama pada grid.

• xgoal adalah koordinat x dari final node.

• yn adalah koordinat y dari node pertama pada grid.

• ygoal adalah koordinat y dari final node.

Kekurangan penggunaan fungsi heuristic straight line distance,

yaitu :

• Masalah tidak semua dapat dipecahkan. Terutama pada

pengujian dengan menggunakan nilai g(n) yang besar.

• Dalam algoritma A* dengan fungsi heuristic straight line

distance, apabila terdapat sedikit hambatan pada ruang

pencarian maka walaupun ditemukan jalurnya, pasti

membutuhkan banyak iterasi.

• Kesulitan pencarian jalur tersebut, terjadi karena dalam

perhitungan nilai fungsinya, yaitu h(n) = sqrt((xn – xgoal)2

+ (yn – ygoal)2), maka nilai yang dihasilkan kecil sehingga

37

dalam pencarian nilai f(n), banyak dipengaruhi oleh

besarnya nilai g(n). Hal ini dapat dilihat, semakin besar

nilai g(n) maka semakin kecil pengaruh nilai fungsi

heuristic tersebut terhadap pencarian nilai f(n), karena

nilai fungsi heuristic pada setiap pengujian tersebut

nilainya tetap sedangkan nilai g(n) semakin besar, maka

nilai fungsi heuristic tersebut semakin tidak berpengaruh.

Dimana nilai pencarian tersebut digunakan dalam memilih

node yang akan dimasukkan kedalam close list.

• Karena alasan diatas, dapat disimpulkan bahwa fungsi

heuristic straight line distance memiliki lebih banyak

iterasi dibanding fungsi heuristic yang lain.

3. Diagonal Distance

Diagonal distance adalah fungsi heuristic yang digunakan pada

aplikasi yang memiliki delapan arah gerakan (dapat bergerak

diagonal). Rumus diagonal distance :

h(n) = d * max (abs(xn – xgoal), abs(yn – ygoal))

Dimana :

• d adalah nilai biaya. d didapat dari nilai minimum cost

perpindahan antar node.

• xn adalah koordinat x dari node pertama pada grid.

• xgoal adalah koordinat x dari final node.

• yn adalah koordinat y dari node pertama pada grid.

• ygoal adalah koordinat y dari final node.

38

Kelebihan penggunaan fungsi heuristic diagonal distance, yaitu :

• Semua jalur-jalur dapat ditemukan (masalah dapat

dipecahkan).

• Jumlah iterasi dan jumlah langkah yang didapat pada

pengujian dengan fungsi heuristic diagonal distance lebih

sedikit dibandingkan dengan fungsi heuristic straight line

distance, tetapi lebih besar dibandingkan dengan fungsi

heuristic manhattan distance.

Jika perhitungan algoritma A* dilakukan pada grid, maka fungsi

heuristic yang tepat adalah menggunakan manhattan distance. Sedangkan

untuk algoritma A* pada graph, fungsi heuristic yang tepat adalah straight

line distance dimana hasil yang didapat akan mempunyai cost yang lebih

kecil daripada fungsi heuristic manhattan distance dan diagonal distance.

Apabila pada grid nilai g(n) untuk vertical, horizontal, dan

diagonalnya dianggap sama, fungsi heuristic yang tepat adalah dengan

menggunakan fungsi heuristic diagonal distance. (Mario, irawan, aryo, 2004,

p150)

2.10 Algoritma Pathfinding

Menurut Wikipedia (2013), pathfinding atau pathing mengacu pada

merencanakan, oleh aplikasi komputer, dari rute terpendek antara dua titik. Pada

intinya, metode pathfinding mencari sebuah graph dengan memulai pada satu titik

dan mengeksplorasi berdekatan node sampai node tujuan tercapai, umumnya dengan

maksud untuk menemukan rute terpendek.

39

Tujuan dari algoritma pathfinding adalah untuk menemukan jalur terbaik dari

node awal ke node tujuan. Secara umum algoritma pathfinding digolongkan menjadi

dua jenis (Russel, Stuart, dan Peter Norvig, 1995, p73), yaitu :

1. Algoritma Uniformed Search

Algoritma uniformed search adalah algoritma yang tidak memiliki

keterangan tentang jarak atau biaya dari path dan tidak memiliki

pertimbangan akan path mana yang lebih baik. Yang termasuk dalam

algoritma ini adalah algoritma breadth first search.

2. Algoritma Informed Search

Algoritma informed search adalah algoritma yang memiliki keterangan

tentang jarak atau biaya dari path dan memiliki pertimbangan

berdasarkan pengetahuan akan path mana yang lebih baik. Yang

termasuk algoritma ini adalah algoritma A* dan algoritma dijkstra.

Dalam algoritma pathfinding sering kali terjadi backtrack bila tidak

menemukan solusi. Backtrack merupakan suatu algoritma pelacakan yang mencoba

mencari penyelesaian masalah yang menyeluruh dengan membangun solusi partial.

Dalam posesnya, backtrack akan mundur ke solusi partial sebelumnya, jika terdapat

solusi yang cocok dengan tuntutan masalah.

2.11 Bahasa Pemrograman C#

C# adalah sebuah bahasa pemrograman berbasis OOP(Object Oriented

Programming) yang merupakan pengembangan dari bahasa pemrograman C. C#

berada dalam lingkungan .NET(red: dot net) Framework yang sudah sejak lama

digencar-gencarkan oleh Microsoft. Anders Hejlsberg adalah yang merancang bahasa

pemrograman ini, atau biasa disebut Language Designer-nya.

40

C# adalah salah satu dari banyak bahasa yang bisa dipakai untuk

pemrograman .NET. Kelebihan utama bahasa ini adalah sintaksnya yang mirip C,

namun lebih mudah dan bersih. Beberapa keunggulan dari C# lainnya, yaitu :

• Sederhana (Simple)

C# bersifat sederhana, karena bahasa ini didasarkan kepada bahasa C

dan C++.

• Object Oriented Language

C# memenuhi syarat-syarat sebagai sebuah bahasa pemrograman yang

bersifat object oriented, yaitu encapsulation, inheritance, dan

polymorphism.

• Powerfull dan Flexible

C# dapat digunakan untuk membuat berbagai macam aplikasi, seperti

aplikasi pengolah kata, grafik, spreadsheets, atau bahkan compiler

untuk sebuah bahasa pemrograman.

• Efisien

C# tidak memiliki terlalu banyak keyword, sehingga dapat

mengurangi kerumitan.

• Modular

Kode C# ini ditulis dengan pembagian masing-masing class yang

tediri dari beberapa routines yang disebut sebagai member methods.

Masing-masing class dan metode ini dapat digunakan kembali oleh

program atau aplikasi lain. Hanya dengan memberikan informasi yang

41

dibutuhkan oleh class dan metode yang dimaksud, maka kita dapat

membuat suatu kode yang dapat digunakan oleh satu atau beberapa

aplikasi dan program (reusable code).

2.12 Unified Modelling Language

Menurut Wikipedia, Unified Modelling Language (UML) adalah bahasa

spesifikasi standar untuk mendokumentasikan, menspesifikasikan, dan membangun

sistem perangkat lunak. UML dikembangkan sebagai suatu alat untuk analisis dan

desain berorientasi objek oleh Grady Booch, Jim Rumbaugh, dan Ivar Jacobson.

Namun demikian, UML dapat digunakan untuk memahami dan

mendokumentasikan setiap sistem informasi.

Dengan menggunakan UML kita dapat membuat model untuk semua jenis

aplikasi piranti lunak, dimana aplikasi tersebut dapat berjalan pada piranti keras,

sitem operasi, dan jaringan apapun, serta ditulis dalam bahasa pemrograman

apapun. Tetapi karena UML juga menggunakan class dan operation dalam konsep

dasarnya, maka UML lebih cocok untuk penulisan piranti lunak dalam bahasa

berorientasi objek, seperti C++, C#, Java, atau VB.NET. Walaupun demikian,

UML tetap dapat digunakan untuk modeling aplikasi dalam VB atau C.

Menurut Bentley & Whitten (2010, p371), UML adalah satu set dari

ketentuan modeling yang digunakan untuk menspesifikasi atau mendeskripsikan

sebuah sistem perangkat lunak dalam suatu kondisi dari objek.

UML dibagi menjadi beberapa komponen :

1. Class Diagram

Class diagram adalah penggambaran grafis mengenai struktur objek

statis dari sebuah sistem, menunjukkan kelas-kelas objek yang

42

menyusun sebuah sistem dan juga hubungan antara kelas objek

tersebut. Class diagram digunakan secara grafis untuk menggambarkan

objek dan asosiasinya. (Bentley & Whitten, 2010, p400).

Class diagram digunakan untuk memberikan gambaran dari class yang

ada, hubungan antar class, dan menjelaskan kedudukan class tersebut

berada dalam sub sistem yang mana. Class diagram memiliki atribut,

operasi, dan juga berbagai macam tipe peran dan asosiasi.

Class menggambarkan keadaan (attribute/property) suatu sistem,

sekaligus menawarkan layanan untuk memanipulasi keadaan tersebut

(metode/fungsi). Class diagram menggambarkan struktur dan deskripsi

class, package, dan objek beserta hubungan satu sama lain seperti

containment, pewarisan, asosiasi, dan lain sebagainya.

Class memiliki tiga area pokok, yaitu nama, atribut, dan metoda.

Atribut dan metoda dapat memiliki salah satu sifat berikut :

• Private, tidak dapat dipanggil dari luar class yang bersangkutan.

• Protected, hanya dapat dipanggil oleh class yang bersangkutan

dan anak-anak yang mewarisinya.

• Public, dapat dipanggil oleh siapa saja.

Hubungan antar class, yaitu :

• Asosiasi, yaitu hubungan statis antar class. Umumnya

menggambarkan class yang memiliki atribut berupa class lain,

atau class yang harus mengetahui ekstensi class lain, atau class

yang harus mengetahui eksistensi class yang lain. Panah

navigability menunjukkan arah query antar class.

• Agregasi, yaitu hubungan yang menyatakan bagian (“terdiri

43

atas..”).

• Pewarisan, yaitu hubungan hierarkis antar class. Class dapat

diturunkan dari class lain dan mewarisi semua atribut dan metode

class asalnya dan menambahkan fungsionalitas baru, sehingga ia

disebut anak dari class yang diwarisinya. Kebalikan dari

pewarisan adalah generalisasi.

• Hubungan dinamis yaitu rangkaian pesan yang di-passing dari

satu class kepada class lain. Hubungan dinamis dapat

digambarkan dengan menggunakan sequence diagram.

2. Use Case Diagram

Use case diagram menggambarkan interaksi antara sistem, sistem

eksternal dan pengguna. Use case diagram menggambarkan secara

grafis siapa yang menggunakan sistem dan dengan cara seperti apa

yang diharapkan pengguna untuk berinteraksi dengan sistem. (Bentley

& Whitten, 2010, p246-250)

Use case diagram berisi actor dan use case, yang memberikan

gambaran mengenai hubungan yang terjadi antara dua hal tersebut. Use

case diagram adalah titik permulaan dalam tahap analisa pada saat

merancang sistem. Diagram ini dibuat oleh Ivan Jacobson.

Tujuan dari use case diagram adalah memberikan gambaran

keseluruhan dari struktur sistem dan fitur yang ada kepada pihak non

teknis, seperti bagian manajemen dan pengguna. Diagram ini juga dapat

digunakan untuk menggambarkan urutan kejadian dalam sistem, apabila

tidak ada kesalahan.

44

Use case merupakan sebuah pekerjaan tertentu, misalnya login ke

sistem, membuat daftar belanja, dan sebagainya. Seorang/sebuah actor

adalah sebuah entitas manusia atau mesin yang berinteraksi dengan

sistem untuk melakukan pekerjaan-pekerjaan tertentu.

3. Sequence Diagram

Sequence diagram menggambarkan secara grafis bagaimana objek

berinteraksi satu sama lain melalui pesan dalam eksekusi use case atau

operasi. Diagram ini menggambarkan langkah-langkah pesan dikirim

dan diterima antara objek. (Bentley & Whitten, 2010, p394)

Sequence diagram digunakan untuk menggambarkan interaksi antara

actor dengan objek dan objek dengan objek lain. Pesan disampaikan

dari actor kepada objek, objek ke objek, dan dari objek ke actor untuk

menunjukkan aliran control dalam sistem. Diagram ini juga dapat

digunakan untuk menggambarkan semua aliran yang mungkin terjadi

dalam interaksi sistem, atau menggambarkan sebuah aliran saja.

Sequence diagram menggambarkan interaksi antar objek di dalam dan

di sekitar sistem, termasuk pengguna, display, dan sebagainya dalam

berupa message yang digambarkan terhadap waktu. Sequence diagram

terdiri antar dimensi vertical (waktu) dan dimensi horizontal (objek-

objek yang terkait).

Sequence diagram biasa digunakan untuk menggambarkan skenario

atau rangkaian langkah-langkah yang dilakukan sebagai respons dari

sebuah kejadian untuk menghasilkan output tertentu. Diawali dari apa

yang men-trigger aktivitas tersebut, proses dan perubahan apa saja yang

45

terjadi secara internal dan output apa yang dihasilkan. Masing-masing

objek, termasuk actor, memiliki lifeline vertical. Message digambarkan

sebagai garis berpanah dari satu objek ke objek lainnya. Pada fase

desain berikutnya, message akan dipetakan menjadi operasi/metoda dari

class. Activation bar menunjukkan lamanya eksekusi sebuah proses,

biasanya diawali dengan diterimanya sebuah message. Untuk objek-

objek yang memiliki sifat khusus, standar UML mendefinisikan icon

khusus untk objek boundary, controller, dan persistent entity.

4. Activity Diagram

Activity diagram menggambarkan secara grafis alur yang berurutan dari

aktifitas use case atau proses bisnis, atau logika dari metode objek.

Diagram ini juga dapat digunakan untuk memodelkan logika dengan

suatu sistem. (Bentley & Whitten, 2010, p390)

Activity diagram digunakan untuk melakukan analisa terhadap perilaku

yang ada dalam suatu use case yang kompleks dan memberikan

gambaran interaksi antar use case tersebut.

Activity diagram menggambarkan berbagai alir aktivitas dalam sistem

yang sedang dirancang, bagaimana masing-masing alir berawal,

decision yang mungkin terjadi, dan bagaimana mereka berakhir.

Activity diagram juga dapat menggambarkan proses parallel yang

mungkin terjadi pada beberapa eksekusi.

Activity diagram merupakan state diagram khusus, dimana sebagian

besar state adalah action dan sebagian besar transisi di-trigger oleh

selesainya state sebelumnya (internal processing). Oleh karena itu,

46

activity diagram tidak menggambarkan behaviour internal sebuah

sistem (dan interaksi antar sub sistem) secara eksak, tetapi lebih

menggambarkan proses-proses dan jalur-jalur aktivitas dari level atas

secara umum.

Dalam standar UML menggunakan segiempat dengan sudut membulat

untuk menggambarkan aktivitas. Decision digunakan untuk

menggambarkan behaviour pada kondisi tertentu. Dan untuk

mengilustrasikan proses-proses parallel (fork dan join) digunakan titik

sinkronisasi yang dapat berupa titik, garis horizontal atau vertical.

Activity diagram dapat dibagi menjadi beberapa object swimlane untuk

menggambarkan objek mana yang bertanggung jawab untuk aktivitas

tertentu.