Лабораторная работа №8 - Исследование интерактивных алгоритмов решения переборных задач на примере задачи поиска гамильтонова цикла или цепи

Цель работы:

1. Получить представление о методах интерактивного решения переборных задач на структурах, когда человек направляет процесс поиска решения, выполняемого компьютером.

2. Изучить метод поиска с возвратом (backtracking) и способы повышения его эффективности, основанные на учёте симметрии структуры.

3. Изучить способ визуализации процесса решения методом поиска с возвратом на диаграмме структуры и дереве решения.

Отчёт:

Гамильтоновой цепью в структуре называется простая цепь, число вершин которой равно числу вершин структуры.

Гамильтоновым циклом в структуре называется простой цикл, число вершин которого равно числу вершин структуры.

Структура, содержащая гамильтонов цикл, называется гамильтоновой.

Структура, не являющаяся гамильтоновой, но у которой любой примарный подграф (структура, полученная из исходной удалением одной вершины) является гамильтоновым, называется гипогамильтоновой.

Поиск с возвратом (backtracking) – стандартный метод построения алгоритмов решения переборных задач. Он позволяет значительно сократить число шагов алгоритма. Главная идея метода поиска с возвратом заключается в попытках последовательного расширения частичного решения, начиная с пустого, и возвращении к более короткому частичному решению при неудаче.