neurohamster (neurohamster) wrote in informaticsguru,
neurohamster
neurohamster
informaticsguru

Алгоритм

Народ, нужно придумать контрпример к алгоритму решения задачи или доказательство, что алгоритм дает оптимальное решение.

Исходным заданием было придумать приближенный алгоритм и его оценку для следующей задачи.
Условие:

Есть n процессоров, m программ и 1 сервер. Каждому процессору сопоставлен набор программ характеризуемых двумя параметрами: время исполнения на процессоре и время скачивания программы с сервера.

Необходимо минимизировать время окончания последней программы.

Когда процессор качает программу с сервера он занят и не может выполнять что-то еще.
Сервер одновременно может отдавать только одну программу.

Предлагаемое решение:
Разбиваем задачу на подзадачи:
Выполнить k программ из заданных m за минимальное время.
Очевидно, что при k = m подзадача дает решение первоначальной задачи.

Решаем по индукции.

При k = 1 просто выбираем программу у которой сумма времени скачивания и выполнения минимальна.

При k != 1 берем решение задачи для k = k-1 и пробуем вставить в него до или после уже использованных программ одну из оставшихся. Выбираем решение с минимальным временем исполнения. При равном времени исполнения выбираем решение с наименьшим простоем сервера.

При k = m решение найдено решение исходной задачи.

Проблема в том, что я не уверен, что из оптимальности решения на предыдущем шаге следует оптимальность решения на текущем. Если кто-то сможет это доказать или опровергнуть буду очень благодарен.
  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

  • 0 comments