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
Graph problems
graph problems dapat di gunakan dalam algoritma greedy.
Pengertian dari Algoritma Greedy merupakan
metode yang paling populer untuk memecahkan persoalan optimasi.
Persoalan optimasi (optimization problems): persoalan yang
menuntut pencarian solusi optimum.
Persoalan optimasi hanya
ada dua macam:
1 . Maksimasi (maximization)
2. Minimasi (minimization)
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).
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