Rumah Peranti teknologi AI Satu kejayaan baharu telah dibuat dalam masalah pemotongan minimum graf tidak terarah dan penyelidikan Google memenangi Anugerah Kertas Terbaik SODA 2024

Satu kejayaan baharu telah dibuat dalam masalah pemotongan minimum graf tidak terarah dan penyelidikan Google memenangi Anugerah Kertas Terbaik SODA 2024

Apr 17, 2024 pm 09:58 PM
Google projek

Blog Google mengeluarkan penyelidikan baharu untuk menyelesaikan masalah pemotongan minimum bagi graf tidak terarah.

Pada tahun 1996, saintis komputer Amerika David R Karger dan penyelidik lain mencadangkan algoritma rawak yang mengejutkan Algoritma Karger dalam kertas "Pendekatan baru untuk masalah potongan minimum", yang sangat popular dalam sains komputer teori sangat penting, terutamanya sesuai untuk anggaran masalah pemotongan minimum pada graf berskala besar.

Algoritma Karger boleh mencari titik potong minimum dalam graf dalam masa O (m log^3n), yang mereka panggil masa hampir linear, bermaksud pendaraban linear dengan faktor polilogaritma.

Dalam blog yang baru dikemas kini oleh Google, mereka memperkenalkan kertas kerja "Deterministic Near-Linear Time Minimum Cut in Weighted Graphs", dan penyelidikan itu memenangi Anugerah Kertas Terbaik ACM-SIAM SODA24. Artikel ini memperincikan algoritma baharu yang berjalan dalam masa hampir linear (bukannya mendekati masa linear). Algoritma ini bersifat deterministik dan boleh mencari potongan minimum yang betul Algoritma untuk graf mudah. Boleh dikatakan ini adalah penemuan terbesar sejak algoritma rawak terkenal Karger. .
Nota: terkecil Masalah pemotongan (selalunya dipanggil potongan minimum) ialah masalah struktur asas mengenai ketersambungan graf Ia secara amnya memfokuskan pada apakah cara paling mudah untuk memutuskan sambungan rangkaian? Dalam teori graf, set tepi yang boleh membuat graf aliran rangkaian tidak lagi bersambung (iaitu, dibahagikan kepada dua subgraf) dengan mengeluarkan semua tepi dipanggil potongan graf, dan potongan terkecil pada graf dipanggil a potongan minimum.
无向图最小割问题取得新突破,谷歌研究获SODA 2024最佳论文奖
  •                                                                                                                                                                                                                                                                                                                                 Graf dan dua potongannya: garis putus-putus merah menandakan potongan yang mengandungi tiga tepi dan garis putus-putus hijau mewakili potongan minimum (termasuk dua tepi) graf ini.

Pengenalan kaedah
无向图最小割问题取得新突破,谷歌研究获SODA 2024最佳论文奖
Berkenaan masalah pemotongan minimum, Karger mempelopori algoritma rawak masa hampir linear pada tahun 1996, yang boleh mencari pemotongan kebarangkalian kerja yang tinggi. cerapan utama bahawa terdapat graf yang lebih kecil yang sebahagian besarnya mengekalkan saiz semua potongan.
Penemuan ini berguna kerana algoritma yang lebih perlahan boleh dijalankan menggunakan graf yang lebih kecil sebagai input, dan masa berjalan yang lebih perlahan (dari segi saiz graf yang lebih kecil) masih setanding dengan yang asal ( Lebih Besar) Saiz graf graf hampir linear.

Sebenarnya, banyak penemuan struktur mengenai masalah pemotongan minimum dilakukan di sepanjang arah ini.

Google melakukan ini, bermula daripada graf G dengan n nod, dan kemudian berdasarkan kaedah sparsifikasi pengawetan potong yang dicadangkan dalam kertas "Skim Penghampiran Rawak untuk Pemotongan dan Aliran dalam Graf Berkapasiti" (dikarang oleh Benzur, Karger ), membuktikan bahawa graf berwajaran jarang G' dengan tepi yang lebih sedikit boleh dibina, dan pada graf ini, saiz hampir semua potongan adalah lebih kurang sama dengan saiz potongan sepadan dalam graf asal G.

Konsep ini boleh digambarkan melalui contoh berikut: graf asal terdiri daripada dua graf lengkap yang disambungkan oleh satu tepi, manakala graf terpencar mempunyai lebih sedikit tepi, tetapi berat tepinya lebih besar, dan pada masa yang sama masa semua pemotongan Saiznya dipelihara secara kasar.
Untuk membina graf yang lebih jarang ini, Benzur dan Karger menggunakan kaedah persampelan tepi secara bebas. Dalam kaedah ini, setiap tepi dalam graf G mempunyai kebarangkalian tertentu untuk dimasukkan ke dalam graf G', dan beratnya dalam G' akan dikuatkan mengikut songsangan kebarangkalian pensampelan (contohnya, jika berat asal tepi ialah 1 Tepi disertakan dengan kebarangkalian 10%, kemudian beratnya dilaraskan kepada 10). Ternyata kaedah yang sangat mudah (hampir masa linear) ini boleh membina pemisahan graf pemeliharaan potong dengan kebarangkalian kejayaan yang tinggi.

Walau bagaimanapun, algoritma Karger ialah algoritma Monte Carlo, iaitu output mungkin tidak betul dengan kebarangkalian kecil, dan tiada cara yang diketahui untuk mengetahui sama ada output itu betul selain membandingkannya dengan potongan minimum yang diketahui sebenar. .

Oleh itu, penyelidik telah berusaha keras untuk meneroka cara untuk menyelesaikan masalah terbuka algoritma penentuan masa hampir linear. Memandangkan pembinaan pemisahan graf pemuliharaan potong adalah satu-satunya komponen stokastik algoritma Karger, satu pendekatan adalah untuk mencari pembinaan penentuan pemisahan dalam masa hampir linear (juga dipanggil derandomisasi).

Pada tahun 2015, Kawarabayashi dan Thorup mencapai pencapaian penting - mencari algoritma masa hampir linear deterministik untuk graf mudah (iaitu, graf dengan paling banyak satu tepi antara setiap pasangan nod dan semua pemberat tepi bersamaan dengan 1) .

Kajian ini membawa kepada idea utama, iaitu, terdapat beberapa perkaitan antara potongan minimum dan satu lagi struktur graf penting (dipanggil "potongan konduktans rendah"). Sambungan ini adalah penting untuk mengubah dominasi algoritma Karger pada graf berwajaran tepi umum kemudiannya dan membantu Google memperoleh algoritma baharunya.

Penjajaran potongan minimum dan potongan konduktans rendah

Konduktans potongan graf S ditakrifkan sebagai nisbah saiz potongan S kepada isipadu S (dengan andaian S ialah sisi volum yang lebih kecil pada potongan dan tidak kosong), di mana isipadu S ialah darjah nod dalam S.

konduktans rendah potongan S secara intuitif menangkap kesesakan dalam rangkaian, kerana terdapat hanya sebilangan kecil tepi (berbanding dengan isipadunya) yang menyambungkan S ke seluruh graf. Konduktans graf ditakrifkan sebagai konduktans minimum untuk sebarang potongan dalam graf, dan graf dengan konduktans besar (juga dipanggil graf lanjutan) dikatakan bersambung dengan baik kerana tiada halangan di dalamnya. Garis putus-putus merah menunjukkan bahawa saiz CUT ialah 2, dan sisi yang lebih kecil (bawah) Isipadu ialah 24, jadi Konduktansnya ialah 1/12, yang juga merupakan Konduktansi graf.
无向图最小割问题取得新突破,谷歌研究获SODA 2024最佳论文奖
Kawayabarashi dan Thorup memerhatikan bahawa dalam graf mudah dengan darjah nod minimum yang besar, sebarang potongan minimum bukan remeh (iaitu sekurang-kurangnya dua nod pada kedua-dua belah) mesti mempunyai konduktans yang rendah. Berdasarkan pemerhatian ini, jika graf boleh dibahagikan kepada gugusan yang bersambung dengan baik, maka pembahagian mestilah konsisten dengan setiap potongan min bukan remeh, kerana setiap gugusan mesti terletak tepat pada satu sisi setiap potongan. Kemudian, setiap kelompok dikecilkan kepada nod dan graf yang lebih kecil diproses di mana semua potongan minimum bukan remeh bagi graf asal adalah utuh.

Walau bagaimanapun, untuk graf berwajaran, pemerhatian di atas tidak lagi berlaku, dan pembahagian yang sama yang digunakan dalam kes graf ringkas mungkin tidak betul-betul konsisten dengan pemotongan minimum bukan remeh.

Seperti yang ditunjukkan dalam rajah di bawah, Jason Li memerhatikan pada 2021 bahawa pembahagian ini masih kira-kira konsisten dengan pemotongan minimum yang tidak remeh. Khususnya, untuk potongan minimum S yang bukan remeh, terdapat potongan S' yang serupa dengan S supaya S' konsisten dengan kelompok. Jason Li selanjutnya memerhatikan bahawa sifat pembahagian ini boleh dieksploitasi untuk merosak secara berkesan pembinaan keterlanjuran graf pemeliharaan potong.

Algoritma baharu yang direka oleh Google bertujuan untuk membina partition untuk merumuskan kes penggunaan potongan min. Kajian Google adalah lebih tepat dan lebih pantas daripada kaedah yang lebih umum dan luar biasa yang digunakan Jason Li dalam kerja sebelumnya. Penyelidikan baharu ini mengoptimumkan masa berjalan sambil memastikan ketepatan, dan akhirnya mencapai algoritma penentu masa hampir linear untuk masalah pemotongan minimum.

无向图最小割问题取得新突破,谷歌研究获SODA 2024最佳论文奖

Pautan rujukan: https://research.google/blog/solving-the-minimum-cut-problem-for-undirected-graphs/

Atas ialah kandungan terperinci Satu kejayaan baharu telah dibuat dalam masalah pemotongan minimum graf tidak terarah dan penyelidikan Google memenangi Anugerah Kertas Terbaik SODA 2024. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!

Kenyataan Laman Web ini
Kandungan artikel ini disumbangkan secara sukarela oleh netizen, dan hak cipta adalah milik pengarang asal. Laman web ini tidak memikul tanggungjawab undang-undang yang sepadan. Jika anda menemui sebarang kandungan yang disyaki plagiarisme atau pelanggaran, sila hubungi admin@php.cn

Alat AI Hot

Undresser.AI Undress

Undresser.AI Undress

Apl berkuasa AI untuk mencipta foto bogel yang realistik

AI Clothes Remover

AI Clothes Remover

Alat AI dalam talian untuk mengeluarkan pakaian daripada foto.

Undress AI Tool

Undress AI Tool

Gambar buka pakaian secara percuma

Clothoff.io

Clothoff.io

Penyingkiran pakaian AI

AI Hentai Generator

AI Hentai Generator

Menjana ai hentai secara percuma.

Artikel Panas

R.E.P.O. Kristal tenaga dijelaskan dan apa yang mereka lakukan (kristal kuning)
2 minggu yang lalu By 尊渡假赌尊渡假赌尊渡假赌
Repo: Cara menghidupkan semula rakan sepasukan
1 bulan yang lalu By 尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island Adventure: Cara mendapatkan biji gergasi
4 minggu yang lalu By 尊渡假赌尊渡假赌尊渡假赌

Alat panas

Notepad++7.3.1

Notepad++7.3.1

Editor kod yang mudah digunakan dan percuma

SublimeText3 versi Cina

SublimeText3 versi Cina

Versi Cina, sangat mudah digunakan

Hantar Studio 13.0.1

Hantar Studio 13.0.1

Persekitaran pembangunan bersepadu PHP yang berkuasa

Dreamweaver CS6

Dreamweaver CS6

Alat pembangunan web visual

SublimeText3 versi Mac

SublimeText3 versi Mac

Perisian penyuntingan kod peringkat Tuhan (SublimeText3)

Cara Mengulas DeepSeek Cara Mengulas DeepSeek Feb 19, 2025 pm 05:42 PM

DeepSeek adalah alat pengambilan maklumat yang kuat. .

Cara Mencari DeepSeek Cara Mencari DeepSeek Feb 19, 2025 pm 05:39 PM

DeepSeek adalah enjin carian proprietari yang hanya mencari dalam pangkalan data atau sistem tertentu, lebih cepat dan lebih tepat. Apabila menggunakannya, pengguna dinasihatkan untuk membaca dokumen itu, cuba strategi carian yang berbeza, dapatkan bantuan dan maklum balas mengenai pengalaman pengguna untuk memanfaatkan kelebihan mereka.

Sesame Open Door Exchange Web Pautan Pautan Gerbang Perdagangan Laman Web Pendaftaran Terkini Sesame Open Door Exchange Web Pautan Pautan Gerbang Perdagangan Laman Web Pendaftaran Terkini Feb 28, 2025 am 11:06 AM

Artikel ini memperkenalkan proses pendaftaran versi web Web Open Exchange (GATE.IO) dan aplikasi Perdagangan Gate secara terperinci. Sama ada pendaftaran web atau pendaftaran aplikasi, anda perlu melawat laman web rasmi atau App Store untuk memuat turun aplikasi tulen, kemudian isi nama pengguna, kata laluan, e -mel, nombor telefon bimbit dan maklumat lain, dan lengkap e -mel atau pengesahan telefon bimbit.

Platform Perdagangan Pintu Terbuka Sesame Muat turun Versi Mudah Alih Platform Perdagangan Platform Perdagangan Alamat Muat Turun Platform Perdagangan Pintu Terbuka Sesame Muat turun Versi Mudah Alih Platform Perdagangan Platform Perdagangan Alamat Muat Turun Feb 28, 2025 am 10:51 AM

Adalah penting untuk memilih saluran rasmi untuk memuat turun aplikasi dan memastikan keselamatan akaun anda.

Mengapa pautan Bybit Exchange tidak dimuat turun dan dipasang secara langsung? Mengapa pautan Bybit Exchange tidak dimuat turun dan dipasang secara langsung? Feb 21, 2025 pm 10:57 PM

Mengapa pautan Bybit Exchange tidak dimuat turun dan dipasang secara langsung? Bybit adalah pertukaran cryptocurrency yang menyediakan perkhidmatan perdagangan kepada pengguna. Aplikasi mudah alih Exchange tidak boleh dimuat turun terus melalui AppStore atau GooglePlay untuk sebab -sebab berikut: 1. Aplikasi pertukaran cryptocurrency sering tidak memenuhi keperluan ini kerana ia melibatkan perkhidmatan kewangan dan memerlukan peraturan dan standard keselamatan tertentu. 2. Undang -undang dan Peraturan Pematuhan di banyak negara, aktiviti yang berkaitan dengan urus niaga cryptocurrency dikawal atau terhad. Untuk mematuhi peraturan ini, aplikasi bybit hanya boleh digunakan melalui laman web rasmi atau saluran yang diberi kuasa lain

Portal Pendaftaran Rasmi Exchange Gate.io Portal Pendaftaran Rasmi Exchange Gate.io Feb 20, 2025 pm 04:27 PM

Gate.io adalah pertukaran cryptocurrency terkemuka yang menawarkan pelbagai aset crypto dan pasangan perdagangan. Mendaftar Gate.io sangat mudah. Lengkapkan pendaftaran. Dengan Gate.io, pengguna dapat menikmati pengalaman perdagangan cryptocurrency yang selamat dan mudah.

Portal Log Masuk Versi Rasmi Binance Binance Portal Log Masuk Versi Rasmi Binance Binance Feb 21, 2025 pm 05:42 PM

Untuk mengakses versi Login Laman Web Binance yang terkini, ikuti langkah mudah ini. Pergi ke laman web rasmi dan klik butang "Login" di sudut kanan atas. Pilih kaedah log masuk anda yang sedia ada. Masukkan nombor mudah alih berdaftar atau e -mel dan kata laluan anda dan pengesahan lengkap (seperti kod pengesahan mudah alih atau Google Authenticator). Selepas pengesahan yang berjaya, anda boleh mengakses Portal Log masuk laman web rasmi Binance.

Alamat muat turun terbaru Bitget pada tahun 2025: Langkah -langkah untuk mendapatkan aplikasi rasmi Alamat muat turun terbaru Bitget pada tahun 2025: Langkah -langkah untuk mendapatkan aplikasi rasmi Feb 25, 2025 pm 02:54 PM

Panduan ini menyediakan langkah muat turun dan pemasangan terperinci untuk aplikasi Bitget Exchange rasmi, sesuai untuk sistem Android dan iOS. Panduan ini mengintegrasikan maklumat dari pelbagai sumber yang berwibawa, termasuk laman web rasmi, App Store, dan Google Play, dan menekankan pertimbangan semasa muat turun dan pengurusan akaun. Pengguna boleh memuat turun aplikasinya dari saluran rasmi, termasuk App Store, muat turun APK laman web rasmi dan melompat laman web rasmi, dan lengkap pendaftaran, pengesahan identiti dan tetapan keselamatan. Di samping itu, panduan itu merangkumi soalan dan pertimbangan yang sering ditanya, seperti

See all articles