Ответ 1
Эта проблема эквивалентна задаче 2-машинного потока n-job с задачей makepan (n/2/F/C max). алгоритм Джонсона находит точное решение.
Решение Оптимизации (найдите минимальное количество времени, необходимое для того, чтобы все поднимали и опускали горы)
Проблема идет так (перевод):
В нижней части горы есть n (n <= 25000) человек, и каждый хочет подняться, затем вниз по горе. Есть 2 гида: один, помогающий человеку подняться на гору, один из которых помогает человеку спуститься. Человек, я занимаю (i) время, чтобы подняться на эту гору, и вниз (i) время, чтобы спуститься. Тем не менее, каждый гид может помочь только одному человеку за раз (что означает, что максимум 1 человек может подниматься, и максимум 1 человек может спускаться по горам в любой момент времени). Предположим, что, когда верхний гид достигает вершины, он мгновенно телепортируется назад, как с помощью "вниз". Найдите наименьшее время, необходимое для того, чтобы поднять всех и спуститься с горы. (Люди могут собираться на вершине горы, если это необходимо)
Здесь пример ввода для проблемы с аннотациями:
3 persons
person 1: up=6 minutes, down=4 minutes
person 2: up=8 minutes, down=1 minutes
person 3: up=2 minutes, down=3 minutes
Выход на вход:
Минимальное время составляет 17. Это происходит потому, что если человек 3 идет первым, то человек 1, а затем человек 2 (и этот же порядок используется как для восхождения, так и для спуска), это дает общее время 17.
Я пробовал придумать несколько алгоритмов, но вот что у меня до сих пор:
Алгоритм O (n! * n): просто переставьте коров через все возможные перестановки, используя next_permutation
Жадный алгоритм: я отсортировал людей, уменьшив нисходящее время и попытался объединить их, но это не привело к правильному решению.
Другие мысли
Теперь я перехожу к динамическому программированию, так как согласно CLR проблемы оптимизации обычно являются жадным или динамическим программированием (эта проблема, я думаю, удовлетворяет оптимальной субструктуре).
Я заметил, что в минимальном решении руководство "вверх" не будет отдыхать, пока все не встанут на гору. (Таким образом, нет пробелов между лицом 1, восхождение на человека и т.д.). Может быть, проблема может быть сведена к простому сокращению разрывов между временами спуска?
У меня возникли проблемы с представлением состояния для этой проблемы динамического программирования (я не думаю, что это одномерное, потому что я не думаю, что вы можете найти оптимальное решение для человека, просто зная оптимальное решение для i- 1 человек).
Может ли кто-нибудь помочь?
Ответы
Ответ 2
Фактическое время простоя только по убыванию. И, подумав, я думаю, что главная проблема здесь - выбрать первого человека, чтобы подняться, потому что время первого альпиниста - это надежная задержка для нисходящего гида.
Решение может заключаться в том, чтобы выбрать тот, у которого самый низкий up(i) из тех, у кого есть down(i) > up(i), а затем для восхождения вы назначаете приоритет всем с down(i) > up(i), затем down(i) = up(i), а затем все остальные. Для спуска вы просто назначаете приоритет людям с самым длинным вниз (i).
Это достигается:
- Вы задерживаете нисходящую направляющую наименее при запуске.
- Вы постоянно держите его занятым.