Dua ilmuwan komputer menemukan sebuah ide di tempat yang sangat tidak terduga yang hanya berguna bagi mereka untuk terobosan dalam teori grafik
Pada Oktober 2019, Jacob Holm dan Eva Rothenberg membolak- balik karya yang telah mereka terbitkan beberapa bulan sebelumnya - dan tiba-tiba menyadari bahwa mereka telah menemukan sesuatu yang serius.
Selama beberapa dekade, ilmuwan komputer telah mencoba untuk merancang algoritma cepat untuk menentukan apakah tepi dapat ditambahkan ke grafik tertentu sehingga tetap “planar” —yaitu, sehingga tepinya tidak berpotongan. Namun, tidak ada yang berhasil meningkatkan algoritme yang diterbitkan lebih dari 20 tahun yang lalu.
Holm dan Rothenberg terkejut menemukannya dalam pekerjaan merekaada ide yang memungkinkan untuk meningkatkan algoritma ini dengan cukup kuat. Dia "memilah salah satu kendala utama untuk algoritme nyata," kata Holm, seorang ilmuwan komputer di Universitas Kopenhagen. "Mungkin kami telah mengungkapkan sepenuhnya masalah ini."
Pasangan itu bergegas mengerjakan artikel baru . Mereka mempresentasikannya pada bulan Juni di Association for Computing Machinery Symposium on Computational Theory , di mana mereka merinci metode untuk memeriksa grafik untuk planaritas, secara eksponensial lebih unggul dari versi sebelumnya.
“Algoritme baru benar-benar hebat,” kata Giuseppe Italiano , ilmuwan komputer di Universitas Louis, salah satu penulis makalah tahun 1996 yang sekarang menjelaskan algoritme tercepat kedua. "Ketika saya terlibat dalam penulisan karya itu, saya tidak berpikir bahwa ini bisa terjadi."
Grafik adalah kumpulan simpul yang dihubungkan oleh tepi. Mereka dapat digunakan untuk melabeli segala hal mulai dari media sosial hingga jaringan jalan raya dan konduktor listrik di papan. Jika dalam kasus terakhir grafiknya tidak planar, maka kedua konduktor akan saling bersilangan, yang akan menyebabkan korsleting.
Kembali pada tahun 1913, grafik planar muncul dalam teka-teki "komunal" yang kompleks tentang tiga rumah , diterbitkan di The Strand Magazine. Publikasi tersebut meminta pembaca untuk meletakkan komunikasi untuk tiga rumah, menghubungkan masing-masing dengan tiga pembawa energi - air, gas, dan listrik - sehingga komunikasi tidak saling bersinggungan. Tidak butuh waktu lama untuk menyadari bahwa tugas ini tidak dapat diatasi.
Namun, dalam kasus dengan grafik yang lebih kompleks, tidak selalu jelas apakah grafik tersebut planar. Bahkan lebih sulit untuk mengetahui apakah grafik yang kompleks akan tetap planar saat Anda mulai menambahkan tepinya - seperti yang terjadi saat merencanakan jalan baru.
Ilmuwan komputer telah lama mencari algoritma yang dapat dengan cepat menentukan apakah perubahan yang diinginkan dapat dilakukan sehingga grafik tetap planar, tanpa melalui setiap bagian grafik ketika hanya sebagian kecil saja yang diubah. Algoritme tahun 1996 memerlukan sejumlah langkah untuk ini, secara kasar sebanding dengan akar kuadrat dari jumlah simpul pada grafik.
“Ini jauh lebih baik daripada memeriksa semuanya dari awal setiap saat, tapi tidak sempurna,” kata Holm.
Algoritme baru memeriksa planaritas dalam sejumlah langkah yang sebanding dengan pangkat tiga dari logaritma dari jumlah simpul dalam grafik - peningkatannya eksponensial. Holm dan Rothenberg dari Universitas Teknik Denmark mencapai percepatan ini dengan memanfaatkan properti khusus grafik planar yang mereka temukan tahun lalu.
Untuk memahami metodenya, Anda harus terlebih dahulu mencatat bahwa grafik planar yang sama dapat digambar dengan cara yang berbeda . Semua koneksi dari opsi ini tetap sama, namun, tepinya dapat ditempatkan relatif satu sama lain dengan cara yang berbeda.
Misalnya, gambar A dapat diubah menjadi gambar B dengan membalik segitiga yang membentuk simpul 1,2 dan 3 relatif terhadap tepi yang menghubungkan simpul 2 dan 3. Bagian atas dari gambar B juga dapat dibalik relatif terhadap simpul 4 dan 5, mendapatkan gambar C. berbeda, tetapi menunjukkan grafik yang sama.
Sekarang bayangkan Anda ingin menyisipkan tepi baru yang menghubungkan dua simpul dari grafik planar - katakanlah, simpul 1 dan 6. Untuk melakukan ini, Anda menjalankan urutan membalik. Dari posisi awal di sebelah kiri, dalam dua putaran, Anda dapat mentransfer simpul 1 ke tempat di mana ia dapat dihubungkan ke simpul 6 tanpa melewati sisi lainnya.
Dalam makalah tahun 2019, Holm dan Rothenberg menemukan bahwa beberapa gambar memiliki lebih banyak keuntungan untuk penyisipan tepi daripada yang lain. Pola "baik" ini hanya perlu beberapa kali membalik untuk menambahkan keunggulan baru tanpa merusak planaritas.
Apa yang terlambat mereka sadari pada bulan Oktober adalah bahwa pembalikan yang membawa Anda lebih dekat ke posisi di mana Anda dapat menambahkan tepi baru juga membawa grafik lebih dekat ke salah satu pola bagus yang telah mereka tentukan. Dengan menunjukkan bahwa urutan pembalikan tak terelakkan membawa grafik lebih dekat ke pola yang disukai, algoritme baru dapat dibuat untuk membatasi jumlah pembalikan yang mungkin Anda perlukan untuk menemukan cara menambahkan tepi (jika memungkinkan).
“Kami segera menyadari bahwa dengan analisis baru ini, masalah dapat diselesaikan
sebuah algoritma yang konsepnya sangat sederhana, ”kata Holm.
Jacob Holm dan Eva Rothenberg
Algoritme baru melakukan satu putaran pada satu waktu untuk mencari solusi. Akibatnya, salah satu dari dua hal terjadi: algoritme menemukan cara untuk memasukkan edge yang diperlukan, atau flip berikutnya membatalkan edge sebelumnya - setelah itu algoritme menyimpulkan bahwa tidak ada cara untuk menambahkan edge baru.
“Kami menyebut algoritme ini malas-serakah,” Rotenberg menjelaskan. "Itu hanya membuat perubahan yang diperlukan untuk mengakomodasi tulang rusuk baru."
Metode baru mereka mendekati - tetapi tidak cocok - kinerja algoritme terbaik untuk tugas-tugas semacam itu. Algoritme baru juga harus melalui terlalu banyak langkah untuk digunakan di sebagian besar aplikasi dunia nyata - biasanya grafik cukup sederhana untuk diuji secara brute force.
Namun bagi Holm dan Rothenberg, kecepatan algoritme tidak sepenting ide yang mempercepatnya. “Ada konsekuensi langsung dari pemahaman ini,” kata Rotenberg.
Italiano yakin akhirnya akan menemukan kegunaan yang sebenarnya. “Cepat atau lambat pasti akan mempengaruhi apa yang diluar ilmu komputer dengan matematika,” ujarnya.
Tidak ada yang tahu kapan algoritma yang lebih cepat dapat muncul. Ini mungkin membutuhkan terobosan baru, atau bahan rahasia mungkin sudah ada di suatu tempat, menunggu di sayap dalam tumpukan penelitian lama.