- •Технология подготовки и решения задач с помощью компьютера
- •Базовые конструкции для написания структурированных программ. Способы обращения неструктурированных программ в структурированные.
- •Ввод и вывод данных, оператор присваивания.
- •Условный оператор: группа If
- •Цикл с параметром: группа For
- •Цикл с параметром: While, Repeat
- •Контрольные вопросы:
- •Пошаговая детализация алгоритма
- •Процедуры и функции
- •Контрольные вопросы.
- •Структуры данных: массивы, строки, записи. Размещение в памяти. Пользовательские типы данных.
- •Контрольные вопросы.
- •Модульное программирование. Организация личных библиотек.
- •Контрольные вопросы:
- •Рекурсивные алгоритмы
- •Контрольные вопросы.
- •Сортировка и поиск. Методы внутренней сортировки.
- •Быстрые алгоритмы сортировки
- •Контрольные вопросы
- •Статистическое и динамическое распределение памяти. Динамические структуры данных.
- •Контрольные вопросы.
- •Алгоритмы с возвращением.
- •Поиск в глубину
- •Поиск в ширину
- •Деревья
- •Достижимость
- •Метод построения максимального потока в сети
- •Метод локальной оптимизации
- •Организация файловой системы. Создание и обработка баз данных.
- •Варианты
- •Контрольные вопросы:
- •Библиотечные модули системы программирования Паскаль: Crt, Dos, Graph.
- •Графический режим работы экрана
- •Основные графические функции и процедуры
- •Контрольные вопросы:
- •Комбинаторные алгоритмы.
- •Перебор с возвратом. Общая схема
- •Задача о рюкзаке (перебор вариантов)
- •Задача о коммивояжере (перебор вариантов)
- •Объектно-ориентированное программирование
Метод локальной оптимизации
Попытаемся отказаться от перебора вариантов, рассмотренного в главе 2. Найдем первое решение (первую оценку), а затем попытаемся улучшить оценку, просматривая только соседние города найденного пути.
Шаг 1. Получить приближенное решение (первую оценку). При этом не следует забывать, что после получения первой оценки предыдущим методом его работа заканчивается.
Шаг 2. Пока происходит улучшение решения, выполнять следующий шаг, иначе перейти на шаг4.
Шаг 3. Для всех пар номеров городов i,j, удовлетворяющих неравенству (1i<jn), проверить:
di-1,i +di,j +dj,j+1 >di-1,j +dj,i +di,j+1 для смежных городов, то есть j=i+1
di-1,i +di,i+1 +dj-1,j +dj,j+1 >di-1,j +dj,i+1 +dj-1,i +di,j+1 для несмежных городов.
Примечание. На рисунке даны графические иллюстрации первого и второго неравенств. “Жирными” линиями обозначены участки старых маршрутов, “тонкими” - новых.
Если одно из неравенств выполняется, то найдено лучшее решение. Следует откорректировать ранее найденное решение и вернуться на шаг 2.
Шаг 4. Закончить работу алгоритма.
Для реализации логики (из рассмотренных в предыдущем алгоритме структур данных) достаточно матрицы расстояний (А) и массива для хранения пути коммивояжера (Way). Вид общей логики:
begin
init;{Ввод из файла матрицы расстояний, инициализация глобальных переменных}
one_way;{Поиск первого варианта пути коммивояжера}
local;{Локальная оптимизация}
out;{Вывод результата}
end.
Примечание. Владение технологиями “сверху вниз” и “снизу вверх” - необходимые составляющие структурной парадигмы мышления.
Procedure local;
var i,j:integer; change:boolean; <здесь функции best1 и best2, а также процедура swap>;
begin
repeat
change:=false;
for i:=1 to n-1 do
for j:=i+1 to n do
if i=j+1 then begin if best1(i,j) then swap(i,j);end
else if (i=1) and (j=n) then begin if best1(i,j) then swap(i,j); end {Об этой проверке лучше первоначально умолчать, чтобы было о чем спросить, «если совсем будет плохо» - все понимают и нет вопросов}
else if best2(i,j) then swap(i,j);
until not(change); end.