Kunci Algoritma Kubus Rubik Adalah N Kuadrat Per Log N

Tinuku
News KeSimpulan.com - Matematika Kubus Rubik. Tidak penting berapa lama waktu Anda menyelesaikan Kubus Rubik tetapi N kotak per baris sebanding dengan N2/log N.

Agustus lalu genap 30 tahun setelah Kubus Rubik pertama kali populer, sekarang penelitian baru menetapkan hubungan antara jumlah kotak dan jumlah maksimum gerak langkah yang diperlukan untuk menyelesaikannya. Tim peneliti internasional membuktikan tidak peduli seberapa lama dilalui untuk menyelesaikan, tetapi langkah tidak lebih dari 20 gerak.

Meskipun peneliti menggunakan beberapa trik cerdas untuk menghindari evaluasi semua 43 triliun posisi yang dilalui kubus, bukti setara dengan 35 tahun nilai angka-angka pada komputer modern.

Sayangnya, untuk kubus lebih besar dari Kubus Rubik standar (katakanlah, 4 atau 5 baris kotak, bukan tiga) mungkin di luar kapasitas komputasi dari semua komputer di dunia.

Namun sebuah laporan ke arXiv yang akan dipresentasikan di 19th Annual European Symposium on Algorithms pada September, para peneliti Massachusetts Institute of Technology (MIT), University of Waterloo dan Tufts University membangun hubungan matematis antara jumlah kotak dalam kubus dan jumlah maksimum langkah yang diperlukan untuk memecahkannya.

Ilmu komputer terkait terutama dengan pertanyaan bagaimana lama waktu algoritma yang dibutuhkan untuk mengeksekusi, namun ilmuwan komputer mengukur jawaban dalam jumlah aturan elemen algoritma.

Waktu eksekusi algoritma yang menemukan jumlah terbesar dalam daftar, misalnya, sebanding dengan panjang daftar. Algoritma "bodoh" untuk memilah nomor dalam daftar dari terkecil sampai terbesar, bagaimanapun memiliki waktu eksekusi proporsional dengan kuadrat panjang daftar.

Erik Demaine, insinyur komputer dari MIT, dan rekannya menunjukkan jumlah maksimum langkah yang diperlukan untuk memecahkan Kubus Rubik dengan N kotak per baris sebanding dengan N2/log N.

"Itu jawabannya dan bukan N2. Hal yang mengejutkan," kata Demaine.

Cara standar memecahkan Kubus Rubik adalah menemukan persegi yang keluar dari posisi dan memindahkannya ke tempat yang tepat sementara meninggalkan sisa kubus sesedikit mungkin berubah. Pendekatan ini memang menghasilkan solusi terburuk proporsional N2.

Demaine mengakui dalam kondisi tertentu, urutan tunggal sudut bisa bergerak beberapa kotak ke tempat yang tepat, mengurangi jumlah total bergerak. Tetapi menemukan diskripsi matematis dan menentukan seberapa sering muncul bukanlah tugas yang mudah.

"Dalam satu jam pertama, kita melihat setidaknya N2/log N. Tapi kemudian berbulan-bulan sebelum kita bisa membuktikan bahwa N2/log N tersebut bergerak cukup," kata Demaine.

Karena metode analisis kasus di mana beberapa kotak dapat dipindahkan ke tempatnya bersamaan, metode menyediakan cara untuk mengenali kasus-kasus dan dengan demikian algoritma untuk memecahkan sebuah kubus secara teratur. Algoritma ini tidak cukup optimal karena selalu membutuhkan beberapa gerakan tambahan. Tetapi karena jumlah per kotak meningkat, gerakan makin berkurang secara signifikannya.

Kubus Rubik adalah contoh dari masalah konfigurasi, contoh paling terkenal yang melibatkan manajemen pergudangan yang paling efisien untuk menata kembali kotak yang ditumpuk di gudang.

"Hidup saya didorong oleh pemecahan masalah yang saya anggap menyenangkan. Ini selalu sulit untuk mengatakan pada saat penting. Belajar bilangan prima hanyalah kegiatan rekreasi. Tidak ada kepentingan praktis selama ratusan tahun sampai kriptografi datang," kata Demaine.

"Estetika tidak hanya untuk melihat hal-hal yang menyenangkan tetapi juga melihat masalah yang sederhana. Saya pikir masalah matematika sederhana, semakin besar kemungkinan maka muncul dalam beberapa aplikasi praktis penting di masa depan. Dan Kubus Rubik adalah tipe kesederhanaan," kata Demaine.

"Erik selalu tertarik memperluas jangkauan matematika populer. Ini benar-benar salah satu hal yang ia coba lakukan, membawa seluruh matematika tidak membosankan tetapi sebenarnya menyenangkan dan Anda dapat melakukan banyak hal dan ini indah," kata Marc van Kreveld, geometriolog dari Utrecht University di Belanda.

"Erik yang brilian. Dia berhasil dalam hard-core penelitian. Tetapi saya pikir mempopulerkan juga sangat diperlukan," kata van Kreveld.

Download Laporan : http://arxiv.org/abs/1106.5736
  1. Erik D. Demaine (MIT) et.al. Algorithms for Solving Rubik's Cubes. arXiv:1106.5736, (Submitted on 28 Jun 2011), http://arxiv.org/abs/1106.5736
Erik Demaine http://www.csail.mit.edu/user/666
Marc van Kreveld http://people.cs.uu.nl/marc/

Gambar : Dominick Reuter
Tinuku Store

No comments:

Post a Comment