Masalah asas komputer, masalah aliran maksimum telah membuat kemajuan terobosan: algoritma baharu adalah "sangat pantas"

Masalah ini sangat asas dalam teori aliran rangkaian. "Algoritma baharu ini sangat pantas. Malah, saya yakin bahawa tidak ada algoritma yang cekap untuk masalah ini," kata Daniel Spielman dari Universiti Yale.

Aliran maksimum telah dikaji sejak tahun 1950-an, apabila ia dikaji untuk memodelkan sistem kereta api Soviet. "Kajian mengenainya lebih tua daripada teori sains komputer," kata Edith Cohen dari Google Mountain View, Calif., pusat penyelidikan.

Soalan ini membawa kepada banyak aplikasi: penstriman data Internet, penjadualan syarikat penerbangan dan juga memadankan pencari kerja dengan peluang pekerjaan. Kertas kerja baharu ini membincangkan kedua-dua masalah aliran maksimum dan masalah yang lebih umum untuk mengendalikan aliran maksimum sambil juga ingin meminimumkan kos. Kedua-dua soalan ini telah memberi inspirasi kepada banyak kemajuan penting dalam teknologi algoritma selama bertahun-tahun. "Itulah sebabnya kami terus bekerja dalam bidang algoritma," kata Spielman "Algoritma baharu menyelesaikan kedua-dua masalah dalam masa "kira-kira linear", yang bermaksud bahawa masa berjalan algoritma adalah berkadar secara kasar dengan masa yang diperlukan untuk. merekod butiran rangkaian. Tiada algoritma lain untuk menyelesaikan masalah ini boleh mencapai kelajuan ini untuk semua rangkaian yang mungkin. Satish Rao dari University of California, Berkeley, berkata bahawa keputusan ini membuatkan dia melompat: "Ia sungguh menakjubkan."

Spielman percaya bahawa kami telah menemui algoritma yang begitu pantas, dan kini ia adalah Masa untuk mula berfikir tentang menyelesaikan pelbagai masalah aplikasi yang anda tidak fikirkan sebelum ini.

Pada masa ini, kaedah baharu ini kebanyakannya adalah penambahbaikan secara teori, kerana peningkatan dalam kelajuan algoritma hanya terpakai pada rangkaian yang lebih besar daripada yang ditemui di dunia nyata Masalah Trafik maksimum sudah boleh dijawab dengan cepat (sekurang-kurangnya tanpa mengambil kira pengurangan kos). Richard Peng dari Universiti Waterloo Kanada, salah satu daripada enam penciptanya, menjangkakan algoritma baharu itu boleh digunakan secara praktikal dalam masa setahun.

Sesetengah penyelidik percaya bahawa dalam beberapa tahun akan datang, saintis komputer mungkin mencari cara untuk menjadikannya lebih praktikal, dan mungkin lebih pantas.

Aleksander Mądry dari MIT berkata walaupun dengan penambahbaikan pada masa hadapan, kertas kerja baharu itu ialah "dunk paling menarik dalam pertandingan dunk." Dia berkata ia pada dasarnya yang terbaik."

Satu laluan pada satu masa

Richard Peng berkata bahawa begitu ramai saintis komputer sedang mengusahakan masalah aliran maksimum yang membincangkan kerja lepas di persidangan adalah seperti menonton perlawanan akhir kredit bahagian filem. Tetapi kebanyakan bersetuju bahawa algoritma rasmi pertama ialah aplikasi 1956 algoritma tamak untuk aliran maksimum oleh Lester Ford dan Delbert Fulkerson, yang menggunakan objek yang paling mudah didapati pada setiap langkah.

Anda boleh memikirkan pendekatan ini seperti ini: Mula-mula, bayangkan rangkaian lebuh raya di mana anda ingin mengalihkan sebanyak mungkin trak penghantaran dari Los Angeles ke New York City dalam tempoh tertentu masa. Algoritma Ford dan Fulkerson bermula dengan memilih laluan dari Los Angeles ke New York dan menghalakan sebanyak mungkin trak di sepanjang laluan itu. Kaedah ini biasanya tidak menggunakan kapasiti penuh semua jalan di jalan tersebut: jika jalan itu adalah lebuh raya lima lorong tetapi ia melalui jambatan dua lorong, anda hanya boleh meminta dua trak bergerak pada satu-satu masa.

Seterusnya, algoritma mengubah suai kapasiti segmen ini untuk mencerminkan bahagian kapasiti segmen itu kini digunakan: ia menolak bilangan trak yang dihantar daripada kapasiti segmen, jadi lima- lebuh raya lorong kini mempunyai kapasiti 3, manakala jambatan dua lorong mempunyai kapasiti sifar. Pada masa yang sama, algoritma menambah 2 pada kapasiti jalan ini dalam arah songsang, jadi kami boleh menarik balik sebahagian lalu lintas kemudian jika kami mahu.

Algoritma kemudiannya mencari laluan baharu dari Los Angeles ke New York yang boleh memuatkan beberapa trak, menghantar sebanyak mungkin trak di sepanjang laluan dan mengemas kini kapasiti semula. Selepas beberapa langkah ini terhad, jalan dari Los Angeles ke New York tidak lagi dapat menampung trak lagi, dan pada ketika ini algoritma selesai: kami hanya menggabungkan semua aliran yang dibina untuk mendapatkan aliran maksimum yang mungkin rangkaian.

Algoritma Ford dan Fulkerson tidak cuba membuat pilihan bijak sepanjang perjalanan. Jika ia memilih laluan yang memotong laluan berguna yang lain, itu adalah masalah untuk algoritma untuk ditangani kemudian. Dalam beberapa dekad sejak algoritma diterbitkan, penyelidik telah cuba mempercepatkan masa berjalan dengan meminta algoritma membuat pilihan yang lebih bijak, seperti sentiasa menggunakan laluan terpendek yang tersedia atau laluan dengan kapasiti tersedia yang paling besar. Pada tahun 1970, Yefim Dinitz menemui cara yang cekap untuk menggunakan semua laluan terpendek dalam rangkaian dalam satu langkah. Masa berjalan algoritma ini dalam rangkaian berkapasiti rendah telah dibuktikan oleh Shimon Even dan Robert Tarjan sebagai m^1.5 (m: bilangan pautan dalam rangkaian. Sebaliknya, algoritma Ford-Fulkerson memerlukan berbilang m dalam kapasiti rendah rangkaian. ^2).

Hampir 30 tahun kemudian, Rao dan Andrew Goldberg menghasilkan keputusan yang sama untuk rangkaian berkapasiti tinggi. Tetapi tiada siapa yang boleh mengalahkan indeks m^1.5. "Melangkah ke abad ke-21...halangan kepada m^1.5 sudah berakar umbi," kata Sushant Sachdeva dari Universiti Toronto, salah seorang pengarang kertas baharu Untuk membuat kemajuan selanjutnya, saintis komputer mesti mencari jalan untuk sepenuhnya Kaedah yang berbeza.

Dari Gabungan ke Kalkulus

Setakat ini semua algoritma ini telah mengambil pendekatan gabungan, iaitu mencari beberapa jenis struktur pada setiap langkah dan Gunakan struktur ini untuk mengemas kini aliran. Tetapi pada tahun 2003, Spielman dan ShangHua Teng dari University of Southern California membuka pintu kepada pendekatan yang sama sekali berbeza untuk "pengoptimuman," di mana teknik kalkulus digunakan sebagai panduan untuk mencari penyelesaian yang optimum.

Spielman dan Teng membangunkan algoritma pengoptimuman pantas yang menyelesaikan bukan masalah aliran maksimum tetapi masalah yang berkait rapat melalui setiap wayar dengan rintangan tertentu Rangkaian mencari arus dengan tenaga paling rendah . Sachdeva berkata kemajuan Spielman dan Teng adalah "saat genting."

Ahli pasukan yang mencipta algoritma ultra pantas untuk menentukan aliran maksimum dan kos minimum rangkaian (mengikut arah jam dari sudut kiri atas ): Yang Liu, Li Chen, Rasmus Kyng, Maximilian Probst Gutenberg, Richard Peng, Sushant Sachdeva.

Penyelidik tidak lama kemudian mula meneroka cara menggunakan kemajuan ini kepada masalah aliran maksimum. Fikirkan rangkaian jalan raya sebagai rangkaian wayar yang menambah rintangan pada jalan yang tidak mempunyai banyak kapasiti tersedia, menghalang elektron daripada bergerak merentasinya. Terima kasih kepada kerja Spielman dan Teng, kami boleh mengira arus dengan cepat melalui wayar ini, dan model ini mempunyai sifat kasar untuk aliran kenderaan maksimum melalui lebuh raya. (Mereka tidak akan sama, kerana isu semasa tidak meletakkan sebarang had keras pada kapasiti wayar.)

Kemudian, selepas menjana aliran awal ini, kita boleh lakukan sesuatu seperti gabungan Ford dan Fulkerson Algoritma menskala semula kapasiti dengan cara yang sama. Seterusnya, rintangan setiap wayar boleh ditetapkan semula untuk mencerminkan jumlah yang berubah ini dan menyelesaikan isu litar yang baru dibuat.

Tidak seperti pendekatan gabungan menukar satu blok rangkaian pada satu masa, kaedah pengoptimuman Spielman dan Teng melengkapkan imbasan keseluruhan rangkaian setiap kali. Ini menjadikan setiap langkah lebih cekap, jadi lebih sedikit jumlah langkah diperlukan untuk mencapai tahap maksimum. Pada tahun 2008, Samuel Daitch dan Spielman dari Google menggunakan kaedah ini, yang pada asasnya sepadan dengan had trafik maksimum sebelumnya iaitu m^1.5. Pada tahun 2013, Mądry memajukan pendekatan lebih jauh untuk melebihi m^1.5 untuk rangkaian berkapasiti rendah, meningkatkan masa jalan kepada kira-kira gandaan m^1.43. "Ia mengejutkan," kata Rao.

Dalam beberapa tahun akan datang, penyelidik mengembangkan lagi kaedah, tetapi keputusan mereka kekal pada m^1.33. Mereka mula tertanya-tanya sama ada indeks ini adalah had asas.

Untuk algoritma aliran maksimum, masa berjalan terpantas yang boleh dibayangkan hendaklah m kali (iaitu m^1.0), memandangkan menulis rangkaian memerlukan gandaan m langkah. Ini dipanggil masa linear. Tetapi bagi ramai penyelidik, algoritma yang sangat pantas itu kelihatan tidak dapat difikirkan. "Tiada sebab yang kukuh untuk mempercayai kami boleh melakukan ini," kata Spielman.

Kecilkan, guna semula, kitar semula

Pengarang kertas baharu ini percaya bahawa pendekatan Daitch dan Spielman mempunyai lebih banyak kelebihan. Mądry telah menggunakannya untuk mengurangkan bilangan langkah yang diperlukan untuk menyelesaikan masalah aliran maksimum, tetapi pengurangan ini dikenakan kos: pada setiap langkah, keseluruhan rangkaian perlu ditulis semula, dan masalah aliran kuasa perlu diselesaikan dari awal.

Pendekatan ini menganggap algoritma Spielman dan Teng sebagai kotak hitam – tanpa mengira apa yang berlaku di dalam algoritma. Enam penyelidik memutuskan untuk menyelidiki inti algoritma dan menyesuaikan komponennya kepada masalah aliran maksimum. Mereka mengesyaki bahawa komponen ini mungkin membolehkan mereka menyelesaikan "masalah kos minimum" yang lebih sukar, di mana ia adalah untuk mencari cara paling murah untuk mengangkut sejumlah bahan tertentu Para saintis komputer telah lama mengetahui bahawa mana-mana algoritma kos minimum boleh menyelesaikannya masalah aliran maksimum.

Seperti kaedah pengoptimuman yang lain, penyelidik mencadangkan konsep "tenaga" aliran sebagai fungsi kos dan kapasiti pautan. Mengalihkan trafik daripada pautan berkapasiti rendah yang mahal kepada pautan berkapasiti tinggi yang murah mengurangkan jumlah tenaga sistem.

Untuk mengetahui cara mengalihkan aliran dengan cepat ke arah keadaan tenaga yang lebih rendah, para penyelidik menggabungkan pendekatan pengoptimuman ini dengan pandangan gabungan lama. Yang terakhir menukar hanya satu bahagian rangkaian pada satu masa, memberikan kemungkinan untuk menggunakan semula beberapa kerja dari langkah sebelumnya.

Pada setiap langkah, algoritma mencari kitaran yang boleh mengurangkan tenaga, iaitu laluan yang bermula dan berakhir pada titik yang sama. Idea asasnya mudah: Katakan anda membuat jalan tol dari Chicago ke New York, dan kemudian anda mendapati bahawa terdapat lebuh raya yang lebih murah. Pada ketika ini, menambah New York pada gelung, berjalan di sepanjang jalan mahal ke Chicago, dan kemudian kembali di sepanjang laluan yang lebih murah, mencipta gelung yang menggantikan laluan mahal, sekali gus mengurangkan kos keseluruhan trafik.

Valerie King dari University of Victoria di Kanada mengatakan kaedah ini menggunakan lebih banyak langkah daripada "kaedah elektrik", jadi pada pandangan pertama ia berbunyi "seperti langkah ke belakang." Untuk mengimbangi, algoritma mesti mencari gelung yang baik pada setiap langkah dengan sangat pantas, lebih pantas daripada yang diperlukan untuk memeriksa keseluruhan rangkaian.

Beginilah cara algoritma Spielman dan Teng berfungsi. Algoritma mereka menyediakan cara baharu untuk menggunakan "pokok rentang regangan rendah", yang merupakan kunci kepada algoritma dan boleh menangkap banyak ciri yang paling menonjol bagi rangkaian. Memandangkan pokok sedemikian, ia sentiasa mungkin untuk membina sekurang-kurangnya satu kitaran yang baik dengan menambah pautan di luar pokok. Oleh itu, mempunyai pokok rentang berskala rendah boleh mengurangkan bilangan kitaran yang perlu dipertimbangkan.

Walaupun begitu, untuk menjadikan algoritma berjalan dengan cepat, pasukan tidak dapat membina pepohon rentang baharu pada setiap langkah. Sebaliknya, mereka mesti memastikan bahawa setiap kitaran baharu hanya mencipta kesan riak kecil dalam pokok rentang supaya kebanyakan pengiraan sebelumnya digunakan semula. Mencapai tahap kawalan ini adalah "kesukaran teras," kata Yang Liu, seorang pelajar siswazah di Universiti Stanford dan salah seorang pengarang kertas itu.

Akhirnya, penyelidik mencipta algoritma yang berjalan dalam masa "hampir linear", bermakna ia berjalan lebih dekat kepada m apabila menggunakan rangkaian yang lebih besar.

Algoritma meminjam banyak idea daripada Spielman dan Teng dan menggabungkannya menjadi sesuatu yang baharu sepenuhnya. Jika anda hanya pernah melihat kereta kuda, Spielman berkata, algoritma hari ini adalah seperti kereta. "Saya nampak ia mempunyai tempat duduk, saya nampak ia mempunyai roda, saya nampak ia mempunyai sesuatu untuk menggerakkannya. Tetapi mereka telah menggantikan kuda dengan enjin."

Rao membuat spekulasi bahawa analisis pasukan adalah panjang dan kompleks, tetapi penyelidik lain akan segera menggali untuk memudahkan masalah itu. "Perasaan saya ialah dalam beberapa tahun akan datang, segala-galanya akan menjadi lebih bersih dan lebih baik," katanya Setelah algoritma dipermudahkan, Spielman berkata, saintis komputer mungkin mula Ia digunakan sebagai subrutin algoritma yang menyelesaikan masalah yang berbeza. "Sekarang kami tahu kami boleh melakukan ini dengan cepat, orang ramai akan menemui semua jenis aplikasi yang mereka tidak fikirkan sebelum ini."

Selain itu, algoritmanya ialah Pecutan yang memeningkan masalah aliran maksimum membuatkan Spielman menantikan isu teras lain dalam teori algoritma, "Apa lagi yang boleh kami lakukan?"

Atas ialah kandungan terperinci Masalah asas komputer, masalah aliran maksimum telah membuat kemajuan terobosan: algoritma baharu adalah "sangat pantas". Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!