Algoritma untuk meminimalkan luas permukaan, diberi volume

22

Pertimbangkan tugas algoritmik berikut:

Input: bilangan bulat positif , bersama dengan faktorisasi utamanya Cari: bilangan bulat positif yang meminimalkan , tunduk pada batasan bahwan
x,y,zxy+yz+xzxyz=n

Apa kompleksitas masalah ini? Apakah ada algoritma waktu polinomial? Apakah ini NP-hard?


Masalah ini pada dasarnya bertanya: dari semua padatan persegi panjang yang volumenya dan yang dimensinya bilangan bulat, yang mana yang memiliki luas permukaan paling kecil?n

Masalah ini diajukan oleh Dan Meyer, dengan judul Masalah Matematika yang Tidak Dapat Dipecahkan oleh 1.000 Guru Matematika . Sejauh ini tidak ada guru matematika yang bekerja dengannya menemukan algoritma yang masuk akal untuk masalah ini. Dalam konteksnya, definisi "masuk akal" agak tidak tepat, tetapi sebagai ilmuwan komputer kita dapat mengajukan pertanyaan yang lebih tepat tentang kompleksitas masalah ini.

Pendekatan yang jelas adalah untuk menghitung semua kemungkinan untuk , tetapi itu membutuhkan waktu yang eksponensial. Komentator di blog Dan Meyer telah mengusulkan banyak algoritma kandidat efisien yang sayangnya semuanya ternyata tidak benar. Martin Strauss menyarankan bahwa masalah ini agaknya mengingatkan pada 3-partisi , tetapi saya tidak dapat melihat pengurangan.x,y,z


Izinkan saya juga menjernihkan beberapa kesalahpahaman yang saya lihat di komentar / jawaban:

  • Anda tidak dapat mengurangi dari 3-partisi hanya dengan mengganti setiap angka dengan kekuatannya , karena fungsi objektif dari kedua masalah berbeda. Pengurangan yang jelas tidak bekerja.q2q

  • Tidak benar bahwa solusi optimal melibatkan memilih salah satu dari untuk menjadi pembagi terdekat dari ke . Saya melihat banyak orang yang berasumsi ini adalah kasus, tetapi pada kenyataannya, itu tidak benar. Ini sudah dibantah pada posting blog Dan Meyer. Sebagai contoh, pertimbangkan ; , dan 4 membagi 68, jadi Anda mungkin berpikir bahwa setidaknya satu dari harus 4; Namun, itu tidak benar. Solusi optimal adalah , , . Contoh tandingan lain adalah , , tetapi solusi optimalnya adalahx,y,znn3n=686834x,y,zx=2y=2z=17n=22222236x=37 , , . ( Mungkin benar bahwa untuk semua , solusi optimal melibatkan membuat setidaknya satu dari sama dengan pembagi terkecil dari lebih besar dari atau pembagi terbesar lebih kecil dari - Saya tidak punya contoh tandingan sekarang - tetapi jika Anda berpikir pernyataan ini benar, itu akan memerlukan bukti. Anda benar-benar tidak dapat menganggap itu benar.)z = 2y=3z=2x , y , z n 3 nx,y,znn3 3 nn3

  • "Jadikan dengan ukuran yang sama" tampaknya tidak selalu menghasilkan jawaban optimal dalam semua kasus; lihat posting blog Dan Meyer untuk contoh-contoh tandingan. Atau, setidaknya, untuk beberapa interpretasi yang masuk akal dari frasa "buat mereka kira-kira berukuran sama", ada contoh tandingan yang menunjukkan bahwa strategi ini sebenarnya tidak optimal. Jika Anda ingin mencoba beberapa strategi semacam itu, pastikan bahwa Anda menyatakan klaim secara tepat dan kemudian berikan bukti matematika yang cermat.x,y,z

  • Waktu berjalan tidak polinomial. Agar masalah ini berada di P, waktu berjalan harus polinomial dalam panjang input . Panjang input adalah sesuatu seperti , bukan . Algoritma brute-force yang jelas dapat dibuat untuk berjalan dalam waktu atau , tetapi itu eksponensial dalam dan dengan demikian dianggap sebagai algoritma waktu eksponensial. Jadi itu tidak membantu.lg n n O ( n 3 ) O ( n 2 ) lg nHAI(n3)lgnnHAI(n3)HAI(n2)lgn

DW
sumber
1
Menarik. Pendekatan naif saya akan "membuat kira-kira ukuran yang sama", menggeneralisasi gagasan bahwa kubus adalah padatan persegi panjang dengan area permukaan terkecil untuk volume yang diberikan. Apakah itu akan berhasil? Dan jika demikian: Saya tidak melihat cara melakukannya secara efisien, tetapi apakah ada pengurangan yang lebih mudah untuk dicapai, mungkin? x,y,z
G. Bach
2
Pengurangan akan menjadi mimpi buruk karena Anda membutuhkan cara untuk menghasilkan bilangan prima yang sesuai. Yang terbaik yang bisa Anda harapkan adalah pengurangan secara acak, menggunakan sesuatu seperti Teorema Dirichlet untuk menghasilkan bilangan prima yang sesuai tetapi bahkan itu tampaknya tidak mungkin.
Tom van der Zanden
1
@ G.Bach, saya pikir artikel blog menganggap banyak heuristik dari nada itu (misalnya, mulai dengan masing-masing untuk menjadi bilangan bulat terdekat ke dan kemudian sesuaikan mereka menjadi kecil bit), dan menunjukkan contoh tandingan eksplisit untuk masing-masing. Tapi mungkin Anda memiliki algoritma yang belum mereka pertimbangkan? 3 x,y,zn3
DW
3
oeis.org/A075777 tampaknya mengklaim suatu algoritma, tetapi tampaknya tidak tercakup (n = 1332 menghasilkan 9,4,37 bukannya 6,6,37 misalnya)
Scott Farrar
1
Inilah pengamatan yang mungkin bermanfaat. Diberikan , y optimal , z benar-benar memuaskan "mimpi naif": mereka harus menjadi pasangan faktor n / x yang paling dekat dengan xy,zn/x . (Ini mudah dibuktikan.) Pada solusi optimalx,y,z, kondisi ini harus berlaku untuk ketiga variabel secara bersamaan:x,yadalah pasangan yang sesuai denganz, dll. Satu implikasi: diberikanz, hanya ada satu pasangan yang mungkinx,yyang dapat optimal. Sayangnya, (1) kondisi ini tidaksecara unikmengidentifikasi triple optimal; (2) Saya tidak melihat cara menemukan pasangan yang sesuai dengan cepat. n/xx,y,zx,yzzx,y
usul

Jawaban:

1

Berikut adalah versi modifikasi dari algoritma "pilih pembagi dekat cube root". Itu masih harus memaksa banyak kasus, jadi saya tidak yakin berapa banyak perbaikan nyata itu bijaksana untuk menghitung semua kasus. Namun, saya mengirimkannya sebagai koreksi terhadap algoritma pada OEIS (yang menghasilkan hasil yang salah) karena saya percaya itu setidaknya harus akurat.

Berikut adalah algoritma untuk menemukan (s1, s2, s3) dan luas permukaan prisma segi empat dengan volumenya n:

  1. Diberikan n, cari akar pangkat tiga.
  2. Tetapkan integer nilai awal s1 di langit-langit dari akar pangkat tiga itu.
  3. Tes untuk melihat apakah s1 adalah pembagi n, dan jika tidak, kurangi s1 dengan 1.
  4. Jika pembagi s1 ditemukan, atur s2 awal menjadi langit-langit dari akar kuadrat (n / s1).
  5. Kemudian uji untuk melihat apakah s2 adalah pembagi n / s1, dan jika tidak, kurangi s2 dengan 1.
  6. Ketika pembagi s2 ditemukan, s3 kemudian diatur ke n / (s1 * s2).
  7. Luas permukaan saat ini dihitung oleh 2 * (s1 * s2 + s1 * s3 + s2 * s3).
  8. SA saat ini dibandingkan dengan minimum saat ini. Jika luas permukaan pertama dihitung, disimpan sebagai minSA. Setelah yang pertama, kami menguji untuk melihat apakah SA saat ini lebih kecil dari minSA, dan jika demikian, simpan di minSA.

Algoritma ini menyebutkan beberapa dari tiga kali lipat (s1, s2, s3) tetapi hanya perlu menguji pembagi di bawah akar pangkat tiga. (Karena tidak semua tiga pembagi bisa di atas akar pangkat tiga). Dengan cara yang sama, s2 hanya perlu menguji pembagi n / s1 di bawah akar kuadrat n / s1, karena tidak kedua pembagi dapat berada di atas akar kuadrat)

Catatan pada langkah 3: jika root cube adalah pembagi maka n adalah cube dan kita bisa berhenti di sana dengan luas permukaan minimal 6 * s1 ^ 2 dari kotak (s1, s1, s1).

Python:

import math
def minSArectprism(n):
    s1_0 = int(math.ceil(n ** (1 / 3.0))) 
    minSA=-1
    s1 = s1_0
    while s1>=1:
        while n % s1 > 0:  
            s1 = s1 - 1
        s1quot = int(n/s1) 
        s2_0 = int(math.ceil(math.sqrt(n/s1)))
        s2 = s2_0
        while s2>=1:
            while s1quot % s2 > 0:
                s2 = s2 - 1
            s3 = int(n / (s1 * s2))  
            SA = 2*(s1*s2 + s1*s3 + s2*s3)  
            if minSA==-1:
                minSA=SA
            else:
                if SA<minSA:
                    minSA=SA
            s2 = s2 - 1
        s1 = s1 - 1    
    return minSA
Scott Farrar
sumber
Algoritme Anda membutuhkan waktu yang eksponensial. Setiap loop memeriksa sekitar kandidat yang memungkinkan, jadi waktu tayang adalahO( 3 n3, yang eksponensial, tidak polinomial waktu. Dengan demikian, algoritma ini tidak menjawab pertanyaan. (Saya sudah menyebutkan algoritma waktu eksponensial dalam pertanyaan.)O(n32)=O(n2/3)
DW
Hmm, y tidak terbatas di bawah akar pangkat tiga dari n, misalnya, n = 1332, kita akhirnya akan menguji s1 = 2, artinya s2 akan berada di bawah akar kuadrat dari 1332/2 ~ = 26. Memang (2,18, 37) diuji dengan y dan z di atas akar pangkat tiga.
Scott Farrar
@ScottFarrar, ya, saya tahu. Saya tidak memasukkan semua detail berdarah dari analisis kompleksitas; tidak ada ruang dalam satu komentar. Jika Anda memasukkan detail berdarah, saya pikir Anda akan menemukan bahwa Anda mendapatkan waktu berjalan yang saya kutip. Anda dapat mempercayai saya :-), atau membaca pertanyaan referensi kami untuk mempelajari lebih lanjut tentang detail mengerikan itu. Dalam kasus apapun, bahkan jika Anda menghapus lingkaran, lingkaran luar masih melakukan iterasi, sehingga waktu berjalan dari algoritma Anda setidaknya Ω ( n 1 / 3 ) - yaitu, hal ini tentunya eksponensial. Θ(n1/3)Ω(n1/3)
DW
0

Masalahnya tentu saja terkait dengan kompleksitas anjak jika dekomposisi utama tidak diberikan. Mengingat faktor-faktor, dan mengambil log dari semua faktor utama, masalah ini tampaknya hampir sama dengan meminimalkan penyimpangan-dari-rata-rata jumlah partisi (latihan, mungkin baik secara analitis atau eksperimental, temukan seberapa dekat perkiraan intuitif ini dari masalah memegang).k

Inilah kasus 3-arah (jumlah partisi adalah ). kasus 2-arah telah dipelajari secara ekstensif dan NP keras (dari 1 st ref). (Kasus 2-cara ini tidak cukup sama dikenal NP-lengkap 2-way masalah partisi di mana jumlah partisi adalah sama. Catatan jumlah partisi yang sama menyiratkan 0 penyimpangan dalam jumlah partisi dan sebaliknya. ) 2 nd ref studi 3- cara dan partisi n -jalan, sebagian secara empiris, di mana tidak ada studi sebanyak kasus 2-arah.log(x),log(y),log(z)n

ay
sumber
Jawaban ini tidak membantu dan tidak menjawab pertanyaan. 1. Saya mencari bukti atau bukti, bukan spekulasi. Tidak ada bukti bahwa meminimalkan penyimpangan menghasilkan solusi yang optimal. Bahkan jika itu benar, itu tidak akan menjawab pertanyaan: itu tidak akan memberi tahu kita kompleksitas meminimalkan penyimpangan. 2. Referensi pertama adalah tentang 2-partisi. Menunjuk saya ke referensi tentang 2-partisi tidak membantu. Saya sudah menjelaskan dalam pertanyaan mengapa masalah saya bukan hanya 3-partisi (atau 2-partisi). Makalah tentang varian masalah yang tidak saya tanyakan tidak membantu.
DW
Tolak sampel dengan klaim bahwa Anda harus meminimalkan penyimpangan absolut dari mean: . Kemudian 1 , 4 , 17 menghasilkan deviasi absolut 2,85342 , yang merupakan deviasi absolut serendah mungkin. Namun 2 , 2 , 17 adalah solusi yang tepat (optimal), dan memiliki luas permukaan yang lebih kecil. [Dengan deviasi absolut dari mean, saya secara khusus berarti | log ( x ) - μ | + | log ( y ) - μ | + |n=681,4,172.853422,2,17(di mana μ = ( log ( x ) + log ( y ) + log ( z ) ) / 3 ).]|log(x)-μ|+|log(y)-μ|+|log(z)-μ|μ=(log(x)+log(y)+log(z))/3
DW
baik! tidak pernah ada klaim bahwa algoritma ini benar, didasarkan pada pemeriksaan beberapa contoh & saran lainnya dalam komentar. ini hanya contoh tandingan tunggal (Anda menunjukkan metode minimasi deviasi cacat pada posting yang direvisi ). pertanyaan "seberapa sering" algoritma ini memberikan solusi yang tepat menarik karena dapat memberikan beberapa petunjuk untuk metrik optimasi yang benar. menduga algoritma ini "sering" memberikan jawaban yang benar. ref 2 arah adalah untuk menunjukkan versi deviasi dari masalah yang berbeda dari versi yang tepat pada wikipedia dll
vzn
lihat juga Bukti dan sanggahan
vzn
0

Edit

Inilah argumen informal untuk alasan mengapa algoritma cepat tidak mungkin ada. Kalimat itu tidak berubah, tetapi saya telah mengambil apa yang dulu ada di sini karena terstruktur terlalu banyak seperti bukti formal di bagian berikutnya dan diskusi semakin teralihkan ke bug-nya, beberapa di antaranya saya perhatikan sendiri dan satu yang dengan ramah ditunjukkan DW kepada saya. Sebagai gantinya, saya mencoba mengungkapkan intuisi di baliknya.

N

Apa yang terjadi ketika kita menerjemahkan langkah-langkah yang sama menjadi aljabar yang berbeda, seperti penjumlahan dan pengurangan alih-alih perkalian dan pembagian? Kita tahu (lihat lemma di bawah) bahwa algoritma kami akan menemukan 3-partisi yang produknya sama, jika ada, atau menentukan tidak ada 3-partisi seperti itu. Jadi, jika kita bisa menerjemahkan teknik yang sama ke dalam kelompok aditif, kita bisa menemukan 3-partisi yang jumlahnya sama, atau menentukan bahwa tidak ada partisi seperti itu. Dengan kata lain, kita bisa menyelesaikan 3-partisi dalam waktu polinomial. Itu tidak masuk akal.

Jadi, mengapa algoritma seperti itu bisa berfungsi untuk multiplikasi dan gagal sebagai tambahan? Salah satu alasan yang mungkin adalah bahwa setiap bilangan bulat memiliki faktorisasi prima yang unik di bawah multiplikasi, tetapi merupakan siklik yang ditambahkan. Lain adalah bahwa perkalian membentuk cincin dengan tambahan, sehingga Anda memiliki satu set operasi yang dapat Anda gunakan. Lain adalah bahwa Anda harus menggeneralisasi algoritma untuk bekerja untuk non-bilangan prima, dan itu mungkin tergantung pada keutamaan mereka. DW yang ditunjukkan adalah bahwa metode terjemahan spesifik mungkin secara eksponensial meningkatkan ukuran input Anda. Dan mungkin P = NP setelah semua.

Tetapi jika itu adalah celah yang memungkinkan algoritma cepat bekerja, saya pikir itu masih berguna untuk diketahui, karena itu menunjukkan di mana kita harus memfokuskan upaya kita. Kita harus mencari sesuatu yang akan rusak jika kita mencoba menerapkannya pada masalah NP-complete. Suatu pendekatan yang akan digeneralisasikan ke aljabar lain mungkin menggonggong pohon yang salah. Saya curiga, multiplikasi tidak cukup berbeda untuk berhasil, tetapi itu hanya dugaan.

Kata pengantar singkat

m=N3(Sebuahm,bm,mSebuahb)Sebuahb(Sebuahb+1Sebuah+1b)m2Sebuah=b=1

xyz=N

(Sebuahm)(bm)+(Sebuahm)(mSebuahb)+(bm)(mSebuahb)=Sebuahbm2+m2b+m2Sebuah=(Sebuahb+1Sebuah+1b)m2

f(Sebuah,b)=Sebuahb+1Sebuah+1bδfδSebuah=b-1Sebuah2δfδb=Sebuah-1b2Sebuah=b2,b=Sebuah2SebuahbSebuah=b=1

Motivasi langsung saya untuk membuktikan ini adalah untuk mengisi gelombang tangan dalam bukti saya di atas bahwa, jika solusi kubus sempurna ada, itu optimal. Namun, rumus ini bisa berguna untuk memangkas pohon pencarian.

Berbagai Macam Pikiran

Saya tidak melihat kesimetrisan yang jelas kecuali pertukaran dari x, y dan z, yang hanya memberi kita paling tidak faktor konstan 6. Kita memang punya beberapa speedups untuk 2-partisi yang pada dasarnya mengatakan kita ingin kedua istilah untuk sedekat mungkin satu sama lain, tetapi saya tidak segera melihat aplikasi untuk masalah ini.

Dari atas kepala saya, hanya mengambil log dari semua angka segera mengurangi ini menjadi masalah 3-partisi klasik menggunakan penambahan, atau setara, mengambil beberapa angka ke kekuatan angka dalam masalah penambahan 3-partisi apapun mengubahnya menjadi masalah multiplikasi seperti ini. Itu menyiratkan masalah ini seharusnya tidak mudah. Di sini kita memang memiliki faktorisasi utama, sedangkan faktorisasi itu tidak akan menjadi prima, tetapi apakah itu membantu kita?

Secara grafis, permukaan xyz = 0 akan terlihat seperti penyatuan bidang xy-, yz- dan xz, dan untuk setiap n positif, persamaannya akan terlihat seperti y = n / xz, sehingga setiap irisan sepanjang bidang koordinat akan menjadi sebuah hiperbola. Secara umum kita dapat mengatakan bahwa jumlah yang kita coba untuk meminimalkan adalah yang terendah di titik asal dan tumbuh paling cepat di sepanjang garis di mana x = y = z. Jika kita dapat mencari hanya di manifold ini, kita mungkin bisa menguranginya menjadi masalah dua dimensi.

Davislor
sumber
Jika x + y + z = n, 2 ^ n = 2 ^ (x + y + z) = 2 ^ x * 2 ^ y * 2 ^ z, yang merupakan contoh dari masalah ini dikurangi pembatasan bahwa input adalah dekomposisi utama produk. Mereka semua akan menjadi kekuatan dua.
Davislor
Memang benar bahwa bobot untuk meminimalkan akan berbeda, tetapi jika x = y = z dalam masalah asli, tidak akan x'y '+ x'z' + y'z 'diminimalkan dalam masalah yang sesuai di mana setiap w adalah diganti dengan w '= 2 ^ w, yang berarti bahwa jika ada solusi untuk masalah asli, pengurangan akan menemukannya? Kita mungkin mendapatkan solusi palsu dari masalah yang diubah, tetapi kita dapat mendeteksi itu dalam waktu linier ketika mengkonversi kembali dengan memverifikasi jumlahnya.
Davislor
xy+yz+xzxyz=nx,y,zn3
@vzn: Kami mencoba meminimalkan luas permukaan, bukan memaksimalkannya. Jika masalah 3-partisi memiliki solusi, itu diterjemahkan menjadi masalah dimensi kotak yang dimodifikasi di mana solusinya adalah kubus sempurna. Algoritma poli-waktu hipotetis akan menemukan faktor-faktor sisi kubus itu, dan kemudian kita dapat menerjemahkannya kembali ke domain asli, sambil memeriksa solusi palsu, dalam waktu linier. Itu menunjukkan suatu algoritma untuk masalah yang sedikit rileks dapat berfungsi sebagai ramalan untuk masalah yang sulit, membuatnya tidak mungkin algoritma yang lebih baik daripada eksponensial ada.
Davislor
? Saya tidak setuju dengan Anda. bukankah kita mengatakan hal yang sama? tlg mampir ke Computer Science Chat untuk menguraikan / memilah ini lebih jauh. juga tidak dapat mengikuti klaim @DWs bahwa transformasi logaritmik tidak berfungsi, bukan? Saya menggunakan beberapa analisis Anda (yang tampaknya sesuai target) sebagai dasar untuk jawaban saya sendiri.
vzn