Seberapa umumkah algoritma waktu eksponensial kasus-generik dalam perangkat lunak produksi?

Saya tahu bahwa algoritma waktu eksponensial umumnya harus dihindari tetapi kadang-kadang diperlukan. Sebuah kasus menjadi Travelling Salesman. Seberapa umumkah algoritma tersebut dalam perangkat lunak produksi? Apakah kasus-kasus ini biasanya diperlukan atau hasil dari pekerjaan terburu-buru? Saya mengerti bahwa banyak yang bisa diselesaikan dengan heuristik yang baik. Apa yang biasanya dilakukan dengan mereka yang tidak bisa?

Sesuatu yang tidak ada dalam perangkat lunak produksi tetapi dilakukan pada perangkat lunak produksi adalah verifikasi formal . Ini mungkin tidak diadopsi untuk sebagian besar perangkat lunak pelanggan tetapi mendapatkan jalur untuk sistem dan driver tertanam, yaitu untuk perangkat keras dan perangkat lunak yang kebenarannya penting (dan dapat ditelusuri).

Masalah-masalah verifikasi yang benar-benar dapat dihitung (penghalang # 1) sering EXPTIM-keras , dalam kasus yang lebih beruntung Anda mendapatkan PSPACE -lengkapan lengkap (penghalang # 2). Kedua kelas (diduga) lebih sulit daripada masalah NP-lengkap, yang mudah dibandingkan. Masalah ganda-eksponensial juga mudah diperoleh.

Dalam kasus ini, heuristik (dalam arti hasil akhir) tidak memotongnya karena Anda memerlukan hasil yang pasti; karena itu Anda membutuhkan mesin dan waktu yang besar. Ada heuristik (dalam arti pemilihan alternatif) yang sering menyebabkan runtime yang lebih pendek (yaitu eksplorasi ruang pencarian yang pintar ketika keadaan kesalahan dicari) tetapi dalam kasus terburuk, menunggu adalah yang dapat Anda lakukan. Atau Anda dapat melakukan bukti pena dan kertas dan memeriksanya dengan mesin , yang secara komputasi lebih sederhana.

Algoritma yang umum digunakan dengan kompleksitas kasus terburuk eksponensial adalah metode simpleks yang digunakan dalam pemrograman linier . Namun, kompleksitas kasus generik dari metode tersebut merupakan masalah terbuka. Dengan beberapa asumsi spesifik, jumlahnya banyak.

Memprogram penerjemah bahasa lebih buruk daripada waktu eksponensial (dalam panjang input mereka, yaitu dalam panjang program mereka menafsirkan), dan mereka cukup umum. Contoh lain adalah pembuktian teorema otomatis / penyelesaian kendala / penyelesaian sat / integer pemrograman linier. Dan contoh lain adalah diferensiasi simbolik seperti yang diterapkan dalam misalnya Maple / Mathematica (walaupun dimungkinkan untuk melakukan diferensiasi simbolik dalam waktu linier jika Anda diizinkan untuk berbagi subekspresi antar node).

Biarkan saya mengambil contoh masalah penjual keliling. Saya telah mengerjakannya beberapa kali.

Ada beberapa kali ketika saya berada di sebuah tim yang menulis solusi untuk masalah salesman keliling tetapi dengan beberapa parameter lagi. Misalnya, itu bisa menjadi toko dengan armada teknisi dan insinyur masing-masing dengan keahlian yang unik. Tujuan datang setiap hari dalam bentuk permintaan layanan. Semua program dalam produksi meskipun mereka telah mengalami modifikasi dan pemeliharaan sejak menulisnya.

Beginilah cara mereka bekerja. Setiap insinyur akan menerima daftar hal-hal yang perlu diperbaiki pada perangkat genggam setiap hari. Ketika mereka menyelesaikan setiap tugas layanan, mereka harus menutup kasing. Kasus-kasus yang ditinggalkan bergabung dengan kasus-kasus yang dijadwalkan untuk hari berikutnya dengan prioritas sedikit lebih tinggi karena pada saat itu pelanggan akan menyatakan beberapa ketidakpuasan. Ada banyak alasan mengapa seorang insinyur tidak mau menghadiri suatu kasus. Masalah lalu lintas adalah yang paling umum.

Seberapa umum mereka? Paling tidak sebanyak jumlah permintaan layanan purna jual yang datang dari pelanggan. Tanpa layanan purna jual, misalnya, mempertahankan pelanggan akan sulit dan mendapatkan pelanggan baru akan menjadi lebih sulit.

Dengan banyak toko berbasis web seperti Amazon dan toko-toko buku lainnya dan toko-toko lain yang berjalan baik dalam bisnis, saya akan berpikir bahwa penjual keliling lebih umum daripada dulu. Juga, mungkin ada banyak variasi dari masalah salesman keliling yang diajarkan dalam buku teks.