close

Вход

Забыли?

вход по аккаунту

?

код для вставки
 1. Разработать алгоритм решения задачи (согласно варианту)
2. Описать структуры данных
3. Реализовать алгоритм на каком-либо языке программирования 4. Оценить временную сложность алгоритма в сравнении с прямым перебором всех вариантов.
5. Дать характеристику использованного метода разработки алгоритма
Задание на лабораторную работу
1. Составление сетевого графика выполнения работ.
Имеется комплекс взаимосвязанных работ N. Для каждой из работ задана трудоемкость выполнения. Имеется К рабочих. Требуется распределить рабочих по операциям таким образом, чтобы длительность выполнения всего комплекса работ была минимальной.
Примечание: не учитываются субъективные факторы, и невозможно перемещение рабочих с одной операции на другую в процессе выполнения.
Комплекс взаимосвязанных работ представляется в виде сетевого графика, где узлы графа - это события окончания предшествующих работ, дуги - работы.
Трудоемкость Ri,j характеризует затраты ресурсов на выполнение работы.
Пример сетевого графика:
L(0, М) - длительность выполнения работы. Эта величина определяется как совокупность возможных путей в графе
В данном примере возможны 3 маршрута:
I1={(0, 1); (1, 3); (3, 5)}
I2={(0, 1); (1, 4); (4, 5)}
I3={(0, 2); (2, 4); (4, 5)}
I1=1+2+4=7 - "критический" путь Iкр.
I2=1+2+1=4
I1=2+3+1=6
Необходимо расставить по операциям заданное число рабочих.
Для случая, когда K=N задача является тривиальной.
Для KN имеется N(K-N) возможных вариантов расстановки.
Пусть N=7, К=10, тогда имеется 1296 вариантов размещения рабочих.
Решение этой задачи методом полного перебора вариантов неэффективно.
Используя метод "Разделяй и властвуй", разбивают исходную задачу на (К-N) последовательных подзадач. Затем решают вопрос о том, на какую операцию поставить 1-го свободного рабочего (для данного примера - 8-го рабочего). После этого размещают 2-го свободного рабочего, взяв за исходное ранее найденное решение и т.д.
Каждая из этих подзадач может быть сформулирована следующим образом: необходимо принять решение о добавлении одного работника на одну из работ комплекса, чтобы полученная расстановка минимизировала "критический" путь
Свободного рабочего размещают на одну из работ, входящих в "критический" путь, желательно, наиболее трудоемкую (здесь - (3, 5)).
Тогда получаем:
I1'=1+2+4/2=5 I3=6 Iкр
L(0, 5)=6
Поиск решения данным алгоритмом требует анализа не более N*(K-N) вариантов.
2. Отсортировать массив из n чисел в порядке возрастания с использованием алгоритма сортировки слиянием.
Описание алгоритма: Книга "Структура данных и алгоритмы" А.В. Ахо и др. С. 313-316.
3. Алгоритм "Ханойская башня";
Описание алгоритма: Книга "Структура данных и алгоритмы" А.В. Ахо и др. С. 275-276.
Документ
Категория
Программирование, Базы данных
Просмотров
10
Размер файла
30 Кб
Теги
1/--страниц
Пожаловаться на содержимое документа