4645

BAB 2LANDASAN TEORI2.1 Algoritma

2.1.1 Definisi AlgoritmaAlgoritma 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. Dalammatematikadankomputasi,algoritmaataualgoritme,merupakan kumpulan perintah untuk menyelesaikan suatu masalah. Perintah-perintah ini dapat diterjemahkan secara bertahap dari awal hingga akhir. Masalah tersebut dapat berupa 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 denganheuristik. Algoritma sering mempunyai langkah pengulangan (iterasi) atau memerlukan keputusan (logika Booleandan 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 untukmembagisuatu permasalahan besar menjadi permasalahan-permasalahan yang lebih kecil. Pembagian masalah ini dilakukan terus menerus sampai ditemukan bagian masalah kecil yang mudah untukdipecahkan. Dynamic programming, paradigma pemrograman dinamik akan sesuai jika digunakan pada suatu masalah yang mengandungsub-struktur yang optimal, dan mengandung beberapabagian permasalahan yang tumpang tindih. Paradigma ini sekilas terlihat mirip dengan paradigmaDivide 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, sebuahalgoritma serakahmirip dengan sebuahpemrograman dinamik, bedanya jawaban dari submasalah tidak perlu diketahui dalam setiap tahap dan menggunakan pilihan "serakah" apa yang dilihat terbaik pada saat itu.2.1.3 Kompleksitas Algoritma, Waktu, Dan MasalahKompleksitas 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 asimptotikdengan 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 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.

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.

Dalammatematikadanilmu komputer, sebuah masalah optimasi adalah

HYPERLINK "https://en.wikipedia.org/wiki/Computational_problem" \o "Masalah komputasi" masalahuntuk menemukansolusi terbaik dari semua solusi.Masalah optimasi dapat dibagi menjadi dua kategori tergantung pada apakahvariabelyang kontinyu atau diskrit.Masalah optimasi dengan variabel diskrit dikenal sebagaimasalah optimasi kombinatorial.Dalam masalah optimasi kombinatorial, kami sedang mencari sebuah benda seperti grafik integer, permutasi atau dari himpunan berhingga (atau mungkin dihitung tak terbatas).

2.3 Gambaran Umum tentang Label Kertas Atau Plastik2.3.1 Definisi LabelDalam 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 onlinekomputer, 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 jenismetadatayang membantu untuk menjelaskan suatu hal dan memungkinkan hal tersebut ditemukan ketika melakukan pencarian (browsing). Gambar 2.1 Macam-macam label kertasTujuan 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 KemasanMerancang 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.

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.

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.

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 LabelTerdapat 3 (tiga) macam label menurut Stanton (1994), yaitu:

1. Brand LabelLabel 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. 3. Grade Label Label ini menginformasikan kepada konsumen tentang penilaian kualitas produk.2.4 PencarianPencarian (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.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-HardMenurut 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.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-NP2.7 Metode Pencarian HeuristicMenurut 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 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.

2.8 Best First Search2.8.1 Pengertian Best First SearchBest First Searchmerupakan 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 evaluasif(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.

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 SearchPertama 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.Gambar 2.3 Langkah-Langkah Algoritma Best First SearchUntuk 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.

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 SearchAlgoritma yang menggunakan metode best first search, yaitu:

a.Greedy Best FirstGreedy Best First adalah algoritma best first yang paling sederhana dengan hanya memperhitungkan biaya perkiraan (estimated cost) saja, yaknif(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.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 sebagaif(n)= g(n) + h(n).Dengan perhitungan biaya seperti ini, algoritma A* adalah completedanoptimal.2.9 Metode A* HeuristicMetode 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. Secara umum, Depth First Search (DFS) dan Breadth First Search (BFS) adalah dua kasus spesial dari metode A*. Algoritma Dijkstras 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.

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 list2. 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.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* HeuristicFungsi 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 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 darif(x)fungsi harus menjadiheuristik diterima, yaitu tidak harus melebih-lebihkan jarak ke tujuan.Jadi, untuk aplikasi sepertirouting,h(x)mungkin mewakili garis lurus jarak ke tujuan, karena itu adalah fisik yang mungkin jarak terkecil antara dua titik atau node.

Jikaheuristikhmemenuhi kondisi tambahanmonoton, atau konsisten INCLUDEPICTURE "http://upload.wikimedia.org/math/a/7/1/a71dc736e76051b0c905aa1a8df1238b.png" \* MERGEFORMATINET

untuk setiap sisi (x, y) dari grafik (di manadmenunjukkan panjang tepi itu), makahdisebut.Dalam kasus seperti itu, A* dapat dilaksanakan dengan lebih efisien-berbicara kasar, tidak ada node perlu diproses lebih dari sekali (lihatditutup ditetapkandi bawah) dan A* setara dengan menjalankan algoritma Dijkstradenganmengurangi biayad '(x, y): = d (x, y) - h (x) + h (y).Sepertipencarian breadth-first, A * adalahlengkapdan akan selalu menemukan solusi jika ada. Jika heuristik fungsihadalahditerima, artinya tidak pernah overestimates biaya minimal sebenarnya mencapai tujuan, maka A * itu sendiri diterima (atauoptimal) jika kita tidak menggunakan satu set tertutup.Jika suatu himpunan tertutup digunakan, makahjuga harusmonoton(ataukonsisten) untuk A* menjadi optimal.Ini berarti bahwa untuk setiap pasangan node yang berdekatanxdany, di manad (x, y)menunjukkan panjang tepi antara mereka, kita harus memiliki:

Hal ini memastikan bahwa untuk setiap jalurXdari node awal untukx:

di manaLadalah fungsi yang menunjukkan panjang jalan, danYadalah jalurXdiperluas untuk mencakupy.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 dalamalgoritma Dijkstra.) monotonicity menyiratkan diterimanya ketika perkiraan heuristik pada setiap node tujuan itu sendiri adalah nol, karena (membiarkanP = (f, v1, v2, ..., vn, g)menjadi jalan terpendek dari nodefuntuk tujuan terdekatg):

A * juga efisien secara optimal untuk setiap heuristikh, 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 manahtepatnya 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 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 sejumlahalgoritma diterima:

Tertimbang A*.Jikah(n)adalah fungsi heuristik diterima, dalam versi tertimbang dari A* pencarian satu menggunakanhw (n)= h(n),> 1sebagai fungsi heuristik, dan melakukan pencarian A * seperti biasa (yang akhirnya terjadi lebih cepat daripada menggunakanhasejak kurang node diperluas).Jalan maka ditemukan oleh algoritma pencarian dapat memiliki biaya palingkali dari jalur biaya termurah dalam grafik. Static Bobotmenggunakan biaya fungsi f (n) = g (n) + (1 + ) h (n).

Dinamis Bobotmenggunakan biaya fungsif (n) = g (n) + (1 + w (n)) h (n), di mana, dan di manad(n)adalah kedalaman pencarian danNadalah panjang diantisipasi dari jalur solusi.

Sampel Pembobotan Dinamismenggunakan 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 keduahFdigunakan untuk memilih node yang paling menjanjikan dari daftar FOCAL.

AMemilih node dengan fungsiA f (n) + B hF(n), di manaAdanBadalah konstanta.Jika tidak ada node dapat dipilih, algoritma akan mundur dengan fungsiC f (n) + D hF(n), di manaCdanDadalah 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 manadanadalah konstanta dengan, (n)adalah induk dari n, danadalah paling baru memperluas simpul.

kompleksitas waktudari A* tergantung pada heuristik.Dalam kasus terburuk, jumlah node diperluas adalaheksponensialdalam panjang dari solusi (jalan terpendek), tetapipolinomialketika ruang pencarian adalah pohon, ada negara tujuan tunggal, dan fungsi heuristikhmemenuhi Kondisi berikut:

di manah*adalah heuristik optimal, biaya yang tepat untuk mendapatkan darixke tujuan.Dengan kata lain, kesalahanhtidak akan tumbuh lebih cepat daripadalogaritmadari "heuristik yang sempurna"h*yang mengembalikan jarak yang benar darixke tujuan.A* mempertahankan sebagian dari solusi, sebagai contoh jalur pada graph dimulai dari node awal, dan akan disimpan dalam sebuah queue yang 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_polaPerhitungan ini untuk menentukan pola label mana yang akan diletakkan pertama kali.

h(n) adalah fungsi heuristich(n) = (((kel_alas batas_alas) + (kel_pola batas_alas)) pola_dempet) + nilai_tambahannilai h(n) pertama dibandingkan dengan h(n) yang lainnya, hingga ditemukan nilai h(n) yang paling minimal. kel_alas = keliling alas kertas atau plastik

batas_alas = pola label yang terkena pembatas alas

kel_pola = keliling pola label

pola_dempet = pola label yang saling berdempetan

nilai_tambahan = pemberian nilai tambah agar tidak saling bersinggungan/berdempetan.2.9.3 Perbandingan Fungsi A* HeuristicBeberapa fungsi heuristic yang umum digunakan pada algoritma pathfinding A* adalah sebagai berikut :1. Manhattan DistanceManhattan 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.

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 DistanceStraight 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 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 DistanceDiagonal 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.

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.

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 SearchAlgoritma 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 disebutLanguage Designer-nya.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 LanguageC# memenuhi syarat-syarat sebagai sebuah bahasa pemrograman yang bersifat object oriented, yaitu encapsulation, inheritance, dan polymorphism. Powerfull dan FlexibleC# 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 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 LanguageMenurut 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 DiagramClass diagram adalah penggambaran grafis mengenai struktur objek statis dari sebuah sistem, menunjukkan kelas-kelas objek yang 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 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 DiagramUse 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.

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 DiagramSequence 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 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 DiagramActivity 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, 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.

8