| engineerklub | Дата: Понедельник, 26.12.2022, 17:38 | Сообщение # 1 |
 Генералиссимус
Группа: Администраторы
Сообщений: 28628
Статус: Offline
| Ознакомительная практика. Вариант №29
Тип работы: Практические занятия и отчеты
Форматы файлов: Microsoft Word
Сдано в учебном заведении: СибГУТИ
Описание:
ОТЧЕТ
по ознакомительной практике
УСЛОВИЕ ЗАДАЧИ
Найдите все вершины взвешенного неориентированного графа, к которым существует путь заданной длины от указанной вершины. Каждая вершина должна выводиться один раз.
ОПИСАНИЕ ИСПОЛЬЗУЕМОГО АЛГОРИТМА
Данный класс задач обычно называется бэктрекинг (backtracking) или поиск с возвратом. Идея решения данной задачи: перебрать всевозможные пути без циклов в графе, затем проверить длину каждого пути и, если длина пути удовлетворяет условиям, запомнить путь.
Перебор всех путей осуществляется с помощью модифицированного обхода в глубину. В стандартном алгоритме используется общее для всех ступеней рекурсии множество посещенных вершин. В нашей версии обхода в глубину для каждой ступени рекурсии мы составляем новое множество посещенных вершин, исходя из рекуррентного соотношения: множество посещенных вершин на предыдущем шаге, объединенное с текущей вершиной обхода. Тем самым, мы переберем все возможные пути без циклов.
Остается проверять длину пути на каждом шаге рекурсии и запоминать путь, если путь удовлетворяет заданным условиям.
ЛИСТНИНГ ПРОГРАММЫ
ТЕСТЫ
ЗАПУСК ПРОГРАММЫ
СКАЧАТЬ
|
| |
| |
