Breath First Search (BFS) & Depth First Search (DFS)

Breadth First Search(BFS)
Merupakan algoritma yang melakukan pencarian secara melebar yang mengunjungi simpul secara preorder yaitu mengunjungi suatu simpul kemudian mengunjungi semua simpul yang bertetangga dengan simpul tersebut terlebih dahulu. Selanjutnya, simpul yang belum dikunjungi dan bertetangga dengan simpul-simpul yang tadi dikunjungi, demikian seterusnya. algoritma BFS menggunakan graf sebagai media representasi persoalan, tidak sulit untuk mengaplikasikan algoritma ini dalam persoalan-persoalan teori graf.

Cara Kerja Algoritma BFS
Dalam algoritma BFS, simpul anak yang telah dikunjungi disimpan dalam suatu antrian. Antrian ini digunakan untuk mengacu simpul-simpul yan bertetangga dengannya yang akan dikunjungi kemudian sesuai urutan pengantrian.

Untuk memperjelas cara kerja algoritma BFS beserta antrian yang digunakannya, berikut langkah-langkah algoritma BFS:

1. Masukkan simpul ujung (akar) ke dalam antrian
2. Ambil simpul dari awal antrian, lalu cek apakah simpul merupakan solusi
3. Jika simpul merupakan solusi, pencarian selesai dan hasil dikembalikan.
4. Jika simpul bukan solusi, masukkan seluruh simpul yang bertetangga dengan simpul tersebut (simpul anak) ke dalam
antrian
5. Jika antrian kosong dan setiap simpul sudah dicek, pencarian selesai dan mengembalikan hasil solusi tidak
ditemukan
6. Ulangi pencarian dari langkah kedua

Mari kita coba coding 🙂
Coding dibawah ini menggunakan Python !!

#Gate ‘pintu’ masuk ruang tunggu pesawat
#Biar sewaktu menjalankan lebih mudah untuk melihat bentuk graphnya.., maka disini kita tampilkan grapnya sewaktu diRuN 🙂

print(“Pilih Awal dan Tujuan”)
print(“Lobby”, ‘–>’, ([‘1A’,’1D’,’2A’,’2D’]))
print(“1A”,”,”,”, ‘–>’, ([‘Lobby’,’1B’]))
print(“1B”,”,”,”, ‘–>’, ([‘1A’,’1C’]))
print(“1C”,”,”,”, ‘–>’, ([‘1B’,’1E’,’3A’]))
print(“1D”,”,”,”, ‘–>’, ([‘Lobby’,’1E’]))
print(“1E”,”,”,”, ‘–>’, ([‘1C’,’1D’,’2A’,’3A’]))
print(“2A”,”,”,”, ‘–>’, ([‘Lobby’,’2B’]))
print(“2B”,”,”,”, ‘–>’, ([‘2A’,’2C’]))
print(“2C”,”,”,”, ‘–>’, ([‘2B’,’2E’,’3B’]))
print(“2D”,”,”,”, ‘–>’, ([‘Lobby’,’2E’,’3E’,’Exit’]))
print(“2E”,”,”,”, ‘–>’, ([‘2C’,’2D’]))
print(“3A”,”,”,”, ‘–>’, ([‘1C’,’1E’,’3B’]))
print(“3B”,”,”,”, ‘–>’, ([‘2C’,’3A’,’3C’]))
print(“3C”,”,”,”, ‘–>’, ([‘2E’,’3B’,’3D’]))
print(“3D”,”,”,”, ‘–>’, ([‘2C’,’2D’]))
print(“3E”,”,”,”, ‘–>’, ([‘2C’,’2D’]))
print(“Exit”,”, ‘–>’, ([‘2D’,’3E’]))

print(“\n”)

print(“Format”‘–>’, “BFS (Gate, ‘Awal’, ‘Tujuan’)”)

Gate = {
‘Lobby’ : set ([‘1A’,’1D’,’2A’,’2D’]),
‘1A’ : set ([‘Lobby’,’1B’]),
‘1B’ : set ([‘1A’,’1C’]),
‘1C’ : set ([‘1B’,’1E’,’3A’]),
‘1D’ : set ([‘Lobby’,’1E’]),
‘1E’ : set ([‘1C’,’1D’,’2A’,’3A’]),
‘2A’ : set ([‘Lobby’,’2B’]),
‘2B’ : set ([‘2A’,’2C’]),
‘2C’ : set ([‘2B’,’2E’,’3B’]),
‘2D’ : set ([‘Lobby’,’2E’,’3E’,’Exit’]),
‘2E’ : set ([‘2C’,’2D’]),
‘3A’ : set ([‘1C’,’1E’,’3B’]),
‘3B’ : set ([‘2C’,’3A’,’3C’]),
‘3C’ : set ([‘2E’,’3B’,’3D’]),
‘3D’ : set ([‘2C’,’2D’]),
‘3E’ : set ([‘2C’,’2D’]),
‘Exit’ : set ([‘2D’,’3E’])
}

def BFS (Graf, Awal, Tujuan):
Queue = [[Awal]]
print(“AWAl : \n”, Awal, ‘\n’)
Visited = set ()

while Queue:
Jalan = Queue.pop(0)
state = Jalan [-1]

if state == Tujuan:
print(“TUJUAN : \n”, Tujuan, “\n”)
print(“Jalan ditemukan”)
return Jalan
elif state not in Visited:
for Tetangga in Graf.get (state, []):
new_Jalan = list(Jalan)
new_Jalan.append (Tetangga)
Queue.append(new_Jalan)

Visited.add(state)

isi = len (Queue)
if isi == 0:
print(“Jalan tidak ditemukan”)

Depth-First Search (DFS)
Pencarian dilakukan pada satu node dalam setiap level dari yang paling kiri. Jika pada level yang paling dalam, solusi belum ditemukan, maka pencarian dilanjutkan pada node sebelah kanan. Node yang kiri dapat dihapus dari memori. Jika pada level yang paling dalam tidak ditemukan solusi, maka pencarian dilanjutkan pada level sebelumnya. Demikian seterusnya sampai ditemukan solusi. Jika solusi ditemukan maka tidak diperlukan proses backtracking (penelusuran balik untuk mendapatkan jalur yang dinginkan).

Kelebihan DFS adalah:
• Pemakain memori hanya sedikit, berbeda jauh dengan BFS yang harus menyimpan semua node yang pernah dibangkitkan.
• Jika solusi yang dicari berada pada level yang dalam dan paling kiri, maka DFS akan menemukannya secara cepat.

Kelemahan DFS adalah:
• Jika pohon yang dibangkitkan mempunyai level yang dalam (tak terhingga), maka tidak ada jaminan untuk menemukan solusi (Tidak Complete).
• Jika terdapat lebih dari satu solusi yang sama tetapi berada pada level yang berbeda, maka pada DFS tidak ada jaminan untuk menemukan solusi yang paling baik (Tidak Optimal).

def DFS (Graf, Awal, Tujuan):
Stack = [[Awal]]
Visited = set ()

while Stack:
tinggi_tumpukan = len(Stack)-1
jalur = Stack.pop(tinggi_tumpukan)
state = jalur[-1]

if state == Tujuan:
return jalur
elif state not in Visited:
for Tetangga in Graf.get(state, []):
jalur_baru = list(jalur)
jalur_baru.append(Tetangga)
Stack.append(jalur_baru)

Visited.add(state)

isi = len(Stack)
if isi == 0:
print(“tidak ditemukan”)
…………………………………………………………………………………………

Mau yang lebih simple ..? 🙂
Di coding ini prosesnya akan dipersingkat dengan menggunakan Jalan sebagai Tempatnya Lalu menambahkan Tetangga dari Akar dengan Jalan… Nah jika Tetangga sudah sama dengan Tujuan Tinggal mengembalikan nilai Jalannya..

Untuk lebih Jelasnya simak Coding dibawah ini !!

def BFS(Graf, Awal, Tujuan):
Queue = [(Awal, [Awal])]

while Queue:
(Akar, Jalan) = Queue.pop(0)

for Tetangga in Gate [Akar] – set(Jalan):
if Tetangga == Tujuan:
yield Jalan + [Tetangga]
print (“jalan ditemukan :”,”\n”)
return Jalan
else:
Queue.append((Tetangga, Jalan + [Tetangga]))

isi = len (Queue)
if isi == 0:
print (“Jalan tidak ditemukan !”)

def DFS(Graf, Awal, Tujuan):
Stack = [(Awal, [Awal])]

while Stack:
Tumpukan = len(Stack)-1
(Akar, Jalan) = Stack.pop(Tumpukan)

for Tetangga in Gate [Akar] – set(Jalan):
if Tetangga == Tujuan:
yield Jalan + [Tetangga]
print (“jalan ditemukan :”,”\n”)
return Jalan
else:
Stack.append((Tetangga, Jalan + [Tetangga]))

isi = len (Stack)
if isi == 0:
print (“Jalan tidak ditemukan !”)

#Kalau ada kata-kata yang kurang pass mohon dimaafkan 😀
#Mari kita sama-sama BELAJAR

Deteksi Tepi dengan metode Robert, Prewitt dan Sobel

Edge Detection pada suatu citra adalah suatu proses yang menghasilkan tepi-tepi dari obyek-obyek citra, tujuannya adalah Untuk menandai bagian yang menjadi detail gambar/citra untuk memperbaiki detail dari gambar/citra yang blur, yang terjadi akrena adanya efek dari proses akuisisi citra Suatu titik (x,y) dikatakan sebagai tepi (edge) dari suatu citra bila titik tersebut mempunyai perbedaan yang tinggi dengan tetangganya. dan berikut pengertian dari beberapa metode Sobel, Prewitt, Laplace, Robert, dan Canny.

A. Sobel

Metode ini mengambil prinsip dari fungsi laplace dan gaussian yang dikenal sebagai fungsi untuk membangkitkan HPF, dan kelebihan dari metode sobel ini adalah mengurangi noise sebelum melakukan perhitungan deteksi tepi.

B. Prewitt

Metode Prewitt merupakan pengembangan metode robert dengan menggunakan filter HPF yang diberi satu angka nol penyangga. Metode ini mengambil prinsip dari fungsi laplacian yang dikenal sebagai fungsi untuk membangkitkan HPF.

C. Robert

Metode Robert adalah nama lain dari teknik differensial pada arah horisontal dan differensial pada arah vertikal, dengan ditambahkan proses konversi biner setelah dilakukan differensial. Maksud konversi biner adalah meratakan distribusi warna hitam dan putih.

mari kita coba :

no-2

Konversi Citra 10 x 10 kedalam Grayscale, lalu dikompresi dengan metode Huffman, RLE, dan Kuantitas

Pengolahan citra adalah salah satu cabang dari ilmu informatika. Pengolahan citra berkutat pada usaha untuk melakukan transformasi suatu citra/gambar menjadi citra lain dengan menggunakan teknik tertentu.

mari kita coba :

coba2

A. PENGERTIAN
Kompresi Citra adalah aplikasi kompresi data yang dilakukan terhadap citra digital dengan tujuan
untuk mengurangi redundansi dari untuk mengurangi redundansi dari data-data yang terdapat dalam citra sehingga dapat disimpan atau ditransmisikan secara efisien.

B. TUJUAN
Kompresi citra bertujuan meminimalkan kebutuhan memori untuk merepresentasikan citra digital
dengan mengurangi duplikasi data di dengan mengurangi duplikasi data di dalam citra sehingga memori yang dibutuhkan menjadi lebih sedikit daripada representasi citra semula.

C. MANFAAT

  • Waktu pengiriman data pada saluran komunikasi data lebih singkat,Contoh : pengiriman gambar dari fax, video conferencing, handphone, download dari internet, pengiriman data medis, pengiriman internet, pengiriman data medis, pengiriman dari satelit, dsb.
  • Membutuhkan ruang memori dalam storage lebih sedikit dibandingkan dengan citra yang tidak dimampatkan.

Proses kompresi merupakan proses mereduksi ukuran suatu data untuk menghasilkan
representasi digital yang padat atau memampatkan namun tetap dapat mewakili kuantitas informasi yang terkandung pada data tersebut.
Pada citra, video atau audio, kompresi mengarah pada minimisasi jumlah bit rate untuk representasi digital.

Semakin besar ukuran citra, semakin besar memori yang dibutuhkan. Namun kebanyakan citra mengandung duplikasi data, yaitu :

  • Suatu pixel memiliki intensitas yang sama dengan dengan pixel tetangganya, sehingga penyimpanan setiap pixel memboroskan tempat.
  • citra banyak mengandung bagian (region) yang sama, sehingga bagian yang sama ini tidak perlu dikodekan berulangkali karena mubazir atau redundan.
  • D.KRITERIA PEMAMPATAN
    • Waktu pemampatan
    • Kebutuhan memory
    • Kualitas pemampatan (fidelity)
    1
    • Format Keluaran

    E. JENIS PEMAMPATAN
    • Pendekatan Statistik
    – Melihat frekuensi kemunculan derajat keabuan pixel
    • Pendekatan Ruang
    – Melihat hubungan antar pixel yang mempunyai derajat
    keabuan yang sama pada wilayah dalam citra
    • Pendekatan Kuantisasi
    – Mengurangi jumlah derajat keabuan yang tersedia
    • Pendekatan Fraktal
    – Kemiripan bagian citra dieksploitasi dengan matriks transformasi.

    D. TEKNIK KOMPRES CITRA
    1. Loseless Compression
    o. Teknik kompresi citra dimana tidak ada satupun informasi citra yang dihilangkan.
    o. Menghasilkan citra yang sama dengan citra semula
    o. Nisbah/ratio pemampatan sangat rendah
    o. Biasa digunakan pada citra medis.
    o. Metode loseless : Run Length Encoding, Entropy Encoding (Huffman, Aritmatik), dan Adaptive
    Dictionary Based (LZW) .2

  1.  Lossy Compression
    o. Ukuran file citra menjadi lebih kecil dengan menghilangkan beberapa informasi dalam citra asli.
    o. Teknik ini mengubah detail dan warna pada file citra menjadi lebih sederhana tanpa terlihat perbedaan yang mencolok dalam pandangan manusia, sehingga ukurannya menjadi lebih kecil.
    o. Biasanya digunakan pada citra foto atau image lain yang tidak terlalu memerlukan detail citra, dimana kehilangan bit rate foto tidak berpengaruh pada citra.
    o. Menghasilkan citra yang hampir sama dengan citra semula.
    o. Ada informasi yang hilang akibat pemampatan tapi masih bisa ditolerir oleh persepsi mata
    o. Nisbah/ratio pemampatan tinggio
    o. Contoh, JPEG dan Fraktal

    # Metode Pemampatan Huffman

  2. Urutkan nilai keabuan berdasarkan frekuensi kemunculannya.
  3. Gabung dua pohon yang frekuensi kemunculannya paling kecil.
  4. Ulangi 2 langkah diatas sampai tersisa satu pohon biner.
  5. Beri label 0 untuk pohon sisi kiri dan 1 untuk pohon sisi kanan.
  6. Telusuri barisan label sisi dari akar ke daun yang menyatakan kode Huffman.

Contoh, citra 64×64 dengan 8 derajat keabuan (k)

3

4 5 7 8 9

 

 

  1. Kode untuk setiap derajat keabuan
    10
  2. Ukuran citra sebelum dimampatkan (1 derajat keabuan = 3bit) adalah 4096×3 bit = 12288 bit
    o. Ukuran citra setelah pemampatan

11

#Metode Pemampatan RLE

• Run Length Encoding
Cocok untuk pemampatan citra yang memiliki kelompok pixel berderajat keabuan yang sama
• Contoh citra 10×10 dengan 8 derajat keabuan
1312-1
Pasangan derajat keabuan (p)  dan jumlah pixel (q)

• Ukuran citra sebelum dimampatkan (1 derajat keabuan = 3 bit) adalah 100 x 3 bit = 300 bit
• Ukuran citra setelah pemampatan (run length =4) adalah (31 x 3) + (31 x 4) bit = 217 bit

 14

 

 

#Metode Pemampatan Kuantisasi

  • Buat histogram citra yang akan dimampatkan. P jumlah pixel
  • Identifikasi n buah kelompok di histogram sedemikian sehingga setiap kelompok mempunyai kira-kira P/n pixel
  • Nyatakan setiap kelompok dengan derajat keabuan 0 sampai n-1.  Setiap kelompok dikodekan kembali dengan nilai derajat keabuan yang baru .
  • Contoh, Citra 5 x 1315
    Akan dimampatkan dengan 4 derajat keabuan (0 – 3) atau dengan 2 bit16
  • Setelah dimampatkan
  • 17Ukuran sebelum pemampatan (1 derajat keabuan = 4 bit) adalah 65 x 4 bit = 260 bit
    • Ukuran citra setelah pemampatan (1 derajat keabuan = 2 bit) adalah 65 x 2 bit = 130 bit

18

Mengubah Background dengan Tresholding

Mengubah Background Foto dengan Thresholding

Pada kesempatan kali ini saya akan menunjukan cara mengubah background foto dengan metode Thresholding yang saya terapkan pada matlab. Apa itu Thresholding? threshoding adalah operasi ambang batas, atau memetakan pixel yang memenuhi syarat ambang batas dipetakan ke satu nilai pixel yang dihendaki, rumusnya sebagai berikut.

 

Rumus :

rumus1

Penerapan pada Matlab :

no-3

Mencoba Brightness dan Contras pada Citra RGB

 

Yang sudah saya coba:

matlab1

Kontras (Contrast)

Kontras adalah tingkat penyebaran piksel-piksel kedalam intensitas warna. Ada 3 macam kontras, yaitu Rendah, Tinggi dan Normal.

1.Rendah

citra yang memiliki kontras rendah dapat terjadi karena kurangnya pencahayaan , citra ini memiliki kurva histogram yang sempit(tingkat penyebaran warna tidak sampai ke hitam pekat dan putih terang)

2. Tinggi

Kurva histogram terlalu besar, sebaran intensitas terang dan gelap merata keseluruh skala intensitas

3. Normal

Kurva histogram tidak terlalu besar dan tidak sempit

Ada beberapa cara untuk melakukan perhitungan kontras, namun yang saya tampilkan sekarang adalah dengan rumus berikut:

Dimana:
G= koefisien penguatan kontras
P=nialai grayscale yang dipakai sebagai pusat pengkontrasan

contoh perhitungan:

 Kode Program dengan VB.Net

bmap = New Bitmap(picAwal.Image)’Gambar asli dijadikan gambar Bitmap
picAwal.Image = bmap
Dim tempbmp As New Bitmap(picAwal.Image) ‘deklarasi gambar Bitmap dari gambar asli untuk diproses
Dim Red, Green, Blue, tc, g As Integer
Dim X, Y As Integer
tc = 2
g = 50
ProgressBar1.Width = picAwal.Width
ProgressBar1.Show()
With tempbmp
For X = 0 To .Height – 1
For Y = 0 To .Width – 1
Red = CInt(.GetPixel(Y, X).R)’ambil nilai warna merah (Red) pada pixel(Y,X)
Green = CInt(.GetPixel(Y, X).G)’ambil nilai warna hijau (Green) pada pixel(Y,X)
Blue = CInt(.GetPixel(Y, X).B)’ambil nilai warna biru (Blue) pada pixel(Y,X)                    ‘hitung kontras
Red = tc * (Red – g) + g
Blue = tc * (Blue – g) + g
Green = tc * (Green – g) + g
‘kondisi jika melibihi nilai pixel
If (Red > 255) Then
Red = 255
End If
If (Blue > 255) Then
Blue = 255
End If
If (Green > 255) Then
Green = 255
End If
If (Red <0) Then
Red = 0
End If
If (Blue < 0) Then
Blue = 0
End If
If (Green <0) Then
Green = 0
End If
bmap.SetPixel(Y, X, Color.FromArgb(Red, Green, Blue)) ‘simpan warna baru pada pixel(Y,X)
Next

Next
End With

Keceraha (Brightness)

Sebuah citra dengan derajat keabuan 256, akan tampak gelap jika seluruh komponen warna berada mendekati 0. sebaliknya, citra akan tampak terang jika seluruh komponennya mendekati angka 255.h

brightness adalah proses untuk kecerahan citra, jika intensitas pixel dikurangi dengan nilai tertentu maka citra akan menjadi lebih gelap, dan sebaliknya jika intensitas pixelnya ditambah dengan nilai tertentu maka akan lebih terang

adapun rumus brightness adalah sbb:

dimana
f0(x,y) : Nilai pixel pada titik x,y setelah brightness
fi(x,y) : Nilai Pixel pada titik x,y citra asli
k       : Nilai Penguatan kecerahan

nah rumus diatas digunakan untuk citra grayscale, namaun jika digunakan untuk RGB maka rumusnya menjadi :

dengan aturan jika intensitas pixel berada antara 0-255 maka, jika pixel >255 diset menjadi 255 dan jika pixel<0 diset menjadi 0.
contoh perhitungan:

contoh hasil penambahan kecerahan:

Citra semula(kiri) dan citra hasil(kanan)

Contoh Program dengan VB.Net

bmap = New Bitmap(picAwal.Image) ‘Gambar asli dijadikan gambar Bitmap
picAwal.Image = bmap
Dim tempbmp As New Bitmap(picAwal.Image) ‘deklarasi gambar Bitmap dari gambar asli untuk diproses
Dim Red As Integer, Green As Integer, Blue As Integer
Dim X, Y As Integer
Dim tb As Integer
tb = 75
With tempbmp
For X = 0 To .Height -1
For Y = 0 To .Width – 1
Red = CInt(.GetPixel(Y, X).R)’ambil nilai warna merah (Red) pada pixel(Y,X)
Green = CInt(.GetPixel(Y, X).G)’ambil nilai warna hijau (Green) pada pixel(Y,X)
Blue = CInt(.GetPixel(Y, X).B)’ambil nilai warna biru (Blue) pada pixel(Y,X)
‘penambahan masing red, blue, green dengan nilai kecerahan

Red = Red + tb
Green = Green + tb
Blue = Blue + tb
‘batasi agar tidak lebih dari 255
If (Red > 255) Then
Red = 255
End If
If (Blue > 255) Then
Blue = 255
End If
If (Green > 255) Then
Green = 255
End If
bmap.SetPixel(Y, X, Color.FromArgb(Red, Green, Blue)) ‘simpan warna baru pada pixel(Y,X)
Next
Next
End With

Program Algoritma Array

ARRAY pada bahasa C

ARRAY adalah kumpulan dari nilai-nilai data bertipe sama dalam urutan tertentu yang menggunakan sebuah nama yang sama.

Macam-macam Array:

»     Array berdimensi satu

Setiap elemen array dapat diakses melalui index. Index array secara default dimulai dari 0.

BU :  tipe_array  nama_array  [ukuran]

»     Array berdimensi dua

Array dua dimensi merupakan array yang terdiri dari m buah baris dan n buah kolom. Bentuknya dapat berupa matriks atau tabel.

BU :  tipe_array  nama_array  [baris] [kolom]

»     Array multidimensi

Array multidimensi merupakan array yang mempunyai ukuran lebih dari dua. Bentuk pendeklarasian array ini sama saja dengan deklarasi array dimensi satu maupun dimensi dua.

BU :  tipe_array  nama_array  [ukuran1] [ukuran2] …. [ukuranN]

………..

#include <stdio.h>

//=====================kamus================================
int array[100], n, c;
main()
{
//=====================deskripsi============================

printf(“masukkan sebuah element \n”);
scanf (“%d”, &n);

printf(“masukkan %d element\n”, n);

for (c=0 ; c<n ; c++)//looping yang digunakan untuk perulangan inputan.
{
scanf (“%d”, &array[c]);//untuk menginputkan angka yang ingin dimasukan.
}

printf(“maka array yang terbentuk adalah :\n”);

for (c=0 ; c<n ; c++)//looping yang digunakan untuk perulangan outputan.
{

printf(“array [%d] = %d \n”, c, array[c]);// untuk menghasilkan outputan .
}
return 0;
}
output :
misal element n adalah 5 .
array[c] {1,2,3,4,5}.

jadi hasilnnya ..

maka array yang terbentuk adalah :
array 0 = 1
array 1 = 2
array 2 = 3
array 3 = 4
array 4 = 5

 

langsung saja liat tutorial dibawah ini !! 😉

sekian dulu ya guys ulasannya, tugu posting berikutnya ….

bye!! 🙂