Apakah ada metode umum untuk mengevaluasi optimalitas suatu algoritma optimasi?

Adakah metode umum untuk mengevaluasi optimalitas suatu algoritma optimasi, misalnya suatu algoritma yang memecahkan masalah NP-hard atau NP-complete?

Satu-satunya metode yang saya temukan sejauh ini adalah membandingkan hasil algoritma dengan solusi optimal yang sudah diketahui.

Jika tidak, adakah metode khusus untuk beberapa masalah khusus?

EDIT Untuk memperjelas: Secara optimal maksud saya seberapa dekat hasilnya dengan hasil solusi optimal.

Itu tergantung pada jenis masalahnya.

Jika ada skema pendekatan polinomial-waktu (PTAS) untuk masalah tersebut (misalnya Euclidian TSP), maka Anda bisa mendapatkan solusi yang mendekati sewenang-wenang dengan solusi optimal dalam waktu polinomial. Itu berarti, untuk setiap e > 0, ada algoritma waktu polinomial yang akan menemukan solusi perkiraan untuk masalah Anda, yang dijamin berada dalam (1+ e ) dari solusi optimal. Dalam hal ini, Anda hanya akan membandingkan kompleksitas runtime / memori untuk dua algoritma untuk nilai e yang sama . Jika satu algoritma dapat membuat "jaminan optimalitas" yang sama dari yang lain, tetapi dengan biaya waktu / memori yang lebih rendah, maka itu mungkin algoritma yang lebih baik.

Jika masalahnya adalah APX, tetapi bukan PTAS , yaitu jika ada algoritma perkiraan waktu polinomial yang dijamin untuk menghasilkan solusi yang berada dalam faktor konstan dari solusi optimal, maka Anda dapat membandingkan faktor konstan itu. Yang dengan faktor yang lebih rendah akan menghasilkan solusi yang lebih baik (tetapi seringkali dengan biaya waktu / memori yang lebih tinggi)

Jika masalahnya tidak ada di kedua kelas tersebut, maka saya pikir yang terbaik yang dapat Anda lakukan adalah membandingkan solusi mereka untuk satu set masalah acak, atau untuk masalah dengan solusi optimal yang diketahui.

Saya tidak berpikir ada cara umum untuk melakukannya, tetapi pasti ada metode untuk melakukannya.

Ambil, misalnya, masalah SET-COVER. Bagi yang tidak tahu masalahnya adalah sebagai berikut:

Diberikan satu set elemen B={1,2,...,m}dan sejumlah himpunan bagian S_1, S_2, ..., S_nyang penyatuannya B. Anda mencoba menemukan jumlah minimum dari himpunan bagian ini sehingga serikat masih B. Contoh khas dunia nyata dari masalah ini adalah di mana Anda diberikan kumpulan lingkungan dan Anda mencoba menemukan tempat yang optimal untuk menempatkan sekolah sedemikian rupa sehingga setiap lingkungan dilayani kurang dari jarak tertentu ddari sekolah terdekat. Dalam hal ini, Badalah himpunan lingkungan dan S_xterdiri dari semua set di dalam dkota x.

Anda membuktikan bahwa masalah ini adalah NP-COMPLETE. Namun ada solusi serakah sederhana di mana Anda berulang kali memilih set S_idengan jumlah elemen terbongkar terbesar. Dan Anda dapat membuktikan bahwa algoritma ini bekerja dengan baik .

Jika algoritma optimal terdiri dari khimpunan, algoritma serakah akan terdiri tidak lebih dari k ln(n)himpunan di mana ln adalah logaritma natural.

Masalah menentukan apakah suatu program memiliki 'kinerja optimalitas' A atau 'kinerja optimalitas' B untuk hampir semua definisi 'kinerja optimalitas' tidak dapat diputuskan secara umum (bukti di bawah). Ini menyiratkan bahwa tidak ada metode tunggal yang selalu dapat memberi tahu Anda seberapa optimal suatu algoritma.

Namun ada metode yang sering diterapkan ketika menganalisis algoritma perkiraan. Seringkali, algoritma aproksimasi dievaluasi dengan jaminan mereka pada seberapa jauh solusinya dari solusi optimal. Saya akan memberikan contoh masalah dan perkiraan, yang akan saya buktikan menggunakan metode 'batas bawah', yang merupakan metode yang sangat umum digunakan untuk membuktikan rasio.

Masalah yang dimaksud adalah masalah 'Memuat Truk': kami memiliki banyak truk identik (sebanyak yang kami suka), masing-masing mampu membawa beban seberat paling banyak T. Kami memiliki n benda yang ingin kami muat di truk ini untuk mengangkut. Setiap objek memiliki bobot w_i, di mana w_i <= T (jadi tidak ada item yang tidak bisa muat di truk bahkan sendiri). Item tidak dapat dibagi menjadi beberapa bagian. Kami ingin mengisi truk sehingga kami membutuhkan truk sesedikit mungkin. Masalah ini sudah selesai NP.

Ada algoritma perkiraan yang sangat mudah untuk masalah ini. Kami hanya mulai memuat truk dengan barang, sampai truk itu penuh sehingga barang berikutnya tidak muat. Kami kemudian mengambil truk lain dan memuat truk ini dengan barang ini yang tidak muat di truk sebelumnya. Kami tidak memuat barang lagi di truk ini: alih-alih, kami mengambil truk baru, kami mengisinya dengan banyak barang lagi sampai tidak muat lagi, letakkan barang terakhir itu di truknya sendiri dan seterusnya.

Algoritma ini adalah apa yang disebut 2-aproksimasi untuk masalah: ia menggunakan truk paling banyak dua kali lebih banyak dari solusi optimal yang dibutuhkan. 'Paling banyak' sangat penting: kita mungkin beruntung dan menemukan solusi optimal, tetapi setidaknya kita tidak akan berbuat terlalu buruk.

Untuk membuktikan ini, pertama-tama kita mendefinisikan batas bawah pada jumlah truk optimal yang kita butuhkan. Untuk ini, bayangkan bahwa kita diizinkan untuk memotong barang menjadi beberapa bagian: kita kemudian dapat dengan mudah mengisi setiap truk tetapi yang terakhir sepenuhnya. Jumlah truk yang kita perlukan jika kita lakukan itu adalah batas bawah untuk jumlah truk yang kita butuhkan untuk pertanyaan awal: dalam kasus 'terbaik' solusi optimal selalu mengisi setiap truk sepenuhnya, dalam hal ini jumlah truk sama, tetapi jika solusi optimal membuat truk tidak terisi, maka itu hanya membutuhkan lebih banyak truk.

Sekarang kita melihat algoritma aproksimasi kami. Perhatikan bahwa dalam setiap langkah, kami (sebagian) mengisi dua truk. Perhatikan juga bahwa dengan cara kerja algoritme, item di truk pertama dan item di truk kedua bersama-sama tidak muat di truk pertama, jadi jumlah mereka setidaknya T. Ini berarti bahwa setiap langkah, kami memuat setidaknya penuh truk senilai barang di dua truk. Sekarang bandingkan ini dengan batas bawah kami: dalam hal ini, kami memuat satu truk penuh barang dalam satu truk. Dengan kata lain, algoritme aproksimasi kami menghitung (dalam waktu linier) solusi yang sangat mirip dengan 'solusi' batas bawah kami, tetapi menggunakan dua truk alih-alih satu. Karenanya, kami menggunakan truk paling banyak dua kali lebih banyak daripada algoritma optimal, karena kami menggunakan truk paling banyak dua kali lebih banyak daripada batas bawah kami pada algoritma optimal.

Algoritma ini memberikan perkiraan faktor konstan: paling banyak 2 kali lebih buruk daripada solusi optimal. Beberapa contoh tindakan lain: paling banyak C lebih dari solusi optimal (kesalahan aditif, sangat jarang), paling banyak c log n kali seburuk solusi optimal, paling banyak cn kali seburuk solusi optimal, paling banyak c 2 ^ (dn) kali lebih buruk dari solusi optimal (sangat buruk; misalnya, TSP umum hanya menerima algoritma dengan jaminan semacam ini).

Tentu saja, jika Anda ingin memastikan bahwa faktor yang Anda buktikan adalah faktor terbaik yang dapat Anda buktikan, Anda harus mencoba untuk menemukan contoh di mana solusi yang diberikan algoritma Anda memang seburuk mungkin.

Juga perhatikan bahwa kami terkadang menggunakan algoritme aproksimasi pada masalah yang bukan NP-hard.

Saya belajar ini (di antara lebih banyak) dalam kursus algoritma perkiraan di universitas saya.

Bukti tidak dapat dipungkiri: misalkan P menjadi masalah dan A dan B menjadi algoritma perkiraan untuk P di mana A dan B tidak memiliki 'optimalitas' yang sama untuk beberapa definisi 'optimalitas' yang masuk akal, dan di mana waktu berjalan A dan B keduanya omega (1) (lebih lambat dari waktu konstan, yaitu, mereka menjadi lebih lambat untuk contoh yang lebih besar) dan di mana A dan B keduanya selalu berhenti.

Misalkan D adalah program yang mengklaim bahwa ia dapat menghitung yang berikut: mengingat beberapa program C menghitung perkiraan untuk P, putuskan apakah sebagus A atau sebaik B untuk input yang cukup besar (karena itu Anda dapat menggunakan ini untuk mengategorikan program sesuai dengan optimalitasnya).

Kita kemudian dapat menggunakan D untuk menyelesaikan masalah penghentian. Biarkan E menjadi program dan F menjadi input untuk program ini. Kami akan menggunakan D untuk memutuskan apakah E akan berhenti pada input F.

Kami merancang program G yang melakukan hal berikut: diberi input S untuk masalah P, ia menjalankan E pada F dan A pada S secara paralel: ia mengeksekusi E untuk sementara waktu, kemudian A, lalu E lagi dan seterusnya. Jika E berhenti pada F, ia berhenti menjalankan A dan sebaliknya menjalankan B pada S dan mengembalikan hasil B. Jika A berhenti sebelum E berhenti, ia mengembalikan hasil A.

Menggunakan D pada G sekarang memutuskan apakah E berhenti pada F: jika E berhenti pada F, maka untuk input S yang cukup besar, E berhenti pada F sebelum A berhenti pada S (karena waktu yang diperlukan E untuk berhenti tidak tergantung pada ukuran input, tidak seperti A). Karenanya D melaporkan bahwa G memiliki karakteristik optimalitas B. Jika E tidak berhenti pada F, D akan melaporkan bahwa G memiliki karakteristik optimalitas A.