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).