Pengaturan Warna Pada Lampu Lalu Lintas

Pada tulisan kali ini, kita akan mencoba menyelesaikan permasalahan pada pembuatan lampu lalu lintas pada sebuah jalan simpang 5, kita akan mencoba menentukan jalur mana yg bisa berjalan dengan memberi lampu hijau, dan memberi lampu merah agar kendaraan pada lintasan yg lain berhenti, tujuannya adalah agar tidak terjadi tabrakan
mari kita lihat contoh gambarberikut

Gambar 1

Dari gambar diatas dapat kita peroleh informasi, bahwa jalur yang boleh melintas adalah dari A ke B, A ke C, A ke D, B ke C, B ke D, E ke B, E ke C, dan E ke D.

Penjadwalan Ujian

Kali ini kita akan mencoba memecahkan masalah penjadwalan dengan cara melakukan pewarnaan pada sebuah graf.

Graf digunakan untuk merepresentasikan objek-objek diskrit dan hubungan antara objek-objek. Representasi visual dari graf adalah dengan menyatakan objek dengan simpul, noktah, bulatan, titik, atau vertex, sedangkan hubungan antara objek dinyatakan dengan garis , edge atau ruas.

Pewarnaan graf adalah proses pelabelan setiap simpul dalam graf dengan label tertentu (warna) sehingga tidak ada dua simpul bertetangga yang memiliki warna sama. Warna yang kita gunakan untuk mewarnai objek diusahakan seminimal mungkin. Jumlah warna minimum yang dapat digunakan untuk mewarnai simpul disebut bilangan kromatik

Tabel berikut adalah contoh penjadwalan kuliah dalam graf:

Tabel 1 Contoh tabel penjadwalan kuliah 

Gambar 1

Pewarnaan (Coloring)

Pewarnaan yang kita bahas kali ini adalah sebuah cara yang digunakan untuk menyelesaiakan proses panjadwalan. Dimana dalam pewarnaan ini akan digambarkan dengan graph yang terdiri atas simpul, dan ruas

Dalam kehidupan sehari-hari sering kali kita dipusingkan oleh rumitnya penjadwalan, misalnya jika kita harus membuat jadwal ujian dimana ada beberapa mahasiswa yang mengikuti beberapa mata kuliah, tentunya agar mahasiswa tersebut dapat mengikuti  semua ujian, maka mata kuliah yang diambil secara bersamaan oleh satu siswa tersebut tidak boleh dijadwalkan pada hari dan jam yang sama. Atau misalnya kita mendapatkan proyek untuk membuat  lampu lalulintas di sebuah perlimaan, maka kita harus mengatur nyala lampu merah dan hijau agar tidak terjadi tabrakan. Saat ini kita akan belajar bersama salah satu metode untuk mengatasi permasalahan tersebut dengan metode pewarnaan (Coloring).

Knapsack Problem

Salah satu penggunaan metode greedy adalah untuk menyelesaiakan permasalahan Knapsack (Knapsack problem), knapsack problem bisa kita gambarkan, misalnya kita mempunyai sebuah kantong atau tas dengan kapasitas tertentu sedangkan dihadapan kita terdapat begitu banyak pilihan barang, maka kita harus memilih barang mana saja yang kira-kira akan kita ungkut sesuai kapasitas kantong yang kita miliki supaya kita bisa mendapatkan keuntungan yang sebesar-besarnya atau maksimal.

Dalam menghadapi masalah di atas, metode greedy memiliki 3 pilihan strategi pengangkutan, yaitu:

1. Greedy by Profit
   Strategi ini mengharapkan keuntungan maksimal dengan cara memasukan barang atau objek dengan nilai keuntungan terbesar terlebih dahulu ke dalam kantong atau knapsack. Jadi strategi ini hanya mempertimbangkan jumlah keuntungan dari sekumpulan barang, dengan catatan berat barang yang akan dibawa tidak melebihi kapasitas kantong yang kita miliki.
2. Greedy by weight 
   Pada strategi ini, kita berusaha memasukan barang sebanyak-banyaknya kedalam kantong, jadi barang atau objek yang dimasukan terlebih dahulu adalah barang dengan bobot paling ringan terlebih dahulu, dengan harapan dengan banyaknya barang atau objek yang terangkut kita bisa mendapatkan keuntungan sebesar-besarnya.

Metode Greedy

Metode greedy adalah metode yang digunakan untuk memecahkan persoalan optimasi, ada 2 macam persoalan optimasi, yaitu maksimasi dan minimasi, artinya dengan metode greedy kita bemaksud mencari solusi terbaik, yaitu solusi yang benilai minimum atau maksimum dari sekumpulan alternatif solusi yang ada.

arti kata greedy sendiri adalah RAKUS, namun maksud dari metode grredy adalah kita melihat solusi optimal lokal, atau solusi optimal yang tampak didepan mata, dengan harapan mendapatkan solusi optimal secara global atau secara keseluruhan

Contohnya adalah pada kasus penukaran uang, misalkan kita memiliki uang senilai 32 dan akan kita tukarkan dengan koin, uang koin pecahan yang tersedia adalah 1, 5, 10, 25, jika kita mengharapkan agar pecahan yang kita miliki sedikit mungkin maka kita bisa menggunakan metode greedy dengan cara memilih pecahan terbesar terlebih dahulu. mari kita lihat