neurohamster (neurohamster) wrote in informaticsguru,
neurohamster
neurohamster
informaticsguru

Алгоритм

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

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

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

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

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

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

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

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

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

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

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

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 0 comments