BAB IV. Penyusunan Algoritma

BAB IV Penyusunan Algoritma


4.1 Penyusunan Algoritma Pada bab sebelumnya telah dimodelkan permasalahan lampu lalu lintas kedalam pewarnaan titik pada graf kabur. Selanjutnya dari bentuk model ini akan disusun suatu algoritma pemrograman berdasarkan bahasa pemrograman Borland Delphi 7. Dalam penyusunan algoritma pemrograman ini digunakan dua macam algoritma sebagai acuan. Algoritma yang jadi acuan ini adalah algoritma degree of saturation (DSATUR) dan algoritma Backtracking Sequential Coloring (BSC). Algoritma pemrograman yang akan disusun dibagi kedalam tahap-tahap berikut : a. Penentuan derajat tiap titik b. Pengurutan titik-titik secara descending c. Pencarian degree of saturation d. Penentuan himpunan warna bebas (U) e. Pencarian nilai U terkecil f. Backtracking Sequential Coloring (BSC)

55 Algoritma pewarnaan titik pada graf dengan sisi kabur untuk pengaturan lampu lalu lintas


(*================fungsi menentukan derajat tiap titik=================*) function GetDegOne(AdMat : Matrix; Kelas : integer): ColorArray; var i, j : integer; begin for i:=1 to n do Result[i]:=0;

for i:=1 to n do for j:=1 to n do if (AdMat[i,j] <= Kelas)and(AdMat[i,j] > 0) then Result[i]:=Result[i]+1; end;

(*============fungsi mengurutkan titik secara descending===============*) function OrderingVertex(deg : ColorArray) : VertexArray; var i, j, max : integer; tempDeg : VertexArray; begin for i:=1 to n do tempDeg[i]:=deg[i];

// deg[i]= derajat titik i

for i:=1 to n do 56 Algoritma pewarnaan titik pada graf dengan sisi kabur untuk pengaturan lampu lalu lintas


begin max:=1; for j:=2 to n do if tempDeg[j]>tempDeg[max] then max:=j; Result[i-1]:=max; tempDeg[max]:=-1; end; end;

(*===============prosedur pencarian degree of saturation===============*) function GetDSaturOne(AdMat : Matrix ; deg, F : ColorArray; Kelas : integer) : integer; var i, j, degs, maxdegs, v : integer;

// degs= derajat saturasi titik

DiffColors : ColorSet; begin maxdegs:=-1; for i:=1 to n do begin if F[i]=0 then begin degs:=0; DiffColors:=[]; for j:=1 to n do 57 Algoritma pewarnaan titik pada graf dengan sisi kabur untuk pengaturan lampu lalu lintas


if ((AdMat[i,j]<=Kelas)and(AdMat[i,j]>0)and((F[j]<>0)and not(F[j] in DiffColors)))then begin inc(degs); DiffColors:=DiffColors+[F[j]]; end; if (degs>maxdegs) or ((degs=maxdegs)and(deg[i]>deg[v])) then begin maxdegs:=degs; v:=i; end; end; end; Result:=v; end;

(*==========prosedur menentukan himpunan warna bebas(U)=============*) function GetUOne(AdMat : Matrix; Col, OCN, v : integer; F : ColorArray; Kelas : integer):ColorSet; var i, UB, temp: integer; SNC : ColorSet; // himpunan warna verteks yang bertetangga U : ColorSet; begin SNC:=[]; 58 Algoritma pewarnaan titik pada graf dengan sisi kabur untuk pengaturan lampu lalu lintas


for i:=1 to n do begin temp := AdMat[i,v]; if ((temp <= Kelas) and (temp > 0) and (F[i]<>0)) then SNC:=SNC+[F[i]]; end;

U:=[]; UB:= min(Col+1,OCN-1); for i:=1 to UB do if not(i in SNC) then U:=U+[i]; Result:=U; end;

(*===================fungsi mencari nilai U terkecil=================*) function MinValue(U : ColorSet): integer; var i : integer; begin for i:=1 to MaxVertex do If i in U then break; Result:=i; end;



function fmax(Fopt:ColorArray):byte; var i, max : byte; begin max:=1; for i:=2 to n do if Fopt[i]>Fopt[max] then max:=i; Result:=Fopt[max]; end; (*========================fungsi BSC==========================*) function BSCOne(AdMat : Matrix ; nVertex : integer; Kelas : integer) : ColorArray; var i, j, v : integer; A : VertexArray; U : ColorSet;

// A urutan verteks berdasarkan derajat secara descending // Himpunan warna bebas

start, optColorNumber, C, l : integer; freeColors : array[1..MaxVertex]of ColorSet; colors : array[-1..MaxVertex]of integer; back : Boolean; VerDeg, Fopt, F : ColorArray; begin n:=nVertex;

// nVertex= banyak titik

for i:=1 to n do

// derajat saturasi setiap titik=0

F[i]:=0; 60 Algoritma pewarnaan titik pada graf dengan sisi kabur untuk pengaturan lampu lalu lintas


VerDeg:=GetDegOne(AdMat, Kelas); A:=OrderingVertex(VerDeg);

// menentukan derajat setiap titik

// pengurutan derajat titik secara descending

start:=0; optColorNumber:=n+1; v:=A[0]; colors[-1]:=0; U:=[1]; freeColors[v]:=U; while (start>=0) do

// setiap titik diwarnai pada loop dibawah ini

begin back:=false; for i:= start to n-1 do begin if i>start then

// cari titik yang belum diwarnai dan mempunyai derajat saturasi terbesar

begin v:=GetDSaturOne(AdMat, VerDeg, F, Kelas); U:=GetUOne(AdMat,colors[i-1],optColorNumber,v, F, Kelas); end;

if U<>[] then begin C:=MinValue(U);

// warna bebas yang dipilih

F[v]:=C;

// pewarnaan untuk titik v

freeColors[v]:=U-[C]; 61 Algoritma pewarnaan titik pada graf dengan sisi kabur untuk pengaturan lampu lalu lintas


l:=colors[i-1]; colors[i]:= max(C,l); end // U = ∅ dilakukan penelusuran kembali, mundur satu posisi

else begin start:=i-1; back:=true; break;

// keluar dari loop for

end; end;

// akhir loop for

if back then begin if start>=0 then begin v:=A[start];

// titik awal yang baru

F[v]:=0;

// hapus warna v

U:=freeColors[v]; end; end else

// loop diatas dilalui tanpa berhenti

begin for i:=1 to n do Fopt[i]:=F[i];

// menyimpan pewarnaan yang optimal pada saat ini

optColorNumber:=colors[n-1]; for i:=0 to n-1 do 62 Algoritma pewarnaan titik pada graf dengan sisi kabur untuk pengaturan lampu lalu lintas


if F[A[i]]=optColorNumber then

// i = indeks terkecil dimana F[A[i]]=optColorNumber

break; start:=i-1; if start<0 then break;

// keluar dari loop while

for j:=start to n-1 do // hapus warna A[j], dimana j ≥ start

F[A[j]]:=0; for i:=0 to start do begin v:=A[i]; U:=freeColors[v];

for j:=optColorNumber to MaxVertex do // semua warna ≥ optColorNumber dihilangkan dari U

U:=U-[j]; freeColors[v]:=U; end;

// disini v= A[start]; U=freecolors(v)

end; end;

// akhir dari loop while

Fopt[n+1]:=fmax(Fopt);

//Bilangan Kromatik

Result:=Fopt; end;

end.



4.2 Simulasi Program Untuk Beberapa Kasus Permasalahan Lampu Lalu Lintas Pada bab sebelumnya telah dimodelkan permasalahan lampu lalu lintas ke dalam bentuk pewarnaan titik pada graf kabur. Di awal bab ini pula, telah disusun suatu algoritma pemrograman dari bentuk model yang telah dilakukan sebelumnya. Selanjutnya akan diberikan suatu simulasi dari algoritma pemrograman yang telah disusun ini sebagai salah satu cara dalam memodelkan permasalahan lampu lalu lintas.

4.2.1 Implementasi Algoritma Antar muka dari perangkat lunak yang dibuat seperti pada gambar dibawah ini :

Gambar 4.1 64 Algoritma pewarnaan titik pada graf dengan sisi kabur untuk pengaturan lampu lalu lintas


Langkah-langkah pengoperasian perangkat lunak adalah sebagai berikut :

Tentukan μ pada kolom banyak tingkat intensitas sisi. μ atau tingkat intensitas sisi ini merupakan kasus-kasus yang akan diselidiki. Sebagai contoh, misal μ = 3 maka dapat dinyatakan μ = 1 sebagai kondisi tingkat keterkaitan high, μ = 2 sebagai kondisi tingkat keterkaitan medium dan μ = 3 sebagai kondisi tingkat keterkaitan low. Setelah banyak tingkat intensitas sisi diisi kemudian klik enter.

Isi banyak titik dari graf G. Titik yang diisi merupakan banyaknya lintasan yang akan dimodelkan. Setelah itu klik enter.

Graf acak dapat di generate dengan memasukkan kepadatan sisi yang direpresentasikan dengan angka 1 sampai 10 atau dengan mengisi sendiri matriks ketetanggaannya. Dalam mengisi matriks ketetanggaan, keterkaitan antara satu titik dengan titik lainnya bergantung pada μ yang ditentukan sebelumnya. Sebagai gambaran, apabila μ = 3 maka untuk titik-titik yang dianggap

memiliki

keterkaitan

high

dapat

diisikan

pada

matriks

ketetanggaannya dengan angka 1, apabila tingkat keterkaitan diantara titik dianggap medium dapat diisikan dengan angka 2 dan 3 untuk titik dengan tingkat keterkaitan low.

Setelah semua input yang dibutuhkan telah dimasukkan, klik tombol proses coloring.

Untuk melihat hasil untuk setiap μ , dapat dilihat dengan mengeklik pada gambar sesuai dengan kondisi μ yang ingin diamati. Sebagai gambaran, apabila kondisi pada μ = 1 yang ingin diamati maka pada gambar dapat dipilih angka 1. 65

Algoritma pewarnaan titik pada graf dengan sisi kabur untuk pengaturan lampu lalu lintas


4.2.2 Simulasi Program Untuk Permasalahan Sederhana Lampu Lalu Lintas Misalkan suatu sistem lampu lalu lintas di suatu perempatan jalan digambarkan sebagai berikut : A

D

B

C

Gambar 4.2

Bentuk model dari masalah ini telah dilakukan sebelumnya, selanjutnya akan dimodelkan kembali permasalahan ini dengan menggunakan simulasi program. Langkah-langkah yang akan dilakukan adalah sebagai berikut :

Masukan input sesuai dengan data yang dapat diamati berdasarkan gambar 4.2.

Gambar 4.3 66 Algoritma pewarnaan titik pada graf dengan sisi kabur untuk pengaturan lampu lalu lintas


Setelah setiap input dimasukkan akan didapatkan hasil simulasi untuk setiap

μ nya sebagai berikut :

Gambar 4.4 μ = h

Gambar 4.5 μ = m

Gambar 4.6 μ = l 67 Algoritma pewarnaan titik pada graf dengan sisi kabur untuk pengaturan lampu lalu lintas


Hasil simulasi diatas menunjukkan bahwa :

Pada saat μ = h , periode lampu hijau pada lampu lalu lintas adalah dua.

Pada saat μ = m , periode lampu hijau pada lampu lalu lintas adalah dua.

Pada saat μ = l , periode lampu hijau pada lampu lalu lintas adalah tiga.

Hasil simulasi ini menunjukkan hasil yang sama dengan model matematika lampu lalu lintas pada bab sebelumnya.

4.2.3 Simulasi Program Untuk Permasalahan Lampu Lalu Lintas Daerah Pertigaan Sukajadi Sistem lampu lalu lintas di daerah pertigaan Sukajadi digambarkan sebagai berikut :

A

B

C

Gambar 4.7

Bentuk model dari masalah ini telah kita lakukan sebelumnya, selanjutnya akan dimodelkan kembali permasalahan ini dengan menggunakan simulasi program. Langkah-langkah yang akan dilakukan adalah sebagai berikut :

Masukan input sesuai dengan data yang dapat diamati berdasarkan gambar 4.7.



Gambar 4.8



Gambar 4.9 μ = h

Gambar 4.10 μ = l



Hasil simulasi diatas menunjukkan bahwa :

Pada saat μ = h , periode lampu hijau pada lampu lalu lintas daerah pertigaan Sukajadi adalah tiga.

Pada saat μ = l , periode lampu hijau pada lampu lalu lintas daerah pertigaan Sukajadi adalah tiga.

Hasil simulasi ini menunjukkan hasil yang sama dengan model matematika lampu lalu lintas daerah pertigaan Sukajadi pada bab sebelumnya.

4.2.4 Simulasi Program Untuk Permasalahan Lampu Lalu Lintas Daerah Perempatan Merdeka Sistem lampu lalu lintas di daerah perempatan Merdeka digambarkan sebagai berikut : A

D

B

C

Gambar 4.11

Bentuk model dari masalah ini telah kita lakukan sebelumnya, selanjutnya akan dimodelkan kembali permasalahan ini dengan menggunakan simulasi program. Langkah-langkah yang akan dilakukan adalah sebagai berikut :

Masukan input sesuai dengan data yang dapat diamati berdasarkan gambar 4.11. 70

Algoritma pewarnaan titik pada graf dengan sisi kabur untuk pengaturan lampu lalu lintas


Gambar 4.12



Gambar 4.13 μ = h

Gambar 4.14 μ = m



Gambar 4.15 μ = l Hasil simulasi diatas menunjukkan bahwa :

Pada saat μ = h , periode lampu hijau pada lampu lalu lintas daerah perempatan Merdeka adalah dua.

Pada saat μ = m , periode lampu hijau pada lampu lalu lintas daerah perempatan Merdeka adalah dua.

Pada saat μ = l , periode lampu hijau pada lampu lalu lintas daerah perempatan Merdeka adalah tiga.

Hasil simulasi ini menunjukkan hasil yang sama dengan model matematika lampu lalu lintas daerah perempatan Merdeka pada bab sebelumnya.

72 Algoritma Pewarnaan titik graf fuzzy pada pengaturan lampu lalu lintas 68

BAB IV. Penyusunan Algoritma

Recommend Documents