ИССЛЕДОВАНИЕ ДЕРЕВА РЕШЕНИЙ В РЕАЛИЗАЦИИ МЕТОДА ВЕТВЕЙ И ГРАНИЦ ДЛЯ РЕШЕНИЯ ЗАДАЧИ КОММИВОЯЖЕРА Ермошин А.С., Плиско В.А. (МГУПИ)

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

3 Процедура ветвления Мы начинаем построение поискового дерева решений с корня, который будет соответствовать множеству «всех возможных туров» Ветви, выходящие из корня, определяются выбором одного ребра

4 Вычисление границ Вычисление нижних границ основной фактор, дающий возможность сокращения перебора в алгоритме

5 Организация дерева решений В предлагаемой реализации узлы дерева решений хранятся в виде несвязанных динамических структур данных; из всего дерева решения хранятся только листья. Каждая структура содержит в себе следующие переменные: вес данного узла массив пути Вес узла 1 Массив пути Вес узла N Массив пути … 1 N ……

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

7 Выбор способа организации массива индексов Вид операции Vector Dynamic Array Доступ к объекту const Вставка нового объекта n Поиск объектаn

8 Выбор способа организации массива индексов Трудоемкость вставки Трудоемкость поиска

9 Выбор следующей вершины в дереве решений 1. Выбор из массива прямым перебором все узлы, имеющие вес такой же, как у первого элемента. Если таких узлов не найдено, то первый узел и является узлом с минимальным весом. 2. Из найденных на первом этапе узлов выбираются те, для которых невозможно дальнейшее ветвление, то есть такие, для которых найден полный путь. Если хотя бы один такой узел найден, то путь, записанный в нем, и является оптимальным. 3. Если же такого не происходит, то выбирается тот узел, который имеет наибольшее количество положительных ребер в массиве пути

10 Демонстрация работы программы Начать демонстрацию Начать демонстрацию

11 Цели исследований: 1. Проанализировать, как изменяются частотная встречаемость количества узлов дерева решений, при заполнении матрицы стоимостей по нормальному и по равномерному закону распределения на разных размерах матриц. 2. Установить зависимость величины среднего количества узлов поискового дерева решений, от размера матрицы стоимостей для задачи коммивояжера методом ветвей и границ.

12 Частотная встречаемость количества узлов в дереве решений

13 Частотная встречаемость количества узлов в дереве решений

14 Изменение частотной встречаемости с ростом размера матрицы

15 Изменение частотной встречаемости с ростом размера матрицы

16 Частотная встречаемость лучшего случая

17 Зависимость среднего значения количества узлов в дереве решений от размера матрицы стоимостей

18 Максимальное, среднее и минимальное кол-во узлов в дереве решений Увеличение разброса