BAB 2 LANDASAN TEORI

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 8

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 ≥ n 0 , 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 potonganpotongan 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 keteranganketrangan 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 pengkomputasipemrosesan 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 heuristicnya 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

menggunakan

sebuah

fungsi

yang

dilakukan

dengan

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 nodenode 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 y)

dari

grafik

(di

mana d menunjukkan

untuk setiap sisi ( x, 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 + ε)

•

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

h (n) .

ε 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

mana

f α (n)

=

(1

+

,

konstanta dengan

w α (n))

di

f

(n) ,

di

mana λ dan Λ adalah

, π (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 (objekobjek 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 objekobjek 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

menggambarkan

aktivitas.

behaviour

pada

Decision kondisi

digunakan

tertentu.

Dan

untuk 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.