Материал: АиСД. Практикум (in dev)

    Всего имеется четыре возможности: 1) B=1 и gi=0 2) B=0 и gi=1 3) B=1 и gi=0 4) B=1 и gi=1     Ясно что вершина j не простреливается – в случаях 2 и 3 (при нечетном В+g).     Теперь можно построить сеть.

После того как сеть построена, можно приступать к нахождению кратчайших путей, воспользовавшись любым из выше рассмотренных алгоритмов (в зависимости от поставленной задачи).

55. Алгоритмы составления расписания.

Предположим, что имеется множество n одинаковых процессоров, обозначенных , и m независимых заданий , которые нужно выполнить. Процессоры могут работать одновременно, и любое задание можно выполнять на любом процессоре. Если задание загружено в процессор, оно остается там до конца обработки. Время обработки задания известно и равно Организовать обработку заданий таким образом, чтобы выполнение всего набора заданий было завершено как можно быстрее.

Система работает следующим образом: первый освободившийся процессор берет из списка следующее задание. Если одновременно освобождаются два или более процессоров, то выполнять очередное задание из списка будет процессор с наименьшим номером.

Пример. Пусть имеется три процессора и шесть заданий , время выполнения каждого из которых равно:

Рассмотрим расписание В начальный момент времени T=0, процессорначинает обработку задания , процессор - задания , а процессор- задания . Процессор заканчивает выполнение задания в момент времени и начинает обрабатывать задание , пока процессоры и все еще работают над своими первоначальными заданиями. При T=3 процессор опять заканчивает задание и начинает обрабатывать задание , которое завершается в момент T=4. Тогда он начинает выполнять последнее задание . Процессоры и заканчивают задания при T=5, но, так как список L пуст, они останавливаются. Процессор завершает выполнение задания при T=12. Рассмотренное расписание проиллюстрировано на рис.1. временной диаграммой, известной как схема Ганта. Очевидно, что расписание не оптимально. Можно «подобрать», например, расписание , которое позволяет завершить все задания за T* = 8 единиц времени (рис.2.).

Теперь рассмотрим другой тип задач по составлению расписания для многопроцессорных систем. Вместо вопроса о быстрейшем завершении набора заданий фиксированным числом процессоров теперь поставим вопрос о минимальном числе процессоров, необходимых для завершения данного набора заданий за фиксированное время . Конечно, время будет не меньше времени выполнения самого трудоемкого задания.

В такой постановке задача составления расписания эквивалентна следующей задаче упаковки. Пусть каждому процессору соответствует ящик размера . Пусть каждому заданию соответствует предмет размера , равного времени выполнения задания , где Теперь для решения задачи по составлению расписания нужно построить алгоритм, позволяющий разместить все предметы в минимальном количестве ящиков. Конечно, нельзя заполнять ящики сверх их объема , и предметы нельзя дробить на части.

56. Литература

1. Т. Кормен, Ч. Лейзерсон, Р. Ривест

Алгоритмы: построение и анализ. М.: МЦНМО, 2000.

2. Д.Кнут Искусство программирования , том 1. Основные алгоритмы. Уч . пос. М.:Изд. Дом " Вильямс ", 2000.

3. Вирт Н. Алгоритмы и структуры данных.: Пер. С англ. - М.: Мир, 2001.

4. Хусаинов Б.С. Структуры и алгоритмы обработки данных. Примеры на

языке Си. Учеб. пособие. М : Финансы и статистика, 2004.

5. А. Ахо, Дж.Хопкрофт, Дж.Ульман, Структуры данных и алгоритмы М: СПб: Киев: Вильямс, 2001г.

57. Лабораторное задание.

Для выполнения лабораторной работы необходимо:

1) Ознакомиться с эвристическими алгоритмами.

2) Осуществить трассировку элементов интегральных схем, размером 10х10, 20х20, 30х30. Зафиксировать параметры трассировок всеми рассмотренными методами.

Системы работает в диалоговом режиме с использованием «меню». Вся необходимая поясняющая информация отображается во время работы системы на экране монитора.

3) Составить оптимальное расписание работы четырех процессоров, для которых известно t_{1, … ,} t_11.

4) Составить алгоритм оптимальной упаковки 12 предметов , размером от1 до 4 в ящики размером 6.

5) Составить программу эвристического алгоритма ( по заданию преподавателя)

58. Требования к отчету

Отчет должен содержать:

5. Конспект лабораторной работы;

6. Схемы волнового и лучевых алгоритмов;

7. Результаты выполнения работы;

8. Выводы по работе.

Контрольные вопросы

6. Какова теоретическая сложность алгоритмов, рассмотренных в данной работе?

7. Особенности работы волнового, лучевых и маршрутного алгоритмов?

8. Принципы составления оптимального расписания работы параллельных процессоров?

9. В чем особенности задачи упаковки?

10. Принципы решения задачи о джипе?

6) Как построить дерево решений в задаче о кодовом замке?

59. Решение задач

Пример 1. Найти выход из произвольной точки лабиринта в саду Хемптон Корт. Отождествив коридоры лабиринта с ребрами, а перекрестки, тупики, входы и выходы - с вершинами, перейти к связному графу, представляющему схему лабиринта.

Пример 2. Нарисуйте граф, соответствующий лабиринту. Найдите путь, по которому можно пройти от пункта А до В лабиринта, используя предложенные выше алгоритмы.

Пример 3. ( Задача о джипе ). Пусть необходимо пересечь на джипе 1000 -километровую пустыню, израсходовав при этом минимум горючего. Объем топливного бака джипа 500 литров, горючее расходуются равномерно, по одному литру на километр. При этом в точке старта имеется неограниченный резервуар с топливом. Так как в пустыне нет складов с горючим, необходимо установить собственные хранилища и наполнять их топливом из бака машины. Конечно, проще было бы ехать на грузовике, загруженным бочками с бензином, но тогда не было бы задачи о джипе.

Итак, идея задачи ясна: нужно из точки старта отъезжать с полным баком на некоторое расстояние, устраивать там первый склад, оставлять там какое-то количество горючего из бака, но такое, чтобы хватило вернуться назад. В точке старта вновь производится полная заправка и делается попытка второй склад продвинуть в пустыню дальше. Но где обустраивать эти склады и сколько горючего оставлять в каждом из них?

Пример 4. ( Задача о кодовом замке ). Пусть кодовый замок состоит из набора N переключателей, каждый из которых может быть в положении “вкл” или “выкл”. Замок открывается только при одном наборе положений переключателей, из которых не менее [N/2] (целая часть от N/2) , находятся в положении “вкл”. Построить алгоритм перебора комбинаций, чтобы не пропустить нужную и не набирать ту, которая заведомо к успеху не приведет.

Промоделируем каждую возможную комбинацию вектором из N нулей и единиц. На i-м месте будет 1, если i-й переключатель находится в положении “вкл” и 0, если i-й переключатель - в положении “выкл”. Множество всех возможных N-векторов моделируется с помощью бинарного (или двоичного) дерева. Если количество переключателей в замке равно N, то в дереве просмотра будет N уровней. Решить задачу для для N=4.

89