NP-Completeness and the TSP

Teori Kompleksitas Komputasional

•Masalah terbagi dua

•Mudah: dapat diselesaikan oleh algoritme yang berjalan dalam waktu polinomial

•Sulit: tidak mudah

•Dalam teori kompleksitas komputasional, permasalahan ‘sulit’ tidak termasuk kelas kompleksitas apapun, karena tidak diketahui berapa waktu penyelesaiannya

•Teori ini dibatasi hanya untuk masalah keputusan (ya atau tidak)

TSP dan Masalah keputusan

•Masalah TSP dapat diubah menjadi masalah keputusan

•Caranya: buat dua algoritme

•TSP_SOLUTION: Masukan berupa graf dan biaya setiap edge

•TSP_DECISION: Masukan ditambah dengan nilai batas C. Keluaran ‘Ya’ apabila ada rute dengan biaya kurang dari C

•Algoritmenya seperti berikut

TSP_SOLUTION(G, E, V, c)

   C = FIND_OPTIMAL_COST(G, E, V, c)

FOR EACH edge I ON G

CI = unlimited.

IF TSP_DECISION(G, E, V, c, C) == ’YES’

REMOVE I from E.

•Waktu Pengerjaan TSP_SOLUTION polinomial jhj TSP_DECISION juga polinomial

Definisi formal masalah keputusan

•Ada dua

•Kelas P (polynomial): dapat diselesaikan oleh algoritme deterministik dalam waktu polinomial

•NP (non-polynomial): tidak dapat diselesaikan dalam waktu polynomial

Tiga formulasi kelas NP

•Properti singkat (succint property)

•setiap “ya” dapat disertifikasi dengan waktu polinomial

•Konstruksi non-deterministik

•Ketika masalah dipecahkan menggunakan algoritme non-deterministik

•Pemrograman Integer

•Untuk masalah yang dapat diredukse ke pemrograman integer dalam waktu polinomial

•Jika A adalah masalah keputusan, maka A memiliki sertifikat properti singkat, A ∈ NP dan A dapat dialihkan ke Integer Programming dalam waktu polinomial

•Karena P ⊆ NP, maka jika A ∈ P, maka A ∈ NP.

Dimana NP-Complete?

•Setiap masalah NP-hard dapat direduksi menjadi beberapa masalah NP-hard lainnya B. yaitu, masalah NP-hard dimana  X ∈ NP dapat ditransformasikan ke B pada waktu polinomial sehingga solusi untuk B akan menghasilkan solusi untuk X. Dalam hal ini, B dianggap NP-complete

•Jika Anda bisa membuktikan bahwa masalah NP-complete B ∈ P, maka Anda telah menunjukkan bahwa P = NP

•Jika Anda dapat membuktikan bahwa masalah NP-complete B ∉ P, maka Anda telah menunjukkan bahwa P ≠ NP

•apakah P = NP?

•Saat ini, belum ada yang dapat membuktikan bahwa P = NP atau P ≠ NP

Mengapa TSP disebut NP-Complete?

•Kita ambil suatu masalah H yang NP-complete. Kemudian, kita akan menunjukkan bahwa kita dapat menyelesaikan masalah H dengan menggunakan TSP. Jiika TSP dipecahkan dalam waktu polinomial, maka masalahi H juga dapat dilesaikan dalam waktu polinomial.

•Kenyataannya TSP tidak dapat diselesaikan dalam waktu polinomial, dan masalah H juga tidak dapat diselesaikan dalam waktu polinomial. Selain itu, TSP harus NP-Complete karena H adalah NP-Complete.

•Dalam membuktikan bahwa TSP adalah NP-Completel, kita akan memilih menyelesaikan masalah H menggunakan Hamiltonian Cycle, yang dikenal sebagai NP-Complete.  Jelas bahwa masalah Hamiltonian Cycle adalah kasus khusus dari TSP.

•Dengan memodifikasi masukan ke algoritma TSP dengan menetapkan biaya dari semua nilai yang ada menjadi beberapa terbatas tetap konstan. Kemudian, jika ditemukan adanya suatu Trail yang tertutup yang merupakan Hamiltonian Cycle, maka dengan demikian dapat dikatakan bahwa TSP merupakan NP-Complete karena telah terbukti bahwa masalah Hamiltonian Cycle adalah NP-Complete.

( Aziz Rahmad, Auzi Asfarian, Ari Setiawan, Chaerur Rozikien, M IqBal)

A quantitative approach for evaluating the quality of design pattern

Ulasan Paper

 

Identitas Paper

•Hsueh N, Chu P, Chu W. 2008. A quantitative approach for evaluating the quality of design pattern. The Journal of Systems and Software. 81:1430-1439.

Latar Belakang (Hsueh et al. 2008)

•Kualitas perangkat lunak adalah hal yang penting.

•Semakin banyak praktisi yang penggunakan design pattern  untuk membuat perangkat lunak berkualitas tinggi, terutama saat membuat desain software berorientasi objek.

•Diperlukan sebuah ukuran untuk menilai correctness (kebenaran) dari design pattern.

4 Komponen Design Pattern (Gamma et al. 1994)

•Pattern Name: penjelasan singkat mengenai masalah desain, solusi, dan konsekuensi.

•Intent : menjelaskan situasi yang tepat untuk menggunakan design pattern tersebut.

•Solution : deskripsi abstrak dari solusi, termasuk elemen-elemen seperti relasi dan kolaborasi pada design pattern tersebut.

•Consequences : mendeskripsikan keuntungan dan kerugian dari penggunaan design pattern tersebut.

Kebaikan Design Pattern (Hsueh et al. 2008)

•Bagian intent mengindikasi masalah yang ingin diselesaikan, sedangkan bagian solution menjelaskan model struktural untuk menyelesaikan masalah tersebut.

•Hsueh et al. (2008) beranggapan bahwa design pattern yang dirancang dengan baik memiliki model struktural (solution) yang benar-benar menyelesaikan masalah pada bagian intent.

•Contoh: apabila intent mendeskripsikan masalah kualitas (Contoh: reusability, maintenance, ekstensibility), model struktural harus memberikan solusi untuk meningkatkan aspek kualitas yang dimaksud.

•Bagaimana cara mengukurnya?

Quality Model of Object-Oriented Design

Tujuan dan Manfaat (Hsueh et al. 2008)

•Hsueh et al. (2008) mengajukan sebuah metode untuk melakukan validasi secara kuantitatif terhadap kebaikan sebuah design pattern.

•Metode didasarkan pada metode pengukuran kebaikan sistem berorientasi objek (contoh: QMOOD).

•Dengan metode tersebut, pertanyaan tersebut dapat dijawab:

•“Apakah design pattern  ini telah didesain dengan baik?”

•“Design pattern mana yang paling cocok dengan masalah yang saya temui?”

Evaluasi Design Pattern (Hsueh et al. 2008)

•Design pattern dapat didefinisikan sebagai <IF, IN, Q, SF, SN, T>

•IF (functional requirement intent) menjelaskan apa yang dilakukan oleh design pattern.

•IN (nonfunctional requirement intent) mendeskripsikan seberapa baik sebuah pattern dapat meningkatkan kualitas sistem.

•Q (quality focus) merepresentasikan fokus kualitas dari IF ke IN.

•SF (FR-structure) merepresentasikan struktur yang dapat mewujudkan IF.

•SN (NFR-structure) merepresentasikan struktur yang dapat mewujudukan IN.

•T (transformation) fungsi transformasi dari SF ke SN.

Travelling Salesman Problem: Aplikasi Dunia Nyata

1. Rute Transportasi
● Menemukan rute yang harus diambil untuk mengunjungi tiap lokasi dengan urutan tertentu, sehingga diperoleh jarak terpendek.
● Contoh:
– Salesman yang beroperasi door-to-door
– Band musik yang berkeliling (tour) dunia
– Pak pos yang mengantarkan banyak paket
● Dengan mengetahui rute optimal, akan banyak menghemat waktu dan biaya.

Representasi Dunia Nyata
● Node pada graf merepresentasikan lokasi geografis.
● Bobot edge merepresentasikan nilai metrik panjang jalan yang menghubungkan kedua lokasi tersebut.

2. Mesin Bor Otomatis
● Mesin bor otomatis pada rantai assembly yang bertugas untuk melubangi material.
● Kecepatan kerja tergantung pada jarak yang harus ditempuh oleh mata bor.
● TSP dapat digunakan untuk menemukan urutan pengeboran lubang yang optimal.
– node: posisi lubang yang akan dibor
– edge: jarak antar lubang
● Menghemat waktu dan meningkatkan produksi.

3. Penempatan Koneksi
Elektronik/Mekanik
● Pemasangan kabel listrik atau layout pipa di dalam gedung.
– node: lampu, saklar; kran
– edge: kabel; pipa
● Pada beberapa kasus, koneksi harus diatur agar tiap komponen tersambung membentuk
cycle.
● TSP digunakan untuk menghemat material dan memperlancar aliran.

4. Multiple Salesmen Model
● Terdapat m salesman, tiap kota harus dikunjungi sekali oleh salah satu salesman.
● Tiap salesman melakukan subtour, yang diawali dan diakhir dari kota yang sama.
● Objektif: salesman mana yang harus disewa dan subtour apa yang dipilih untuk meminimumkan total jarak dan biaya sewa.
● Model: dengan menambahkan (m – 1) node pada graf input (Lawler et al. 1985).

Tahap- tahap utama pada simulasi dengan NS-2

Terdapat tiga acuan langkah kunci dalam mendefinisikan skenario simulasi dalam NS-2, yaitu :

1. 1.      Tahap I : Merancang Simulasi

Tahap pertama dalam melakukan simulasi sebuah jaringan adalah untuk membuat perancangan simulasi.  Pada langkah ini, perancang harus menentukan tujuan dari simulasi, konfigurasi jaringan dan asumsi-asumsi terhadap konfigurasi tersebut, perhitungan kehandalan jaringan, dan perkiraan hasil dari simulasi.

1. 2.      Tahap II : Melakukan konfigurasi dan menjalankan simulasi

Pada tahap ini dilakukan implementasi dari rancangan pada tahap pertama.  Terdapat dua tahap yang harus dilakukan pada langkah ini, yaitu :

Tahap I : Konfigurasi Jaringan

Pada tahap ini, komponen jaringan diciptakan dan dikonfigurasi berdasarkan rancangan simulasi.  Selain itu dilakukan pula penjadwalan terhadap kejadian-kejadian yang direncanakan pada proses simulasi.  Parameter-parameter simulasi dikodekan dengan menggunakan bahasan pemrograman Tcl.

Tahap II : Simulasi

Pada tahap ini, proses simulasi pada perangkat lunak network simulator dilakukanberdasarkan konfigurasi yang telah dibuat pada tahap konfigurasi jaringan.  Dalam proses simulasi tersebut eksekusi terhadap kejadian-kejadian yang dijadwalkan dilakukan secara berurutan.  Tahap ini akan terus berjalan hingga batas waktu simulasi yang dispesifikasikan pada tahap konfigurasi jaringan tercapai.

1. 3.      Tahap III : Pemrosesan setelah simulasi

Fungsi pada tahap ini terdiri atas pembuktian integritas dari program dan melakukan evaluasi terhadap performansi dari jaringan yang disimulasikan.  Fungsi pertama di atas mengacu pada proses debugging, sedangkan fungsi kedua dapat mengacu pada pencapaian hasil akhir simulasi dengan mengumpulkan dan melakukan kompilasi terhadap keluaran hasil simulasi.  Visualisasi simulasi dapat diperoleh dengan melakukan pemrosesan terhadap trace file pada.

Arsitektur Dasar NS-2

NS-2 menyediakan sebuah perintah ns, yang merupakan sebuah perintah yang dapat dieksekusi (executable) oleh penggunanya.  Dalam menjalankan simulasi pada NS-2, perintah ns tersebut membutuhkan argumen masukan.  Argumen masukan yang dibutuhkan tersebut berupa nama dari skrip simulasi Tcl yang telah dipersiapkan untuk simulasi terlebih dahulu.  NS-2 akan menjalankan simulasi berdasarkan skenario yang terdapat pada file skrip simulasi Tcl tersebut.  Simulasi tersebut akan menghasilkan sebuah trace file yang berisikan data hasil simulasi.  File tersebut akan digunakan sebagai dasar dalam menampilkan grafik hasil simulasi dan/atau menampilkan animasi simulasi.  Gambar 11 menunjukkan arsitektur dari NS.

 

Gambar 16.  Arsitektur dasar dari NS

Karakteristik sistem client server

1. Servis (layanan)

• Hubungan antara proses yang berjalan pada mesin yang berbeda
• Pemisahan fungsi berdasarkan ide layanannya.
• Server sebagai provider, client sebagai konsumen

2. Sharing resources (sumber daya)

• Server bisa melayani beberapa client pada waktu yang sama, dan meregulasi akses bersama untuk share sumber daya dalam menjamin konsistensinya.

3. Asymmetrical protocol (protokol yang tidak simetris )

• Many-to-one  relationship antara client  dan server. Client  selalu menginisiasikan dialog melalui layanan permintaan, dan server menunggu secara pasif request dari client.

4. Transparansi lokasi

• Proses  yang dilakukan  server  boleh  terletak pada mesin yang  sama atau pada mesin yang  berbeda  melalui   jaringan. Lokasi  server  harus  mudah diakses  dari client.

5. Mix-and-Match

• Perbedaan server client platforms

6. Pesan berbasiskan komunikasi

• Interaksi   server   dan   client   melalui   pengiriman   pesan   yang   menyertakan permintaan dan jawaban.

7. Pemisahan interface dan implementasi

• Server  bisa diupgrade  tanpa mempengaruhi  client  selama  interface pesan yang diterbitkan tidak berubah.

 

Gambar 1. Client Server System

Konsep kerja HTTP

1. Saat kita membrowsing suatu alamat web memakai suatu web browser (client http), Sebuah client HTTP seperti web browser, biasanya memulai permintaan dengan membuat hubungan TCP/IP ke port tertentu di server Http ( port 80).
2. Sebuah server HTTP yang mendengarkan di port tersebut menunggu client mengirim kode permintaan (request), seperti “GET /HTTP/1.1″ (yang akan meminta halaman yang sudah ditentukan), diikuti dengan pesan MIME yang memiliki beberapa informasi kode head yang menjelaskan aspek dari permintaan tersebut, diikut dengan body dari data tertentu.

Begitu menerima kode permintaan (dan pesan, bila ada), server mengirim kembali kode jawaban, seperti “200 OK”, dan sebuah pesan yang diminta, atau sebuah pesan error atau pesan lainnya,seperti 404 (Not Found), 500 (Internal Server Error)

Web Server

Web server adalah komputer yang tergabung dalam jaringan atau internet yang memberikan informasi. Web client  adalah komputer yang tergabung dalam jaringan atau internet yang meminta informasi. Untuk dapat mengakses web server, web client menggunakan aplikasi yang disebut Web browser [9]. Web server merupakan software yang menjadi tulang belakang dari world wide web (www). Web server menunggu permintaan dari client yang menggunakan browser seperti Netscape Navigator, Internet Explorer, Modzilla, dan program browser lainnya. Jika ada permintaan dari browser, maka web server akan memproses permintaan itu kemudian memberikan hasil prosesnya berupa data yang diinginkan kembali ke browser. Data ini mempunyai format yang standar, disebut dengan format SGML (standar general markup language). Data yang berupa format ini kemudian akan ditampilkan oleh browser sesuai dengan kemampuan browser tersebut. Web server, untuk berkomunikasi dengan client-nya (web browser) mempunyai protokol sendiri, yaitu HTTP (hypertext transfer protocol).

Dengan protokol ini, komunikasi antar web server dengan client-nya dapat saling dimengerti dan lebih mudah. Para pengguna internet saat ini lebih banyak menggunakan format HTML (hypertext markup language) karena penggunaannya lebih sederhana dan mudah dipelajari. Kata HyperText mempunyai arti bahwa seorang pengguna internet dengan web browsernya dapat membuka dan membaca dokumen-dokumen yang ada dalam komputernya atau bahkan jauh tempatnya sekalipun.

Hal ini memberikan cita rasa dari suatu proses yang tridimensional, artinya pengguna internet dapat membaca dari satu dokumen ke dokumen yang lain hanya dengan mengklik beberapa bagian dari halaman-halaman dokumen (web) itu. Proses yang dimulai dari permintaan webclient (browser), diterima web server, diproses, dan dikembalikan hasil prosesnya oleh web server ke web client lagi dilakukan secara transparan. Setiap orang dapat dengan mudah mengetahui apa yang terjadi pada tiap-tiap proses. Secara garis besarnya web server hanya memproses semua masukan yang diperolehnya dari web clientnya

Contoh soal Backtracking

Diberikan X=(8,6,7,5,3,10,9) tentukan subset yang menghasilkan jumlah 15

Solusi :

• Urutkan X menjadi à X=(3,5,6,7,8,9,10)
• Lakukan Backtracking dengan kendala T = 15

1. (1,2,4)à 3+5+7=15
2. (2,7) à 5+10=15
3. (3,6) à 6+9=15
4. (4,5) à 7+8=15

Algoritme Greedy untuk Pewarnaan Graf

Masalah
Pewarnaan graf tidak berarah dengan maksimum M warna dengan syarat tidak ada simpul tetangga yang memiliki warna yang sama.

Tujuan
Setiap simpul yang bertetangga memiliki warna yang berbeda, dengan meminimumkan jumlah warna yang digunakan untuk mewarnai graf tersebut.

Elemen Algoritme Greedy

1. Himpunan kandidat: himpunan simpul yang akan diwarnai
2. Himpunan solusi: himpunan simpul yang bisa diberikan warna yang sama (simpul yang tidak bertetangga), jika tidak ada kandidat yang memenuhi maka dibuat himpunan solusi warna yang
baru. Simpul yang sudah diberikan warna dikeluarkan dari himpunan kandidat, masuk ke himpunan solusi. Proses berakhir jika himpunan kandidat kosong.
3. Fungsi seleksi: simpul diurutkan dari derajat (jumlah edge simpul) yang paling besar. Simpul dengan derajat terbesar diberikan warna dahulu.
4. Fungsi kelayakan: tidak ada simpul bertetangga yang berwarna sama.
5. Fungsi objektif: jumlah warna minimum yang digunakan.

Solusi Optimal
Solusi optimal algoritme greedy bergantung pada penomoran simpul yang mempunyai derajat sama.