Saya mencari daftar masalah optimasi NP-hard, di mana ada penelitian aktif dalam heuristik praktis untuk menyelesaikannya dan ada tolok ukur umum, yang coba dikalahkan orang.
Contohnya termasuk: Rekonstruksi pohon filogenetik (heuristik misalnya di sini ) Penjual keliling (tidak begitu aktif, tetapi LKH cukup terkenal)
Lebih khusus lagi, saya mencari bidang penelitian, di mana orang benar-benar peduli tentang biaya yang dihasilkan (seperti TSP atau filogeni yang disebutkan di atas). Misalnya menemukan pohon keputusan bukanlah hal yang saya cari, karena sangat sedikit orang yang peduli dengan hasil tinggi pohon.
heuristics
usamec
sumber
sumber
Jawaban:
MaxSAT - orang benar-benar peduli tentang hal ini karena pemecah SAT sangat berkembang sehingga seringkali rute terbaik untuk masalah optimasi NP favorit Anda dalam praktiknya adalah menguranginya menjadi MaxSAT dan kemudian menerapkan salah satu pemecah yang terkenal. Lihat kompetisi SAT untuk benchmark, dll.
Pencari-klik terbiasa dalam biologi komputasi dan kombinatorik, dan algoritma heuristik sangat bagus, seingat saya.
Bagian yang luas dari Riset Operasi dikhususkan untuk algoritma, termasuk yang heuristik, untuk menyelesaikan kasus integer atau mixed-integer linear programming.
sumber
Riset operasi memiliki banyak masalah optimisasi kombinatorial di mana pengembangan heuristik untuk meminimalkan (atau memaksimalkan) biaya yang dihasilkan adalah area yang sangat aktif.
Misalnya, masalah perutean kendaraan, masalah perutean busur dengan kapasitansi, masalah spanning tree minimum dan variasi masalah ini.
sumber