1

Тема: Практична задача. Стратегія вибору ліфта.

Ситуація: в моїй установі 2 ліфта і 5 поверхів. На всіх поверхах (крім першого й останнього, але це можна ігнорувати) по дві кнопки виклику для кожного: вгору і вниз, і індикатор номеру поверху, де знаходиться ліфт.  Якщо ліфт іде в якийсь бік, він не реагує на кнопки виклику в інший бік, доки не залишиться викликів в напрямку руху, тоді їде назад до найближчого виклику. В людини на поверсі є інформація з 4 світлодіодів (чи викликали ліфт з цього поверху в певному напрямку) і номери двох поверхів, на яких знаходяться ліфти. Рух відносно активний, а стан ліфту (стоїть чи їде кудись) ніяк не позначається на індикаторі, тому постає питання: яка оптимальна стратегія виклику ліфта, щоб і самому якнайшвидше дочекатися, і іншим заважати якнайменше (реально вже ненавиджу людей, що викликають одразу обидва ліфти).
Можливість ходити пішки, наявність підвалу, в який ходить тільки один ліфт, але люди там не працюють, зламану кнопку виклику одного з ліфтів вгору на третьому поверсі, часовий розподіл поїздок (вранці і ввечері значно більше поїздок на перший поверх) можна ігнорувати.

Наразі я для себе розробив таку стратегію:

Прихований текст

1. Якщо один з ліфтів на поверсі - викликаємо його.
2. Якщо ліфта на поверсі нема - викликаємо той, що знаходиться якнайдалі в протилежному напрямку руху (якщо їдемо з 4 на 5, то викликаємо з 2, а не з 3 поверха).
3. Якщо ліфтів в тому напрямку нема - викликаємо той, що знаходиться якнайдалі від нас.
Виклик ліфту, що знаходиться далі, здається, зменшує ймовірність того, що його "викрадуть" - принаймні за суб'єктивними враженнями :)

Подякували: quez1

2

Re: Практична задача. Стратегія вибору ліфта.

На форумі щось цікаве :)

Тут є багато невідомих, таких як наявність людей, які активно переміщуються між поверхами, відмінними від першого, швидкість ліфта і середній час, який ліфт тратить на завантаження. Якщо вважати це несуттєвим, то в мене виходить така схема:
- Знаходимось на першому або останньому поверсі. Деякий час (приблизно половину середнього часу посадки) чекаємо, після чого обираємо той ліфт, який, з урахуванням поточної швидкості, прибуде на потрібний поверх швидше.
- Знаходимось на другому поверсі. Якщо їдемо догори і є ліфт на першому поверсі, то обираємо його, інакше користуємось стратегією з першого пункту. Все це справедливо і для четвертого поверху, який є другим зверху.
- Знаходимось на третьому поверсі. Для простоти будемо вважати, що їдемо вниз. Тоді з двох ліфтів вище обираємо будь-який (гарантовано чекаємо 2 поверхи у випадку п'ятого поверху, у випадку чекаємо 1 або 3 поверхи з імовірністю 0.5, маточікування 2); якщо один зверху, то обираємо його; в іншому випадку вам не пощастило :) Тут варто обрати той, що рухається в вашому напрямку.

А тепер почитаю вашу стратегію.

3

Re: Практична задача. Стратегія вибору ліфта.

Виклик ліфту, що знаходиться далі, здається, зменшує ймовірність того, що його "викрадуть" - принаймні за суб'єктивними враженнями :)

Скоріше, зменшує імовірність поїздки на ньому в напрямку від вас - там тупо менше поверхів.

4

Re: Практична задача. Стратегія вибору ліфта.

Піти і побити інженерів які поставили кнопки виклику для кожного ліфта окремо.

5

Re: Практична задача. Стратегія вибору ліфта.

Ще скажіть, де бюджетній установі взяти гроші на переобладнання ліфтів.

6

Re: Практична задача. Стратегія вибору ліфта.

На horizont park (в Києві), де я раніше працював є 18 поверхів, які обслуговують 8 ліфтів місткістю по 10-15 (здається) людей, причому ліфти на стільки швидкісні, що коли я тільки влаштовувався на роботу, то при спуску з 18 на 1 поверх явно відчувався перепад тиску у вухах (потім звик).

Але навіть і там люди викликають дуже часто усі 8 ліфтів одразу. І що цікаво, ліфти явно по різному запрограмовані. Один ліфт на стільки "привітний", що буквально на кожному поверсі стає щоб взяти ще людей, навіть якщо йому вже "нікуди" (схоже його привітність продиктована відсутністю міри максимальної ваги). Коли настає час пік, особливо о 18:00, то це дуже нагадує евакуацію, а не "розходження по домам" людей =). Так от, часто немає вибору і стаєш у цей привітний ліфт, то він усі 18 поверхів стає, падлюка. Люди в ліфті вже не раз намірялись прибити тих, хто викликає усі ліфти одразу...

Хоча, як на мене, то якраз правильно викликати усі ліфти зразу, але якщо люди заходять у якийсь вже ліфт, який їх повністю забирає, то треба придумати кнопку "скасувати усі інші виклики". Дивно чому її досі немає.

Стосовно найкращого алгоритму, то перше що прийшло в голову:
1. якщо ліфт йде у нашому напрямку і проходить наш поверх, то викликаємо його
2. якщо ви прийшли і бачите, що людей більше, ніж вміщує їх ліфт, то викликайте інший
3. якщо спостерігається зависання ліфта, тобто він не зайнятий, то викликаємо його

7

Re: Практична задача. Стратегія вибору ліфта.

koala написав:

Якщо ліфт іде в якийсь бік, він не реагує на кнопки виклику в інший бік,

мабуть, це правильно, бо забезпечується більша швидкість(все одно та ж людина в інший бік). Щоправда в ліфтах(в яких нема 2 кнопки, тільки одна) можна зустріти, що коли їдеш донизу і не хочеш нікого підбирати, то тримаєш кнопку 1-ого поверху, а ліфт все одно зупиняється на проміжних поверхах(бо його викликали). Ну і аналогічно в звичайних ліфтах - коли хтось їде наприклад на 13-ий поверх, то ліфт не буде тебе підбирати на 9-ому чи 11-ому поверсі(він потім приїде)