Dalam blog
kami ini akan menjelaskan beberapa materi diatas, pada kesempatan kali ini
kami akan menjelakan tentang
Penjelasa tentang string
processing
Algoritma
pencarian string atau
sering disebut juga pencocokan string adalah algoritma untuk melakukan pencarian semua
kemunculan string pendek pattern [0..n-1] yang disebut
pattern di string yang lebih panjang teks [0...m-1] yang disebut teks
String
processing dapat di gunakan dalam Algoritma brute force dalam pencarian string
Algoritma brute
force merupakan algoritma pencocokan string yang ditulis tanpa memikirkan
peningkatan performa. Algoritma ini sangat jarang dipakai dalam praktik, namun
berguna dalam studi pembanding dan studi-studi lainnya.
Pseudocode
Pseudocode
algoritma brute force ini:
procedure BruteForceSearch(
input m,
n : integer,
input P
: array[0..n-1] of char,
input T
: array[0..m-1] of char,
output
ketemu : array[0..m-1] of boolean
)
Deklarasi:
i, j:
integer
Algoritma:
for
(i:=0 to m-n) do
j:=0
while (j < n and T[i+j] = P[j]) do
j:=j+1
endwhile
if(j >= n) then
ketemu[i]:=true;
endif
endfor
Solusi
optimum (terbaik) adalah solusi yang bernilai minimum atau maksimum dari
sekumpulan alternatif solusi yang mungkin.
Solusi yang
memenuhi semua kendala disebut solusi
layak (feasible solution). Solusi layak yang mengoptimumkan
fungsi optimasi disebut solusi optimum.
Algoritma
Greedy adalah algoritma yang memecahkan masalah langkah per langkah;
pada setiap langkah:
1. mengambil pilihan yang terbaik yang dapat
diperoleh pada saat itu tanpa memperhatikan konsekuensi ke depan (prinsip “take what you can get now!”)
2. berharap bahwa dengan memilih optimum lokal
pada setiap langkah akan berakhir dengan optimum global
Contoh kasus algoritma greedy :
Misalkan tersedia koin : 1, 3, 5.
Uang senilai X=8 dapat di tukar dengan cara :
- 1+1+1+1+1+1+1+1 = 8 (8 koin)
- 1+1+1+1+1+3=8 (6 koin)
- 1+1+1+5=8 (4 koin)
- 1+1+3+3=8 (4 koin)
- 3+5=8 (2 koin) solusi optimal.
Maka solusi optimal dari kasus penukaran koin di atas
adalah 2 koin.
Algoritma yang termasuk ke dalam tipe algoritma greedy antara lain :
·
Kode Huffman
·
Algoritma
dijkstra
·
Algoritma
prim
·
Algoritma
kruskal
Yang
ketiganya digunakan dalam menyelesaikan permasalahan optimasi pada graf .
Algoritma
greedy dalam menyelesaikan masalah dengan langkah per langkah “ secara bertahap
“ .
Dengan
definisi , pada setiap langkah algoritma greedy :
1. Mengambil pilihan yang terbaik
Yaitu dapat
diperoleh pada saat itu tanpa memperhatikan konsekuensi kedepan (
prinsip “ take what you can get now )
2. Berharap bahwa dengan memilih optimum
Local pada
setiap langkah akan berakhir dengan optimum global .
Algoritma kruskal
Algoritma Kruskal adalah algoritma untuk mencari pohon merentang
minimum secara langsung didasarkan pada algoritma kruskal sisi-sisi di dalam graf diurut terlebih dahulu berdasarkan
bobotnya dari kecil ke besar. Sisi yang dimasukkan ke dalam himpunan T adalah
sisi graf G sedemikian sehingga T adalah pohon. Pada keadaan awal, sisi-sisi sudah
diurut berdasarkan bobot membentuk hutan (forest). Hutan tersebut dinamakan hutan merentang (spanning
forest). Sisi dari graf G ditambahkan ke T jika tidak membentuk sirkuit di
T.
Perbedaan prinsip antara algoritma Prim dan Kruskal
adalah jika pada algoritma Prim sisi yang dimasukkan ke dalam T harus bersisian
dengan sebuah simpul di T, maka pada algoritma Kruskal sisi yang dipilih tidak
perlu bersisian dengan simpul di T asalkan penambahan sisi tersebut tidak
membentuk sirkuit.
Langkah-langkah dalam algoritma Kruskal
adalah sebagai berikut:
1. Lakukan
pengurutan terhadap setiap sisi di graf mulai dari sisi dengan bobot terkecil
sampai terbesar.
2. Pilih sisi
yang mempunyai bobot minimum yang tidak membentuk sirkuit di pohon. Tambahkan
sisi tersebut ke dalam pohon.
3. Ulangi langkah
2 sampai pohon merentang minimum terbentuk, yaitu ketika sisi di dalam pohon
merentang minimum berjumlah n-1 (n adalah jumlah simpul di graf).
Berdasarkan gambar
di atas, maka dilakukan pengurutan sisi pada graf mulai dari sisi dengan bobot terkecil
sampai terbesar dapat dilihat pada tabel berikut:
Untuk lebih memahami
perbedaan algoritma Prim dan algoritma Kruskal yang keduanya merupakan
algoritma untuk pohon merentang minimum, maka dari gambar di atas dapat dicari
pohon merentang minimumnya dengan menggunakan kedua algoritma tersebut.
Langkah-langkah pembentukan pohon merentang minimumnya dapat dilihat pada gamba
berikut ini:
Sumber:
http://wikipedia.org
Tidak ada komentar:
Posting Komentar