Mengunjungi titik pada garis angka sambil meminimalkan biaya yang tidak terkait dengan jarak

Saya butuh bantuan untuk masalah ICM ACM ini. Ide saya saat ini adalah untuk memodelkan ini sebagai masalah jalur terpendek, yang dijelaskan di bawah pernyataan masalah.

Masalah

Ada N = 1000kontainer limbah nuklir yang terletak di sepanjang garis angka 1-D pada posisi yang berbeda dari -500,000 to 500,000, kecuali x=0. Seseorang bertugas mengumpulkan semua tempat sampah. Setiap detik bahwa wadah limbah tidak dikumpulkan, ia memancarkan 1 unit radiasi. Orang tersebut mulai x = 0dan dapat memindahkan 1unit setiap detik, dan mengumpulkan sampah membutuhkan waktu yang sangat sedikit. Kami ingin menemukan jumlah minimum radiasi yang dilepaskan saat mengumpulkan semua wadah.

Input sampel:

4Wadah terletak di [-12, -2, 3, 7].

Cara terbaik untuk mengumpulkan wadah-wadah ini adalah [-2, 3, 7, -12], untuk emisi minimum 50unit. Penjelasan: orang tersebut pergi ke -2dalam 2 detik dan selama waktu itu 2 unitsradiasi dipancarkan. Dia kemudian pergi ke 3(jarak:) 5sehingga barel telah merilis 2 + 5 = 7unit radiasi. Dia membutuhkan 4lebih banyak detik untuk sampai ke x = 7tempat laras itu dipancarkan 2 + 5 + 4 = 11. Dia membutuhkan beberapa 19detik untuk sampai ke x = -12tempat laras itu dipancarkan 2 + 5 + 4 + 19 = 30. 2 + 7 + 11 + 30 = 50, yang jawabannya.

Catatan

Ada O(N!)solusi yang jelas . Namun, saya telah menjelajahi metode serakah seperti pindah ke yang terdekat, atau pindah ke cluster terdekat tetapi itu tidak berhasil.

Saya sudah memikirkan masalah ini cukup lama, dan telah memodelkannya sebagai masalah pencarian grafik:

1. Kami menyisipkan 0sebagai posisi dasar (Ini akan menjadi keadaan awal)
2. Kemudian, kami menyortir posisi dari paling tidak ke yang terbesar.
3. Kami kemudian melakukan BFS / PFS, di mana stateterdiri dari
   • Dua bilangan bulat ldan ryang mewakili rentang berdekatan dalam susunan posisi yang diurutkan yang telah kami kunjungi
   • Integer locyang memberi tahu kita apakah kita berada di titik akhir kiri atau kanan rentang
   • Integer timeyang memberi tahu kita waktu yang telah berlalu
   • 'Biaya' integer yang memberi tahu kami total biaya sejauh ini (berdasarkan node yang kami kunjungi)
4. Dari masing-masing negara kita dapat pindah ke [l - 1, r] dan [l, r + 1], menyesuaikan 3 bilangan bulat lainnya sesuai
5. Keadaan akhir adalah [0, N], memeriksa kedua posisi akhir.

Namun, tampaknya itu [L, R, loc]tidak secara unik mendefinisikan keadaan, dan kita harus menyimpan L, R, loc, and time, sambil meminimalkan costmasing-masing. Ini mengarah ke algoritma eksponensial, yang masih terlalu lambat untuk kebaikan apa pun.

Adakah yang bisa membantu saya memperluas ide saya atau mendorong saya ke arah yang benar?

Sunting: Mungkin ini dapat dimodelkan sebagai masalah optimisasi pemrograman dinamis? Berpikir tentang itu, ia memiliki masalah yang sama dengan solusi pencarian grafik - hanya karena saat costini rendah tidak berarti itu adalah jawaban yang optimal untuk sub masalah, karena timejuga sangat mempengaruhi jawaban.

Serakah tidak berfungsi: Saya memiliki algoritme seleksi rakus yang memperkirakan biaya pindah ke tempat tertentu (misalnya jika kita bergerak ke kanan, kita menggandakan jarak ke barel kiri dan semacamnya).

Bisakah Anda melakukan pencarian Prioritas-pertama, dengan heuristik? Heuristik dapat menggabungkan biaya perjalanan saat ini dengan jumlah waktu yang telah berlalu.

Saya pikir Anda dapat meningkatkan ini dengan melihat masalah sebagai grafik pasangan posisi yang diarahkan.

Untuk contoh ini saya akan menggunakan baris dengan nilai -9, -6, -1, 3, dan 5.

Karena terlalu sulit untuk menggambar grafik hanya dengan teks, saya akan mewakili pasangan sebagai sebuah tabel. Kita bisa menganggap sel-sel itu mewakili keadaan di mana semua wadah di antara kedua posisi itu dikumpulkan. Setiap sel memiliki dua nilai, satu mewakili biaya untuk pergi ke kiri, yang lain mewakili biaya untuk pergi ke kanan (ke wadah berikutnya).

Nilai-nilai hanya dapat dihitung sebagai jarak antara dua titik dikalikan dengan jumlah barel di luar dua titik +1 . Sel di mana kedua angka memiliki tanda yang sama mewakili kasus ketika semua barel dari tanda yang berlawanan telah dikumpulkan. Ini dihitung hanya menggunakan jumlah barel dalam arah yang jauh dari nol.

Dalam tabel nilai X berarti bahwa Anda tidak dapat pergi ke arah itu (semua barel di arah itu telah diambil). Baris mewakili posisi kolektor saat ini dan kolom mewakili lokasi laras berlawanan berikutnya.

    +------+------+------+------+------+
    |  -9  |  -6  |  -1  |   3  |   5  |
+---+------+------+------+------+------+
|-9 |      |      |      | X, 24| X, 14|
+---+------+------+------+------+------+
|-6 | 3, X |      |      | 9, 27| 6, 22|
+---+------+------+------+------+------+
|-1 |      |10, X |      |20, 8 |15, 18|
+---+------+------+------+------+------+
| 3 |24, 4 |27, 6 |16, 8 |      | X, 2 |
+---+------+------+------+------+------+
| 5 |14, X |22, X |18, X |      |      |
+---+------+------+------+------+------+

Aturan untuk bergerak di antara kotak bisa agak membingungkan.

Untuk kolom bernomor negatif, aturannya adalah sebagai berikut:

• Ke kanan bergerak ke bawah satu sel.
• Ke kiri bergerak ke bawah satu sel lalu cermin melintasi diagonal.
• Jika nilai yang benar adalah X, ke kiri bergerak ke atas diagonal (di mana kolom dan baris sama) dan dibiarkan satu.

Untuk kolom bernomor positif, aturannya adalah sebagai berikut:

• Ke kiri bergerak ke atas satu sel.
• Ke kanan bergerak ke atas satu sel dan kemudian mirror melintasi diagonal.
• Jika nilai kiri adalah X, ke kanan bergerak ke bawah ke diagonal dan ke kanan satu per satu.

Sekarang kita dapat menjalankan algoritma Dijkstra untuk menghitung jalur terbaik, menggunakan aturan gerakan ini untuk melintasi grafik. Posisi awal kami adalah (-1, 3) dan (3, -1), masing-masing dengan biaya awal 5 dan 15. Setelah kami menghitung nilai untuk dua posisi ujung (kiri (-9, -9) dan kanan (5, 5)) yang lebih kecil dari keduanya adalah jawaban kami.

Waktu berjalan untuk masing-masing langkah adalah:

• O (N log N) untuk awalnya mengurutkan nilai input di sepanjang baris
• O (N ^ 2) untuk menghitung tabel / grafik
• O (N ^ 2 log N) untuk menjalankan Dijkstra pada grafik (Catatan: paling banyak ada dua sisi untuk setiap titik yang diberikan).

Dua langkah pertama didominasi oleh yang terakhir, jadi runtime keseluruhan Anda adalah O (N ^ 2 log N) yang seharusnya menjadi runtime yang cukup baik untuk tantangan.

Jarak terdekat

Saya menulis aplikasi Java kemarin untuk menyelesaikan masalah. Masalahnya pada dasarnya adalah masalah jarak pendek, seperti kata SRJ dalam komentarnya. Radiasi hanya menunjukkan bahwa Anda dapat mengakumulasi nilai bersama dengan jarak terdekat.

Pada dasarnya, inilah yang saya lakukan.

• Masukkan nomor kontainer dalam Daftar <Integer>
• Sedangkan Daftar berisi elemen;
  • Temukan elemen yang paling dekat
  • Jika ada satu elemen, berjalanlah ke sana dan hapus elemen itu.
  • Jika ada dua elemen, salin path dan berjalan ke kedua elemen
• Temukan jalur dengan nilai radiasi terkecil.

Ini beberapa output dari aplikasi

10 containers are located at [-90, -75, -47, -9, 9, 26, 48, 50, 64, 79].

You walk to position -9 and pick up the container.  The total radiation emitted is 90 units.
You walk to position 9 and pick up the container.  The total radiation emitted is 252 units.
You walk to position 26 and pick up the container.  The total radiation emitted is 388 units.
You walk to position 48 and pick up the container.  The total radiation emitted is 542 units.
You walk to position 50 and pick up the container.  The total radiation emitted is 554 units.
You walk to position 64 and pick up the container.  The total radiation emitted is 624 units.
You walk to position 79 and pick up the container.  The total radiation emitted is 684 units.
You walk to position -47 and pick up the container.  The total radiation emitted is 1,062 units.
You walk to position -75 and pick up the container.  The total radiation emitted is 1,118 units.
You walk to position -90 and pick up the container.  The total radiation emitted is 1,133 units.

Saya tidak mengoptimalkan algoritme dengan cara apa pun. Saya bahkan tidak memperhatikan bahwa daftar input angka diurutkan. (Saya seorang doofus.)

Ketika saya menjalankan kode saya dengan nilai maksimum, 1.000 kontainer dan kisaran dari -500.000 hingga 500.000, kode saya membutuhkan waktu 3 detik untuk dieksekusi. Sebagian besar waktu itu menulis 1.000 baris cetak ke konsol.

Saya bukan orang O besar, tapi saya pikir kekuatan kasar saya berjalan algoritma jalur terpendek adalah O (N kuadrat), bukan O (N!).

Jika saya mengambil keuntungan dari fakta bahwa nomor input diurutkan, sehingga saya hanya perlu memeriksa dua angka di kedua sisi di mana saya saat ini berada, saya bisa mendapatkan aplikasi di dekat O (N). Saya hanya perlu memeriksa 2 angka karena saya menghapus elemen dari Daftar begitu saya mendapatkannya.

Anda menggunakan berbagai algoritma, seperti algoritma serakah, untuk menemukan solusi perkiraan.

Jika program saya membutuhkan waktu 3 jam untuk berjalan alih-alih 3 detik, maka Anda harus memilih.

Apakah solusi yang cukup baik cukup baik?

Dengan kata lain, apakah saya bersedia untuk berdagang kecepatan pemrosesan untuk jawaban yang cukup baik?

Jika jawaban yang cukup baik cukup baik, maka Anda menggunakan algoritma aproksimasi.

Jika Anda menginginkan jawaban yang sempurna, Anda harus menempuh semua jalur terpendek. Tidak ada jalan pintas.

Jika ada yang ingin saya memposting kode saya, saya akan. Saya yakin masih ada bug, karena saya ingin melihat apakah saya bisa menerapkan algoritma jalan terpendek.

Saya punya solusi yang akan menyelesaikan masalah ini 2^Ntepat waktu, yang buruk, tetapi saya pikir ini adalah cara yang membantu untuk membingkai masalah, jadi saya pikir saya akan memposting.

Daripada memodelkan masalah sebagai grafik, saya akan memodelkannya adalah pohon keputusan biner (katakanlah T). Di setiap level Anda harus memilih antara kanan atau kiri. Cukup mudah untuk menghitung 'biaya' setiap sisi. Membiarkan h(K)menjadi tinggi dari simpul saat ini K,, maka biaya tepi pergi ke left_child(K) = h(K) x dist(K, left_child(K)). Perhitungan serupa sudah cukup untuk biaya tepi ke anak yang tepat. Anda membangun pohon ini, dan melacak biaya kumulatif tepi semua jalan ke bawah, dan melaporkan jalan ke simpul daun dengan total biaya terkecil.

Perhatikan bahwa perhitungan biaya berfungsi karena panjang setiap tepi dist(K, left_child(K))mewakili waktu untuk pergi ke situs berikutnya, sedangkan ketinggian subtree adalah jumlah situs yang tersisa (mis. Masih memancarkan radiasi).

Sekarang trik dalam kerangka ini adalah untuk menentukan apakah ada beberapa heuristik yang dapat Anda gunakan untuk 'membuktikan' bahwa Anda dapat mengabaikan memperluas pencarian di sepanjang beberapa cabang. Intuisi saya adalah bahwa untuk heuristik semacam itu ada pengaturan situs yang akan mengalahkannya, tetapi mungkin seseorang dapat menemukan sesuatu.

Sejumlah orang telah mengusulkan untuk menerapkan solusi jalur terpendek untuk grafik, saya ragu apakah solusi semacam itu dapat bekerja. Tetangga Anda di 'grafik' dalam masalah akan berubah tergantung pada jalur yang Anda ikuti. Misalnya dalam posting asli Anda dengan [-12, -2, 3, 7]jika Anda pergi ke -2kemudian -12dan 3menjadi 'tetangga' dan jika Anda pergi ke 3kemudian -2dan 7tetangga. Setiap 'pasangan' yang mungkin dari nilai positif dan negatif dapat berpotensi menjadi neigbours dalam grafik akhir. Saya tidak tahu adanya algoritma jalur terpendek yang terbukti benar dalam grafik dinamis.

Saya pikir paling masuk akal untuk memikirkan setiap tahap hanya sebagai pilihan biner antara pergi ke kanan ke tong terdekat dan pergi ke kiri ke tong terdekat. Cukup memiliki fungsi biaya yang merinci jumlah unit radiasi yang akan dikeluarkan secara total dengan melakukan gerakan apa pun dan memilih unit dengan biaya terendah.

JANGAN hanya mempertimbangkan tong terdekat, tetapi anggaplah bahwa dengan menjauh dari tong Anda secara efektif menambahkan dua kali radiasi karena dengan menjauh Anda juga harus mengeluarkan biaya karena harus pindah kembali ke arah itu nanti.

Dalam contoh Anda [-12, -2,3,7], bergerak ke kiri akan menghasilkan total 14 (2 + 2 + 10) di sebelah kiri, dan 18 (2 + 2 + 5 + 9) di kanan, untuk total 22. Bergerak ke kanan akan menimbulkan 10 (3 + 3 + 4) di sebelah kanan, dan 26 (3 + 3 + 5 + 15) di sebelah kanan. Jelas kiri adalah solusi yang tepat pada awalnya. Perhitungan serupa dapat dilakukan untuk setiap gerakan berturut-turut.

Setelah itu masalahnya pada dasarnya berkurang menjadi pencarian, jadi kompleksitasnya harus O (nlog (n)), yang JAUH lebih baik daripada O (n!). Saya percaya ini adalah kompleksitas terendah yang dapat ada untuk masalah ini karena pada dasarnya ini adalah algoritma pencarian berbasis perbandingan yang tidak mungkin dilakukan lebih baik daripada O (nlog (n))

Tampaknya saya tidak cukup jelas dengan uraian ini, jadi saya telah memutuskan untuk membuatnya sedikit lebih terprogram: 1. Hitung biaya yang dikeluarkan dengan pergi ke kiri, dan biaya yang dikeluarkan dengan berjalan lurus berdasarkan posisi saat ini 2. Bergerak masuk arah yang paling murah 3. Lepaskan barel yang dijangkau dari pertimbangan dalam menghitung biaya bergerak ke suatu arah

Menghitung biaya: 1. Identifikasi laras terdekat dalam arah yang diberikan. Katakanlah $ dist adalah jarak dari posisi saat ini ke barel terdekat di arah yang diberikan. 2. Biaya diinisialisasi sebagai N * $ dist di mana N hanya menganggap barel masih aktif. 3. Untuk ini, tambahkan jarak bahwa posisi baru yang ditunjukkan oleh $ dist akan dari setiap barel yang tersisa.

Solusi sebagian - saya akan kembali lagi nanti.

Asumsikan strategi "default" dijalankan dari kiri atau kanan, mana yang lebih murah. Sekarang tanyakan, apakah ada gunanya melakukan perjalanan kecil dengan cara lain untuk mengambil satu barel. Cukup mudah untuk menghitung jawabannya.

Untuk Anda sampel input, menjalankan semua jalan yang benar lebih murah daripada semua jalan di kiri. Apakah akan -2 bernilai perjalanan samping? Ini mengurangi biaya menjalankan semua jalan yang benar dan kemudian kembali ke 0 oleh 14 (karena Anda "membayar" 4 unit radiasi per gerakan dari 0 ke 3 pada strategi default, sekarang turun ke 3, Anda membayar 3 dari 3 ke 7, sekarang 2, dll), ditambah mengurangi satu per gerakan, biaya bergerak Anda dari 0 ke -2, sehingga menghemat 2 lebih untuk total 16.

Namun, itu menambah biaya untuk -2 lalu kembali ke 0 dari 14 (4 unit per pindah ke -2, 3 per pindah kembali ke 0), untuk keuntungan bersih (16-14) = 2. Perhatikan bahwa untuk menghitung ini, Anda tidak perlu mengevaluasi biaya yang tepat untuk menyelesaikan seluruh masalah untuk setiap keputusan - Anda memiliki informasi yang cukup untuk memutuskan hanya dengan mengetahui apakah menjalankan semua jalan yang tersisa lebih murah daripada berjalan dengan cara yang benar, plus bagaimana banyak wadah limbah ada di setiap sisi Anda, dan jarak ke 2. terdekat. Jadi itu O (N ^ 2).

Kecuali untuk satu masalah penting - saya berasumsi Anda akan berlari sampai akhir, dan kami tahu Anda mungkin akan kembali berlipat ganda. Untuk membersihkannya, kita perlu memperbarui perhitungan saya. Untuk input sampel, saya berasumsi Anda akan menghemat 14 dengan memancarkan 1 lebih sedikit radiasi total per unit per detik sambil berlari dari 0 hingga 7 dan kembali. Tetapi, jika Anda menggandakan kembali sebelum berlari ke 7, penghematan akan berkurang.

Itu sangat buruk, karena, saya tidak tahu bagaimana menghitung double-back berikutnya tanpa mencoba semua kemungkinan, yang membuat kita kembali ke O (2 ^ N).

Kecuali - ini 2 ^ N dengan pemangkasan. Saya menghitung bahwa "perjalanan samping" ke -2 berharga 14, tetapi naik 16, jika saya tidak memiliki lebih banyak perjalanan samping sebelum saya mencapai angka paling kanan. Jika angka paling kanan adalah 5, saya akan segera tahu bahwa perjalanan samping ke -2 tidak dapat membuahkan hasil. (Biaya masih 14, manfaat maksimal 12). Saya juga tidak harus mempertimbangkan pergi ke -2 lalu melakukan perjalanan samping sebelum mencapai 6, karena itu selalu lebih rendah daripada langsung ke titik itu di tempat pertama.

Saya pikir Anda dapat menyelesaikannya menggunakan pencarian pertama, menjaga tidak lebih dari 2 * N ^ 2 tupel (boolean, int, int, int, string) di mana string sepanjang jalur rumit.

Tupel adalah (min atau max boolean, posisi min yang dilalui, posisi maks yang dilalui, total radiasi yang dipancarkan, riwayat jalur).

Saya melihat algoritma berjalan seperti ini:

1. Inisialisasi kumpulan tupel ke satu entri, (min, 0, 0, 0, "")
2. Temukan elemen di kolam yang memiliki radiasi minimal yang dipancarkan. Jika min dan maks sesuai dengan min dan maks semua barel, maka riwayat jalur adalah solusi optimal. Atau hapus dari kolam.
3. Hitung 2 keturunan tuple ini, yang masing-masing sesuai dengan berjalan ke kiri atau kanan ke barel yang belum diproses berikutnya.
4. Masukkan keturunan ke kolam. Jika sudah ada elemen dalam kumpulan dengan boolean yang sama, min, dan maks sebagai keturunan baru, maka buang elemen dengan jumlah radiasi yang lebih tinggi.
5. kebagian 2.

Menemukan dan menghapus tupel yang didominasi akan secara dramatis meningkatkan kinerja. Mungkin bermanfaat untuk menambahkan bendera 'telah dikembangbiakan' untuk setiap tuple, dan meninggalkan tupel dikembangbiakan di kolam.

Ada juga beberapa keputusan penting yang harus dibuat dalam memutuskan bagaimana menyimpan tuple, dan mencari mereka untuk dominasi dan elemen baru untuk berkembang biak.