Концепция решения задач методом прямого перебора.
Этот метод предполагает генерацию множества возможных решений, вычисление целевой функции для каждого из решений и выбор решения, имеющего минимальное значение целевой функции. Элементами решения являются: перестановки, сочетания, размещения, либо иные комбинаторные упорядочения элементов. Трудоемкость генерации вариантов резко возрастает при увеличении размерности задачи, поэтому этот метод в основном используется либо в сочетании с другими методами, либо для проверки точности эвристических методов для малой размерности задачи планирования. Основная сложность при реализации этого метода состоит в генерации множества перестановок, сочетаний и размещений.
Алгоритм формирования перестановок на основе упорядоченных пар
Определение 1. Два числа ik,,ik+l называются упорядоченной парой при условии, что ik+l > ik.
Определение 2. Первое число упорядоченной пары называется обрывающим числом.
Определение 3. Хвостом перестановки п из п чисел называется последовательность чисел, начиная с последнего числа до первого обрывающего числа: п = (i1, i2, ..., ik, ik+l, ..., i„). Собственно обрывающее число в хвост перестановки не включается.
Шаг 1. Формируется первоначальная перестановка из п чисел = (l, 2, 3, ..., п)и пересылается в банк сгенерированных перестановок.
Шаг 2.В перестановке находится хвост, в нем определяется минимальное число, но большее, чем обрывающее число.
Шаг 3.Найденные минимальное и обрывающее числа переставляются местами.
Шаг 4.Полученный хвост упорядочивается в порядке возрастания чисел. После упорядочения результат направляется в банк сгенерированных перестановок. Производится проверка: все ли перестановки сгенерированы. Если не все, то переход на шаг 2. Исходными данными для шага 2 являются результаты, полученные на шаге 4.
Замечание.Минимальное число, найденное в хвосте перестановки, должно быть больше, чем обрывающее число. Если это условие не выполняется, то происходит поиск следующего по возрастанию числа.
Проектирование сценария диалога
В итоговой программной реализации необходимо предусмотреть следующие возможности:
1) Ввод и редактирование количества городов;
2) Ввод и редактирование матрицы расстояний;
3) Вывод оптимального значения пути для посещаемых городов;
4) Вывод последовательности посещения городов.
Описание структур данных
Для создания качественного программного обеспечения необходимо детально разработать все структуры данных, применяемые в ходе решения задачи. Для хранения матрицы расстояний была создана структура Matrix, её поля представлены в таблице 1.
Таблица 1- Описание структуры Matrix
Поле | Тип | Назначение |
C | int ** | Массив расстояний между городами |
Fn | char[13] | Имя файла в котором сохраняется матрица |
S | char | Флаг показывающий сохранялась ли матрица в файле |
Для хранения информации о всех подмножествах была создана структура CitiesSet . Все поля структуры описаны в таблице 2.
Таблица 2 - Описание структуры CitiesSet
Поле | Тип | Назначение |
Ksi | int | Нижняя оценка множества |
Cps_num | unsigned int | Количество пройденных городов |
r,m | unsigned int | Перспективная пара для текущего подмножества |
CM | Matrix | Матрица расстояний между городами для текущего подмножества |
СС | Couple | Матрица пройденного пути |
Для хранения информации о пройденном пути была создана структура Couple. Все поля структуры описаны в Таблице 3.
Таблица 3 – Описание структуры Couple
Поле | Тип | Назначение | Обозначение на схеме |
Sc, jk | int | Счётчик циклов | Sc, jk |
MatrRast | double* | Матрица расстояний | MR |
KolGor | int | Количество городов | KolGor |
MasStep | Step * | Массив структур, содержащих все шаги расчётов | MS |
TempMas | int * | Массив оптимального посещения городов | TempMas |
AllVal | double | Итоговый путь | AllVal |
CurVal | double | Значение из матрицы расстояний | CurVal |
BackVal | double | Путь на предыдущем шаге | BackVal |
Ниже, на рис. 4 представлена блок-схема алгоритма решения задачи методом Литла.
.
Рис. 4 – Блок-схема алгоритма решения задачи