--PAGE_BREAK--4. Ручной просчёт.
Процесс работы алгоритма с возвратом удобно показать на некотором дереве поиска, которое строится следующим образом. Каждая вершина дерева соответствует некоторому частичному решению. Корнем данного дерева является пустая последовательность. Для построения гамильтоновой цепи поиск будет начинаться с неё. При обходе в глубину посещаются все поддеревья, пока не будет найдена гамильтонова цепь.
Возьмём для примера следующий граф:
0, 1, 2, 3 – вершины графа;
Рёбра графа;
Гамильтонова цепь в графе.
Рис. 1 Граф.
Теперь покажем дерево данного графа:
0312 – гамильтонова цепь
Рис. 2 Дерево графа.
Составим матрицу смежности для данного графа:
v
1
2
3
1
1
1
1
1
1
2
1
3
1
1
0 – если между вершинами нет ребра
1 – если между вершинами есть ребро (или петля)
При расчёте гамильтоновой цепи, программа обращается к графу и работает с ним только посредством матрицы смежности.
Расчёт происходит так: сначала программа создает пустую цепь длиной 4 символа. Создаётся массив куда заносятся элементы матрицы. Берёт первый элементы пути и присваивает ему 0. То есть начинает поиск с нулевой вершины. Просматривает в матрице строку 0, находит значение 1 (есть ребро), проверяет номер столбца «1» и записывает номер столбца в путь, если такого там нет. Записывает неполный путь «01» в список временных путей. Далее поиск ведется в строке «1», находит 1 на пересечении строки «1» и столбца «0» и проверяет была ли такая вершина в пути, была, пропускает, ищет дальше, находит 1 на пересечении строки «1» и столбца «2». Проверка, такой вершины не было, записывает в маршрут (он теперь «012»), записывает неполный маршрут в список временных путей, ищет далее в строке «2». Смотрим: «2» «0» — значение 0, «2» «1» — значение 1 было, «2» «2» — значение 0, «2» «3» — значение 0. Теперь получается что это последняя j-тая вершина (столбец), а ребер больше нет, программа проверяет готова ли цепь. Так как цепь не готова, записывает частичное решение в список временных путей. Делает шаг назад, запоминает последнюю вершину, затем стирает её, и начинает поиск с предыдущей, пропуская текущую. Теперь маршрут снова «01», программа ищет дальше в строке «1», пропуская столбец «2» и находит 1 в следующем столбце «3». Проверяет, такой не было, записывает в путь, записывает неполный путь в список путей. Ищет в строке «3», не находит ничего подходящего, делает шаг назад, и начинает снова поиск со строки «1» столбца «0». Доходит до столбца «2», тут проверка показывает, что в списке неполных путей такой путь уже был. Не записывая повтор, делает шаг назад в пути «01», стирает единицу, запомнив её, и продолжает поиск в строке «0», пропустив столбец «1». Находит 1 в столбце «3» (путь «03»), затем «031», и наконец завершает гамильтонову цепь, найдя «2». Цепь готова: «0312».
5. Описание программы.
Описание программы.
Программа состоит из одного главного окна (рис. 3)
Рис. 3 Главное окно программы.
Как видно из рисунка, программа состоит из трёх блоков:
Входная информация. Здесь можно создать новый граф, указав количество вершин и его имя или загрузить готовые графы, которые записаны в папку с программой в текстовые файлы. Тоже входная информация, а также основной цикл поиска гамильтоновой цепи (кнопка «Построить гамильтонову цепь»). Если создаётся новый граф, то для него вручную вводятся значения наличия или отсутствия (1 или 0 соответственно) рёбер между вершинами. Если выбирается готовый, то эти значения подставляются автоматически. Выходная информация. Здесь выводится весь список временных вершин, а также результат: гамильтонова цепь. Также здесь можно сохранить набранный во втором блоке граф в текстовый файл.
Ограничения программы.
Программа предусматривает действительное наличие гамильтоновой цепи в заданном графе. В случае, если цепи в графе не существует, то программа этого определить не сможет и либо произойдёт зависание программы из-за того что основной поисковый цикл войдёт в бесконечное цикл, либо программа выдаст ошибочный результат. В блоке 2 при ручном вводе значений, допускается ввод только 0 или 1. Другие значения, а также пустая ячейка матрицы смежности приведёт либо к ошибке программы, либо к её зависанию. продолжение
--PAGE_BREAK--