Описание метода прямого перебора

Концепция решения задач методом прямого перебора.

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

Алгоритм формирования перестановок на основе упорядоченных пар

Определение 1. Два числа i_k,, i_k₊_l называются упорядоченной парой при условии, что i_k₊_l > i_k.

Определение 2. Первое число упорядоченной пары называется обрывающим числом.

Определение 3. Хвостом перестановки _п из п чисел называется последовательность чисел, начиная с последнего числа до первого обрывающего числа: _п = (i1, i₂, ..., i_k, i_k₊_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 – Блок-схема алгоритма решения задачи

⇐ Предыдущая 123 Следующая ⇒