Tugas 4 : Search mlm menggunakn Breadth First Search

         Breadth-first search adalah 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

Pseudocode

1 Prosedur Breadth First Search (G, v):
2 membuat antrian Q
3 masukkan antrian v ke Q
4 mark v
5 sedangkan Q tidak kosong:
6 t ← Q.keluarkan antrian ( )
7 jika t adalah apa yang kita cari:
8 kembali t
9 untuk semua tepi e di G.tepi yang berdekatan (t), maka lakukan
12 u ← G.puncak yang berdekatan (t, e)
13 jika u tidak ditandai:
14 maka tandai u
15 masukkan antrian u ke Q

 misalnya dari pohon mlm berikut :

mencari rendi dengan nomer 34

Tugas 1 : Subsidi BBM

TUGAS 1

SOAL :

Membuat notasi algoritma untuk persoalan pemakaian bahan bakar bersubsidi harus mobil dengan tahun perakitan dibawah tahun 1990 dan bukan mobil sedan.

PENYELESAIAN :

Notasi I:

1.      Jika ada mobil masuk, maka harus di lihat dulu tahun perakitan dan jenis mobil tersebut.

2.      Jika mobil tersebut termasuk mobil sedan maka, mobil tersebut tidak boleh menngunakan BBM bersubsidi walaupun tahun perakitan dibawah tahun 1990.

Notasi II :

1.      Mulai

2.      Mobil masuk SPBU

3.      Petugas memeriksa jenis mobil

4.      Jika termasuk mobil sedan, maka petugas menyarankan kepada pengemudi untuk tidak menggunakan BBM bersubsidi.

5.      Jika bukan termasuk / jenis mobil sedan maka, petugas akan memeriksa tahun perakitan

6.      Jika tahun perakitan di atas tahun 1990. Maka petugas menyarankan pengemudi untuk tidak mengunakan BBM bersubsidi.

7.      Jika tahun perakitan di bawah tahun 1990, maka diperbolehkan untuk menggunakan BBM bersubsidi

8.      Selesai.

Notasi III :

Tugas 3 Merge Sort

Algoritma Merge Sort ialah algoritma pengurutan yang berdasarkan pada strategi divide and conquer. Algoritma untuk merge sort ialah sebagai berikut :
1. Untuk kasus n=1, maka table a sudah terurut sendirinya (langkah solve)
2. Untuk kasus n>1, maka :
      a. DIVIDE: bagi table a menjadi dua bagian, bagian kiri dan bagian kanan, masing-masing bagian berukuran n/2 elemen.
      b. CONQUER: secara rekursif, terapkan algoritma D-and-C pada masing-masing bagian. MERGE: gabung hasil pengurutan kedua bagian sehingga diperoleh table a yang terurut.

Tugas 2 Insertion Sort

Insertion Sort

Metode insertion sort ini akan lebih mudah dipahami dengan secara langsung mempelajari setiap tahapnya.

Tahap 1 :

Dimulai dari A[1]

Simpan nilai A[1] pada sebuah variabel (misal x)

Geser masing-masing satu langkah ke kanan semua nilai yang berada pada kiri A[1] satu per satu  jika nilai tersebut lebih besar dari x

Insert (sisipkan) x di bekas tempat nilai yang terakhir digeser.

Tahap 2 :

Simpan nilai A[2] pada variabel x.

Geser masing-masing satu langkah ke kanan semua nilai yang berada pada kiri A[2] satu per satu  jika nilai tersebut lebih besar dari x

Insert (sisipkan) x di bekas tempat nilai yang terakhir digeser.

Tahap berikutnya dan seterusnya hingga terakhir tahap ke N-1 (untuk array dengan N elemen).

Instruksi pergeseran ke kanan adalah A[i]=A[i - 1], sehingga nilai A[i] akan hilang (ditimpa oleh nilai A[i-1] oleh karena itu pada awal tahap A[i] disimpan pada sebuah variabel.

Sudah ada array satu dimensi sudah ada isinya, diilustrasikan sebagai berikut :

	0	1	2	3	4	5
A[6]	17	11	8	25	3	15

Akan dirurutkan ascending sehingga dihasilkan urutan data seperti berikut:

	0	1	2	3	4	5
A[6]	3	8	11	15	17	25

Maka proses pengurutan tahap demi tahap dengan menggunakan metode insertion sort adalah sebagai berikut :

Tahap 1 (dimulai dari A[1])

17

11

8

25

3

15

x=A[1]= 11

17

17

8

25

3

15

Nilai di kiri A[1] adalah A[0], A[0]>x, geser ke kanan

11

17

8

25

3

15

Tidak ada lagi nilai di kiri, jadi insert x ke A[0], A[0]=x

Tahap 2 (dimulai dari A[2])

11

17

8

25

3

15

x=A[2]= 8

11

17

17

25

3

15

Nilai di kiri A[2] adalah A[1], A[1]>x, geser ke kanan

11

11

17

25

3

15

Nilai di kiri A[1] adalah A[0], A[0]>x, geser ke kanan

8

17

8

25

3

15

Tidak ada lagi nilai di kiri, jadi insert x ke A[0], A[0]=x

Tahap 3 (dimulai dari A[3])

8

11

17

25

3

15

x=A[3]= 25

8

11

17

25

3

15

Nilai di kiri A[3] adalah A[2], A[2]<x

A[2] tidak lebih besar dari x maka tidak perlu melanjutkan ke nilai kirinya lebih lanjut karena sudah pasti tidak lebih besar dari x juga.

Jadi proses insert x pada A[3], A[3]=x

Tahap 4 (dimulai dari A[4])

8

11

17

25

3

15

x=A[4]= 3

8

11

17

25

25

15

Nilai di kiri A[4] adalah A[3], A[3]>x, geser ke kanan

8

11

17

17

25

15

Nilai di kiri A[3] adalah A[2], A[2]>x, geser ke kanan

8

11

11

17

25

15

Nilai di kiri A[2] adalah A[1], A[1]>x, geser ke kanan

8

8

11

17

25

15

Nilai di kiri A[1] adalah A[0], A[0]>x, geser ke kanan

3

8

11

17

25

15

Tidak ada lagi nilai di kiri, jadi insert x ke A[0], A[0]=x

Tahap 5 (dimulai dari A[5])

3

8

11

17

25

15

x=A[5]= 15

3

8

11

17

25

25

Nilai di kiri A[5] adalah A[4], A[4]>x, geser ke kanan

3

8

11

17

17

25

Nilai di kiri A[4] adalah A[3], A[3]>x, geser ke kanan

3

8

11

15

17

25

Nilai di kiri A[3] adalah A[2], A[2]<x

A[2] tidak lebih besar dari x maka tidak perlu melanjutkan ke nilai kirinya lebih lanjut karena sudah pasti tidak lebih besar dari x juga.

Proses pergeseran terakhir pada A[3], maka proses insert x pada A[3], A[3]=x

Flowchart Insertion