Masalah Ketinggian Penumpukan Maksimum

8

Apakah masalah berikut telah dipelajari sebelumnya? Jika ya, pendekatan / algoritma apa yang dikembangkan untuk menyelesaikannya?

Masalah ("Masalah Ketinggian Penumpukan Maksimum")

Diberikan npoligon, temukan susunannya yang stabil dan tidak tumpang tindih yang memaksimalkan ketinggian susunnya pada lantai tetap di bawah pengaruh gravitasi.


Contoh

Tiga poligon:

masukkan deskripsi gambar di sini

dan tiga dari pengaturan stabil dan tidak tumpang tindih tak terhingga banyaknya mereka, dengan ketinggian susun yang berbeda:

masukkan deskripsi gambar di sini


Klarifikasi

  • Semua poligon memiliki massa seragam dan kepadatan yang sama
  • Gesekan adalah nol
  • Gravitasi bekerja pada setiap titik ke arah bawah (yaitu vektor gaya semuanya paralel)
  • Konfigurasi tidak dianggap stabil jika bertumpu pada titik kesetimbangan yang tidak stabil (misalnya, segitiga hijau pada gambar tidak dapat menyeimbangkan pada salah satu simpulnya, bahkan jika massa ke kiri dan kanan titik keseimbangan sama)
  • Untuk lebih memperjelas poin di atas: Sebuah poligon dianggap tidak stabil ("jatuh") kecuali ia bertumpu pada setidaknya satu titik ketat ke kiri dan setidaknya satu titik ketat di sebelah kanan pusat gravitasinya (definisi ini sangat menyederhanakan simulasi dan khususnya membuat integrasi posisi dll. tidak perlu untuk tujuan mengevaluasi apakah suatu pengaturan stabil atau tidak.
  • Masalah dalam bentuk "fisik" adalah masalah terus menerus yang hanya dapat diselesaikan kira-kira untuk sebagian besar kasus. Untuk mendapatkan masalah tersendiri yang dapat diatasi secara algoritmik, batasi simpul poligon dan penempatannya dalam pengaturan ke kisi yang sesuai.


Catatan

  • Pendekatan kekerasan apa pun jelas tidak mungkin dilakukan. Bahkan dengan kendala ketat pada penempatan poligon di dalam kisi (seperti menyediakan wilayah "ruang kisi" yang terbatas), kompleksitasnya meledak lebih dari beberapa poligon.
  • Algoritma iteratif harus membawa beberapa heuristik yang sangat pintar karena mudah untuk membangun pengaturan di mana menghapus setiap poligon tunggal dalam konfigurasi menjadi tidak stabil dan pengaturan tersebut tidak dapat dijangkau oleh algoritma yang mengandalkan setiap langkah menengah yang stabil.
  • Karena masalahnya berbau setidaknya NP- tetapi lebih mungkin EXPTIME-lengkap dalam jumlah total simpul, bahkan heuristik akan sangat menarik. Satu hal yang memberi harapan adalah kenyataan bahwa kebanyakan manusia akan mengenali bahwa pengaturan ketiga dalam contoh adalah optimal.
algorithms time-complexity optimization computational-geometry heuristics
sumber
Untuk definisi "tidak stabil" (walaupun mungkin tidak untuk definisi yang lebih akurat), seseorang pada prinsipnya dapat menyelesaikan masalah dengan menghilangkan kuantifikasi bidang tertutup nyata .
@ RickyDemer: Saya benar-benar ingin memahami itu tetapi sayangnya, meskipun saya melirik kertas dan mengikuti poin utama, saya gagal melihat hubungannya. Bisakah Anda memberi saya beberapa petunjuk lagi? Tautan antara masalah susun dan aljabar tentu terdengar menarik.
1
Itu mungkin karena saya salah menghubungkan ke prosedur keputusan daripada algoritma penghilangan kuantifier . Makalah ini adalah referensi yang jauh lebih baik untuk apa yang saya bicarakan.Saya juga menemukan sebuah makalah tentang beberapa kasus kuadrat yang mungkin cukup ketika koordinat verteks semuanya rasional.
:) Saya juga menemukan beberapa bahan yang secara eksplisit menghubungkan geometri komputasi dengan eliminasi kuantifier. Sekarang saya mengerti apa yang Anda maksud dengan "meskipun mungkin bukan untuk yang lebih akurat"; memang, tampaknya mustahil untuk memperluas metode formal murni ke fisika "nyata", di mana kendala kompleks seperti persamaan diferensial ikut bermain. Namun demikian, terima kasih atas sudut serangan yang sangat menarik, saya akan meluangkan waktu untuk mempelajarinya.

Jawaban:

1

Meskipun saya tidak mengetahui adanya algoritma spesifik untuk masalah ini, Anda dapat melakukan pendekatan ini dengan metode yang cukup efisien dengan memecahnya menjadi beberapa bagian.

Saya akan mulai dengan menemukan rotasi untuk setiap bentuk individu yang memberikan ketinggian maksimum sambil mempertahankan orientasi penyeimbangan yang valid (adalah: tidak pada titik seperti dengan segitiga). Jika bentuk memiliki beberapa ketinggian yang sama, saya akan pergi dengan konfigurasi yang memberikan area permukaan terbesar di atasnya. Setelah Anda memiliki ini, Anda kemudian dapat mengetahui cara terbaik untuk menumpuk setiap objek di manor yang dapat diseimbangkan.

GEMISIS
sumber
4
Cukup mudah untuk membuat contoh di mana pendekatan ini mengarah ke solusi yang kurang optimal. Misalnya, pertimbangkan jajar genjang yang diperoleh dengan menggunting persegi panjang yang sangat panjang (untuk membuatnya hanya stabil jika bersandar pada sisi yang panjang) ditambah segitiga yang cocok dengan sudut gesernya. Secara individual, dengan pendekatan Anda, Anda akan dipaksa untuk memutar jajaran genjang sehingga terletak pada sisi yang panjang, tetapi segitiga dapat mendukungnya untuk membuatnya "berdiri" (perhatikan bahwa masalah gesekan nol dapat dengan mudah diatasi dengan menambahkan sudut kecil ke jajaran genjang yang memungkinkan segitiga untuk "terhubung").
Itu benar, saya belum memikirkan hal itu. Salah satu solusi untuk itu bisa dengan memeriksa bentuk yang dapat digunakan sebagai dukungan untuk objek, tetapi itu mungkin tidak selalu memberikan ketinggian optimal. Anda bisa mencoba yang diam dan memeriksa beberapa konfigurasi total untuk ketinggian terbaik, karena itu masih harus lebih baik daripada kekuatan kasar.
GEMISIS
Di sini juga ada yang mengalami masalah yang signifikan, yaitu ketika bukan satu objek yang mendukung yang lain, tetapi setumpuk objek yang memiliki ketinggian yang tepat untuk mendukung objek yang sangat besar berdiri. Algoritma untuk memeriksa semua yang menjadi kompleks semena-mena. Yang sedang berkata, saya setuju bahwa itu mungkin untuk mendapatkan runtime "lebih baik daripada brute" dengan beberapa eliminasi yang masuk akal.