11. Algoritma
untuk menentukan bilangan ganjil atau genap
1.
Masukkan sebuah bilangan/Input bilangan sembarang
2.
Bagi bilangan tersebut dengan angka 2
3.
Prosesnya, Hitung sisa bagi pada langkah kedua
4. Bila sisa bagi sama dengan nol,
maka bilangan itu adalah bilangan genap, tetapi bila sisa bagi sama dengan 1
maka bilangan itu adalah bilangan ganjil.
12.A. Sorting
B. SEARCHING C. Knapsack
a. Pengurutan atau Sorting merupakan suatu
proses mengatur susunan data-data menurut syarat tertentu. Meskipun pengurutan ini
sepertinya hanya sebuah masalah klasik dalam keinformatikaan,namun perannya
tidak dapat dipisahkan terutama dalam pengolahan data. Suatu pengolahan data
biasanya akan lebih efisien jika datanya telah terurut,seperti Binary Search
misalnya. Mengingat pentingnya pengurutan dalam penggunaannya dalam hal
keinnformatikaan, maka perlu diketahui algoritma mana yang sebenarnya paling
efisien untuk dipakai. Meskipun suatu algoritma pengurutan mempunyai kelebihan
dan keterbatasan masing-masing, kompleksitas dan keefisiensiannya tetap
harusdipertimbangkan.
b. CONTOH
APLIKASI TEKNIK PEMECAHAN MASALAH (SEARCHING) memecahkan permainan FREECELL DENGAN ALGORITMA
BACKTRACKING FreeCell merupakan sebuah permainan puzzle kartu yang sangat
terkenal. Permainan inimerupakan permainan yang dikembangkan dari permainan
terdahulunya seperti Klondike dan Eight Off. Permainan FreeCell merupakan
permainan yang lebih mengandalkan kemampuan dan strategi daripada
keberuntungan. Permainan ini berkembang dengan sangat pesat sehingga Windows
mengimplementasikannya dalam entertainment packnya sehingga semua komputer yang
memiliki OS Windows (kecuali Windows Vista) biasanya memiliki permainan
FreeCell. Selain itu terdapat juga website website yang menyediakan permainan
FreeCell dengan fasilitas fasilitas seperti turnamen antar pemain dan
sebagainya.
Algoritma backtracking (runut balik) merupakan algoritma yang sangat
terkenal dan banyak digunakan dalam memecahkan berbagai jenis permainan.
Algoritma ini merupakan algortima yang berdasarkan pada DFS (Deep First Search)
untuk mencari solusi suatu masalah.
I. Rule Freecell
1. Kocok kartu (joker tidak diikutsertakan).
Kemudian bagi kartu tersebut ke dalam 8 kolom (terletak di bawah pada gambar
1). Akan terdapat 4 buah kolom yang memiliki 7 buah kartu dan 4 buah kololm
yang memiliki 6 buah kartu. Pada setiap kolom, kartu kedua diletakkan di bawah
kartu pertama, kartu ketiga di bawah kartu kedua, dan seterusnya. Peletakkan
kartu di bawah kartu yang lainnya hanya bermaksud bahwa hanya kartu terbawah
yang boleh diambil. Apabila kita memainkan permainan ini dari program yang
telah disediakan Windows, maka langkah ini tidak perlu dilakukan karena telah
ditangani oleh program. Selain itu akan terdapat 4 buah kotak kosong (free
cells) di kiri atas dan 4 buah tumpukan fondasi di kanan atas.
2. Objektif atau tujuan dari
permainan ini adalah memindahkan semua kartu ke tumpukan fondasi.
3. Setiap kartu yang tunggal bisa
dipindahkan apabila memenuhi kriteria berikut:
a. Dari kolom
yang satu ke kolom yang lain yang tidak kosong, apabila kolom yang dituju memiliki kartu terakhir memiliki indeks
yang lebih rendah dengan perbedaan 1 dan berbeda warna. Indeks tertinggi adalah
King dan indeks terendah adalah As. Urutan indeks sama dengan urutan yang
digunakan dalam permainan kartu pada umumnya. Setiap kartu yang dipindahkan
akan ditempatkan ke bawah kartu terkahir dari kolom yang dituju
b. Dari kolom
ke kolom lain yang masih kosong.
c. Dari kolom
ke free cell, apabila kotak free cell yang dituju masih kosong.
d. Dari free
cell ke kolom yang masih kosong.
e. Dari free cell ke kolom yang tidak kosong, memiliki syarat yang
sama dengan pemindahan kartu dari kolom
ke kolom lain yang tidak kosong.
f. Dari kolom ke tumpukan fondasi yang masih kosong, apabila kartu yang
dipindahkan adalah As.
g. Dari kolom ke tumpukan fondasi yang telah terisi, apabila kartu yang
dipindahkan memiliki lambang yang sama dengan kartu terakhir tumpukan fondasi
dan indeksnya lebih tinggi dengan perbedaan satu
h. Dari free cell ke tumpukan fondasi yang masih kosong, apabila kartu
yang dipindahkan adalah As.
i. Dari free cell ke tumpukan fondasi yang
tidak kosong, dengan syarat yang sama dengan
pemindahkan kartu dari kolom ke tumpukan fondasi yang tidak kosong.
c. Dalam
kehidupan sehari-hari, kita sering dipusingkan dengan media penyimpanan yang
terbatas padahal kita diharuskan menyimpan beberapa objek kedalam media
tersebut.
Bagaimana kita mengatur objek apa saja yang dipilih dan seberapa besar
objek tersebut disimpan?
Dari permasalahan tersebut, munculah suatu permasalahan yang dikenal
dengan “Permasalahan Knapsack” atau lebih dikenal dengan “Knapsack Problem”.
Masalah Knapsack merupakan suatu permasalahan bagaimana memilih objek dari sekian
banyak dan berapa besar objek tersebut akan disimpan sehingga diperoleh suatu
penyimpanan yang optimal dengan memperhatikan objek yang terdiri dari n objek
(1,2,3,…) dimana setiap objek memiliki bobot (Wi) dan profit (Pi) dengan
memperhatikan juga kapasitas dari media penyimpanan sebesar M dan nilai
probabilitas dari setiap objek (Xi).
Permasalahan ini dapat diselesaikan dengan 3 cara, yaitu :1.
Matematika, 2. Kriteria Greedy, dan 3. Algoritma Greedy. Dalam kasus ini
penulis mencoba menyelesaikan dengan 3 cara di atas.
Metode Greedy merupakan salah satu cara untuk mendapatkan solusi optimal
dalam proses penyimpanan. Pada metode ini untuk mendapatkan solusi optimal dari
permasalahan yang mempunyai dua kriteria yaitu Fungsi Tujuan/Utama dan Nilai
Pembatas (Constrain). Fungsi Tujuan hanya terdiri atas satu fungsi sedangkan
Fungsi Pembatas dapat terdiri atas lebih dari satu fungsi.
2. 3.
a.
Misalkan kita punya data seperti ini: 6, 4, 3, 2 dan kita ingin mengurutkan
data ini (ascending) dengan menggunakan bubble sort. Berikut ini adalah proses
yang terjadi:
Iterasi ke-1: 4, 6, 3,
2 :: 4, 3, 6, 2 :: 4, 3, 2, 6 (ada 3 pertukaran)
Iterasi ke-2: 3, 4, 2,
6 :: 3, 2, 4, 6 :: 3, 2, 4, 6 (ada 2 pertukaran)
Iterasi ke-3: 2, 3, 4,
6 :: 2, 3, 4, 6 :: 2, 3, 4, 6 (ada 1 pertukaran)
Iterasi ke-4: 2, 3, 4,
6 :: 2, 3, 4, 6 :: 2, 3, 4, 6 (ada 0 pertukaran) -> proses selesai
b. Algoritma backtracking untuk
menyelesaikan permainan FreeCell.
1. Apabila status sekarang telah merupakan
status final atau status selesai, permainan telah berhasil diselesaikan, return
true. Kalau tidak lanjut ke langkah 2.
2. Kita daftarkan semua langkah yang mungkin
dilakukan dari status sekarang.
3. Apabila tidak ada langkah yang bisa
dilakukan maka berarti status sekarang tidak dapat melahirkan penyelesaian. Backtracking ke
status sebelumnya. Apabila tidak ada lagi status yang dapat dibacktrack maka
berarti tidak ada solusi, return false. Apabila masih ada langkah yang bisa
dilakukan, lanjut ke langkah 4.
4. Kita ambil satu langkah yang pertama dari list, hapus langkah yang
diambil tersebut dari list dan kita
lakukan langkah tersebut sehingga membentuk status yang baru.
5. Apabila status yang baru tersebut sudah pernah terjadi, kembali ke
langkah ke 3. Apabila belum, kita ulangi langkah 1 hingga 5 dengan status yang
baru terbentuk.
III.
Penggunaan Metode Heuristik
Salah satu cara yang digunakan untuk
meningkatkan efektifitas algoritma adalah dengan menggunakan metode heuristik.
Beberapa di antaranya adalah:
1.
Bila terdapat langkah yang menempatkan kartu pada tumpukan fondasi, dan
angka pada kartu tersebut memiliki nilai indeks yang minimal sama dengan nilai
indeks tumpukan fondasi lain yang berbeda warna, maka kartu tersebut pasti akan
aman untuk ditempatkan di fondasi. Seperti kita ketahui, kartu pada tumpukan
fondasi tidak dapat diambil lagi, hal ini menyebabkan terkadang terjadi
kesalahan seperti terlalu cepat menaruh kartu pada tumpukan fondasi padahal
kartu tersebut masih diperlukan untuk menyangga kartu kartu lain yang berbeda
warna dan memiliki angka lebih kecil dari dirinya. Tetapi dengan cara di atas,
kesalahan tersebut tidak akan terjadi karena kartu lain yang berbeda warna dan
memiliki angka lebih kecil sudah dimasukkan ke dalam tumpukan fondasi.
2.
Bila terdapat langkah yang menempatkan kartu pada tumpukan fondasi, dan
kartu tersebut memiliki angka yang lebih tinggi dari angka kartu pada tumpukan
fondasi lain yang berbeda warna sebesar n, maka kartu itu akan aman dipindahkan
apabila tumpukan fondasi lain yang memiliki warna yang sama dengan kartu
tersebut memiliki angka yang lebih kecil sebesar 2n. Hal ini dikarenakan
meskipun kita kehilangan kemungkinan untuk menyangga kartu kartu lain dengan
memasukkan kartu tersebut, tetapi masih terdapat kartu lain yang memiliki warna
yang sama dengan kartu yang kita masukkan yang mampu menggantikan peran kartu
yang kita masukkan tersebut. Tentu saja metode ini belum tentu benar karena
bisa saja kartu yang kita harapkan dapat mengganti peran kartu lain yang kita
masukkan ternyata terdapat di kolom yang paling bawah. Namun demikian, biasanya
metode heuristik ini berhasil.
3.
Pada Permainan FreeCell, terdapat gerakan yang disebut super move [6],
yaitu gerakan yang memindahkan 2 atau lebih kartu sekaligus dari kolom yang
satu ke kolom yang lain. Hal ini bisa dilakukan apabila terdapat ruang lain
untuk menyimpan kartu sementara. Misalnya kita memiliki sebuah kolom dengan
kartu teratas adalah jack hitam dan 10 merah, selain itu terdapat kolom lain
dengan kartu teratas adalah queen merah. Kita dapat memindahkan jack dan 10
sekaligus ke atas queen apabila terdapat sebuah ruang kosong seperti sebuah sel
kosong. Sebenarnya yang terjadi adalah pertama tama 10 merah dipindahkan
terlebih dahulu ke sel kosong tersebut, lalu jack dipindahkan ke atas queen,
dan baru kemudian 10 dipindahkan ke atas jack. Super move akan sangat membantu
mempercepat kerja program apabila diimplementasikan, meskipun demikian, super
move
juga tidak selalu menuntun kita
menuju penyelesaian.
4.
Urutan urutan kartu yang dipindahkan terlebih dahulu cukup penting untuk
meningkatkan kemangkusan program. Pemindahan kartu yang salah dari awal akan
membuat program menjadi lambat
karena program akan memeriksa semua kemungkinan hingga ditemukan jalan buntu
sebelum melakukan runut balik ke awal. Dari penelitian yang telah dilakukan
penulis, urutan pemindahan kartu dari yang sebaiknya dilakukan terlebih dahulu
adalah sebagai berikut:
* Pemindahan kartu ke
tumpukan fondasi.
* Super move.
* Pemindahan kartu dari kolom
ke sel kosong.
* Pemindahaan kartu dari sel
kosong ke kolom atau dari kolom ke kolom lain.
c.
Cara menyelesaikan masalah Knapsack
adalah
1. Tentukan Fungsi Tujuan, yaitu
mencari nilai maximum dari jumlah hasil perkalian antara nilai profit (Pi)
dengan nilai probabilitas (Xi)
Maximum ∑Pi.Xi
2. Tentukan Fungsi Pembatas, yang
merupakan hasil penjumlahan dari perkalian antara bobot (Wi) dengan nilai
probabilitas (Xi) yang tidak boleh melebihi dari kapasitas media penyimpanan
(M)
∑Wi.Xi≤M, dimana
0≤Xi≤1, Pi>0, Wi>0
Dari ke-2 cara di atas berarti kita
harus mengetahui
1. Jumlah objek (n)
2. Bobot setiap objek (Wi)
3. Profit setiap objek (Pi)
4. Probabilitas setiap objek (Xi),
dan
5. Kapasitas media penyimpanan (M)
Tidak ada komentar:
Posting Komentar