Algoritma apa yang digunakan oleh elevator untuk menemukan jalur terpendek menuju pesanan lantai perjalanan?

Saya mencoba mensimulasikan lift, seperti biasa saya mulai dengan sangat sederhana dengan hanya mengambil satu urutan pada satu waktu, kemudian menambahkan memori ke lift dalam bentuk antrian sehingga lantai dilalui sesuai urutan penekanannya, yang jelas bukan pendekatan terbaik.

Jadi saat ini saya menggunakan logika yang sangat sederhana dan "singkat", yaitu, untuk lantai saat ini temukan lantai yang paling dekat dengan saya dan atur sebagai tujuan berikutnya dan putar sampai tidak ada lantai lagi dalam daftar.

Tapi ini tidak selalu berhasil, misalnya lift berada di lantai 3 gedung 5 lantai dan mendapat pesanan 4,5,2 jalur terpendek adalah 2-> 4-> 5 yang harganya 4 lantai tetapi menggunakan logika ini 4-> 5-> 2 yang harganya 5 memiliki peluang yang sama untuk dipetik, tergantung pada kodenya.

Bagaimana cara menemukan jalur terpendek dan membuat lift lebih efisien?

"Efisiensi" bukan fitur yang paling penting, yang paling penting adalah memastikan setiap pesanan diikuti, bahwa tidak ada kelaparan. Jika seseorang menekan 100 dan orang-orang terus menekan 1 dan 2 mungkin efisien untuk terus berjalan di antara lantai-lantai itu, tetapi alangkah baiknya jika 100 dikunjungi di beberapa titik.

Saya pikir (dari pengamatan pribadi ketika saya tertarik untuk mencari tahu) bahwa kebanyakan dari mereka:

1. Mulai pergi ke arah tombol pertama ditekan, melacak ke arah mana kita pergi
2. Ketika lantai tercapai dan tombol itu ditekan, berhenti dan buka pintu, tandai tombol untuk lantai ini karena tidak ditekan lagi.
3. • Jika masih ada lagi lantai yang perlu kita kunjungi yang berada di arah yang sama, teruslah ke arah itu .
   • Jika tidak dan masih ada lantai yang perlu kita kunjungi, bergeraklah ke arah itu.
   • Jika tidak maka kita sudah selesai dan akan mulai pada 1 ketika tombol ditekan lagi.

Perhatikan bahwa banyak elevator memiliki tombol "Saya ingin naik" dan "Saya ingin turun" di sebelah pintu alih-alih satu tombol. Algoritme hanya membutuhkan perubahan kecil: pada 2, jika satu-satunya tombol yang ditekan untuk lantai itu adalah salah satu tombol di sebelah pintu, hanya berhenti dan buka pintu jika kita menuju ke arah itu. Mungkin terus menekan tombol jika pintu terbuka karena tombol ditekan di dalam lift dan itu menuju ke arah yang salah.

Anda tidak perlu mencari tahu seluruh jalan , hanya ke arah mana untuk pergi berikutnya.

Jawaban lainnya dengan benar memberikan algoritma lift standar, yang pada dasarnya "tetap berjalan ke arah yang sama selama mungkin dan membuat setiap yang diperlukan berhenti di sepanjang jalan".

Ada algoritma lift lainnya. Misalnya, pertimbangkan sebuah gedung apartemen di mana apartemen menjadi lebih mahal saat Anda naik. Pemilik gedung mungkin memilih untuk memodifikasi algoritma lift untuk "pergi ke arah yang sama selama mungkin tetapi hanya berhenti di jalan turun". Dengan begitu jika Anda memiliki orang-orang di lift yang berada di lobi dan pergi ke 2, 5 dan 10, lift pergi ke 10, lalu 5, lalu 2, mengantarkan orang ke dalam urutan berapa banyak sewa yang mereka bayar. Tetapi tentu saja ketika orang-orang di 10 meninggalkan apartemen mereka, mereka akan lebih sering harus menunggu lebih lama untuk sampai ke lobi.

Jika Anda mencari solusi yang efisien maka buatlah metrik untuk biaya dan implementasikan banyak algoritma yang berbeda, dan jalankan simulasi. Ingatlah untuk mengukur tidak hanya biaya rata-rata, tetapi juga metrik seperti yang terlama yang harus dilayani oleh satu permintaan. Mengoptimalkan untuk rata-rata rendah kadang-kadang dapat mengoptimalkan kasus terburuk, yang buruk.

Perhatikan bahwa elevator menggunakan algoritma penjadwalan yang sama dengan beberapa pengontrol hard drive. Algoritma SCAN standar bahkan dikenal sebagai algoritma elevator . Saya pikir dalam praktiknya algoritma LOOK lebih umum, karena sedikit lebih efisien daripada SCAN.