Menarik

Algoritma, Optimasi, dan Masalah Penjual Bepergian

Algoritma, Optimasi, dan Masalah Penjual Bepergian

Ini adalah artikel kelima dalam seri tujuh bagian tentang Algoritma dan Komputasi, yang membahas bagaimana kita menggunakan bilangan biner sederhana untuk menggerakkan dunia kita. Artikel pertama, Bagaimana Algoritma Menjalankan Dunia Tempat Kita Tinggal, dapat ditemukan di sini.

Tugas penting seorang ilmuwan komputer teoretis adalah menemukan algoritme yang efisien untuk masalah dan yang paling sulit dari masalah ini bukan hanya masalah akademis; mereka berada di inti dari beberapa skenario dunia nyata yang paling menantang yang dimainkan setiap hari. Yang paling kritis dari ini adalah masalah pengoptimalan: bagaimana kami menemukan terbaik solusi untuk masalah ketika kita memiliki kemungkinan solusi yang tampaknya tak terbatas?

TERKAIT: ALGORITMA BARU MEMUNGKINKAN MOBIL OTONOM UNTUK MENGUBAH LANS LEBIH SEPERTI MANUSIA

Untuk saat ini, hal terbaik yang dapat kita lakukan adalah mengambil pendekatan heuristik dan menemukan filecukup baik solusi, tetapi kami menciptakan tingkat inefisiensi yang tak terhitung jumlahnya yang bertambah seiring waktu dan menguras sumber daya kami yang terbatas yang dapat digunakan dengan lebih baik di tempat lain. Kami menyebutnya Masalah Penjual Keliling dan tidak meremehkan untuk mengatakan bahwa solusi untuk masalah ini dapat menghemat ekonomi kita triliunan dolar.

Masalah Penjual Keliling, Kompleksitas Waktu Eksponensial, dan Selebihnya

Masalah Penjual Keliling digambarkan seperti ini: sebuah perusahaan mengharuskan salah satu tenaga penjual keliling mereka untuk mengunjungi setiap kota dalam daftar n kota, di mana jarak antara satu kota dan setiap kota lain dalam daftar diketahui. Setiap kota hanya dapat dikunjungi satu kali dan penjual selesai di kota tempat dia memulai. Apa jalan terpendek yang bisa dia ambil untuk mencapai ini?

Algoritme paling efisien yang kami tahu untuk masalah ini berjalan waktu eksponensial, yang sangat brutal seperti yang telah kita lihat. Tidak seperti enkripsi RSA, dalam kasus Travelling Salesman Problem tidak ada aritmatika modular atau mengubah faktorisasi menjadi pencarian periode, seperti yang dilakukan algoritma Shor. Masalah Penjual Perjalanan adalah masalah keputusan, dan tidak ada jalan pintas yang kami ketahui yang membuat kami bingung kompleksitas waktu eksponensial.

Hanya untuk menegaskan mengapa ini adalah situasi yang mengerikan, mari kita gunakan contoh yang sangat umum tentang betapa tidak warasnya kompleksitas waktu eksponensial bisa mendapatkan. Katakanlah Anda bisa melipat selembar kertas berkali-kali sebanyak yang Anda mau dan itu akan selalu sepanjang yang diperlukan untuk membuat lipatan. Dengan mengukur lebar tumpukan "lembaran" pada produk akhir di mana kertas yang dilipat semakin panjang dari kita, inilah yang dapat Anda harapkan:

* 0 lipatan: Tebal 1/250 inci.
* 10 kali lipat: ~ Tebal 2,05 inci.
* 25 kali lipat: ~ Tebal 1 mil.
* 43 kali lipat: Permukaan bulan.
* 52 kali lipat: Di dalam matahari.
* 57 kali lipat: Melewati Ultima Thule
* 67 lipatan: Membutuhkan waktu 1,5 tahun untuk melakukan perjalanan dari satu ujung ke ujung lainnya.
* 82 kali lipat: Selebar Galaksi Bima Sakti.
* 93 kali lipat: Dalam jarak lemparan astronomis dari lubang hitam supermasif di pusat Messier 87.
* 101 lipatan: Tidak yakin apa yang ada di sana karena berada di luar alam semesta yang dapat diamati.

Dan itu dengan terbaik algoritma yang kita punya sekarang. Masing-masing dari "lembaran" dalam tumpukan itu rute yang bisa diambil penjual yang panjangnya pada akhirnya kita perlu memeriksa dan mengukur terhadap semua panjang rute lainnya dan setiap lipatan sama dengan menambahkan satu kota ekstra ke daftar kota yang perlu dia kunjungi. Jika kami hanya melakukan kesalahan dalam mencoba menyelesaikan Masalah Penjual Perjalanan dengan memeriksa setiap solusi yang mungkin untuk menemukan yang terbaik, kami sedang melihat kompleksitas waktu faktorial. Menggunakan kami 128-bit nomor dari contoh enkripsi RSA kami, yaitu 2128, sedangkan 101 lipatan hanya 2101, 35! pukulan melewati 2128 dengan setidaknya faktor 100. Hal ini semakin memburuk dengan setiap penambahan tambahan dalam masukan Anda, dan inilah yang membuat Masalah Penjual Keliling begitu penting dan juga menjengkelkan.

Masalah Algoritma Optimasi

Kami tidak tahu bagaimana menemukan jawaban yang benar untuk Masalah Penjual Perjalanan karena untuk menemukan jawaban terbaik Anda memerlukan cara untuk mengesampingkan semua jawaban lain dan kami tidak tahu bagaimana melakukan ini tanpa memeriksa semua kemungkinan atau menyimpannya catatan rute terpendek yang ditemukan sejauh ini dan dimulai kembali setelah rute kami saat ini melebihi jumlah tersebut. Itulah yang terbaik yang kami miliki, dan itu hanya membuat segalanya berjalan lancar kompleksitas waktu eksponensial, jadi sebagai solusinya, ini sama sekali bukan solusi.

Masalah Travelling Salesman istimewa karena berbagai alasan, tetapi yang paling penting adalah karena ini adalah masalah pengoptimalan dan masalah pengoptimalan muncul di mana-mana dalam kehidupan sehari-hari. Sejauh ukuran input berjalan, 101 tidak terlalu besar sama sekali. Di dunia nyata, ada banyak kota kecil atau kota besar di satu negara bagian AS yang secara teoritis dapat menjadi bagian dari area pengiriman distributor komersial besar. Mencari tahu satu rute terpendek antara semua halte yang perlu dilakukan truk mereka ke berbagai pelanggan setiap hari akan menghemat biaya tenaga kerja dan bahan bakar yang tak terhitung banyaknya.

Jika Anda mencari suku cadang dari luar negeri untuk pabrik Anda, rute dan kombinasi metode pengiriman mana yang akan menghabiskan biaya paling sedikit? Konfigurasi lipatan protein manakah yang dapat mengalahkan kanker? Menemukan algoritme yang dapat memecahkan Masalah Penjual Perjalanan di tempat yang dekat waktu polinomial akan mengubah segalanya dan itu akan terjadi dalam semalam.

Bagian dari masalahnya adalah karena sifat dari masalah itu sendiri, kita bahkan tidak tahu apakah ada solusi yang masuk waktu polinomial secara matematis mungkin. Ini karena cara kita mengklasifikasikan masalah dan Masalah Penjual Keliling termasuk dalam klasifikasi yang sangat khusus dalam sistem itu, yang merupakan salah satu tantangan terbesar dalam matematika dan ilmu komputer, dengan implikasi yang menjangkau jauh ke dunia nyata.

Artikel keenam dalam seri kami tentang Algoritma dan Komputasi, P Vs. NP, NP-Complete, dan Algoritma untuk Semuanya, dapat ditemukan di sini.


Tonton videonya: Meningkatkan Pengunjung Website dengan SEO - Meet and Greet Sharing #Tourtravelrevolution (Oktober 2021).