Алгоритмы метода перебора с возвратами - (МПВ), жадные алгоритмы

Цель работы: Изучение алгоритмов метода поиска с возвратами на примерах реализации шахматных задач и задачи динамического программирования. Освоение "жадных" алгоритмов- точного и приближенного.

 

Домашнее задание:

1 Изучить алгоритм метода поиска с возвратами.

2 Изучить алгоритм нахождения критического пути в задаче динамического программирования.

3 Освоить принципы построения "жадных" алгоритмов.

 

 

Порядок выполнения работы.

 

1. Открыть проект Delphi Structures.

2. Добавить в управляющее главное меню пункт «Лабораторная работа №7», при выборе которого должно появляться окно модуля «Poisk_with_back» (модуль Poisk_with_back» с формой добавить в проект).

3. Установить на форму модуля Poisk_with_back компоненты, обеспечивающие ввод исходных данных, управляющую кнопку (класса TButton или TBitBtn) и компоненты для вывода результатов на экране в соответствии с вариантом задания таблицы №2.1.

4. В обработчике события onClick управляющей кнопки на языке

5. Object Pascal написать фрагмент программы для реализации алгоритма в соответствии с вариантом.

6. Отладить обработчик на тестовых примерах и продемонстрировать работу приложения преподавателю.

7. произвести анализ запрограммированного алгоритма (по количеству сравнений).

8. Составить отчет и защитить работу преподавателю. В отчете обязательно представить блок-схему алгоритма решения задачи.

 

Таблица 7.1

№ вар.	Текст задачи
1.	Написать и отладить программу, реализующую решение задачи о "безопасном" размещении к ферзей (к<=8) на шахматной доске. Найти одно решение и отобразить его графически на форме приложения. Для нахождения " безопасного " размещения ферзей использовать метод поиска с возвратами.
2.	Написать и отладить программу, реализующую решение задачи о "безопасном" размещении 8 ферзей на шахматной доске. Найти все возможные решения и отобразить первое решение графически на форме приложения. Все найденные решения сохранить в файле. Для нахождения " безопасного " размещения ферзей использовать метод поиска с возвратами.
3.	Используя перечень номиналов ассигнаций: Const Nominal: array[0..5] of currency= (5000, 1000, 500, 100, 50, 10);, запрограммировать "жадный" алгоритм формирования выдачи заданной суммы в банкомате. Организовать сервис- диалог с заказчиком суммы и учесть в программе возможность отсутствия ассигнаций того или иного номинала.
4.	Используя перечень номиналов ассигнаций и монет: Const Nominal: array[0..10] of currency= (5000, 1000, 500, 100, 50, 10, 5, 1, 0.5, 0.1);, запрограммировать "жадный" алгоритм формирования заданной сдачи кассиром. Общее число купюр и монет в сдаче должно получиться минимальным. Организовать сервис- диалог с кассиром для выяснения обстоятельств наличия номиналов в кассе и учесть в программе возможность отсутствия ассигнаций того или иного номинала.
5.	Используя метод "жадных" алгоритмов, реализовать решение задачи "о рюкзаке ограниченного объема", если заданы величины: V--ограничение объема рюкзака, N-- количество предметов заданного объема q[i] и стоимости c[i]. Программа должна выбрать подмножество предметов, вмещающихся в рюкзак и имеющих наибольшую общую стоимость.
6.	Пусть имеется решетка для описания последовательности работ: узлы в решетке пронумерованы формально:     Рис.1   Длительность каждой работы указана возле направленной дуги. Написать и отладить программу нахождения времени окончания строительства, если решетка моделирует график работы и длительность (вес дуг).
7.	Написать и отладить программу нахождения критического пути для заданной модели-решетки (Рис.1).

 

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

 

1. Суть алгоритма метода поиска с возвратами.(МПВ).

2. Что такое 'тупик' в МПВ и как выйти из тупиковой ситуации в этом алгоритме?

3. Почему стек является непременным аксессуаром в алгоритме МПВ?

4. Сформулируйте задачу динамического программирования.

5. Опишите модель задачи динамического программирования.

6. Дайте понятие критического пути.

7. Что такое топологический порядок выбора узлов?

8. Каков механизм нахождения критического пути, если найдено время окончания работ(строительства)?

 

Лабораторная работа № 8