37869

Автор(ы): 

Автор(ов): 

2

Параметры публикации

Тип публикации: 

Статья в журнале/сборнике

Название: 

Resource characteristics of ways to organize a decision tree in the branch-andbound method for the traveling salesmen problem

DOI: 

10.17323/1998-0663.2015.4.38.46.

Наименование источника: 

  • Business Informatics

Обозначение и номер тома: 

№. 4 (34)

Город: 

  • Москва

Издательство: 

  • Национальный исследовательский университет «Высшая школа экономики»

Год издания: 

2015

Страницы: 

38-46
Аннотация
Ресурсная эффективность различных реализаций метода ветвей и границ для классической задачи коммивояжера зависит, в том числе, и от способов организации поискового дерева решений, порождаемого этим методом. Классическая дилемма «время-память» реализуется здесь либо вариантом хранения усечённых матриц в вершинах дерева решений, что приводит к сокращению трудоемкости при дополнительных ёмкостных затратах, либо перевычислением матрицы для текущей вершины, что ведет к увеличению трудоемкости при экономии памяти. Предметом данной статьи является экспериментальное исследование временных характеристик решения задачи коммивояжера методом ветвей и границ с целью определения реального сокращения временных затрат при использовании дополнительной памяти в выбранной структуре хранения дерева решений. Конечной целью исследования является формулировка рекомендаций при реализации метода в практических задачах логистики и бизнес-информатики. В статье на основе полученных экспериментальных данных показано, что оба рассмотренных варианта классического алгоритма решения задачи коммивояжера методом ветвей и границ порождают программные реализации с экспоненциальной зависимостью времени выполнения от длины входа. Экспериментальные результаты позволяют говорить, что возможность использования дополнительной памяти объемом не более 1 Гб приводит к значительному (до 5 раз) сокращению временных затрат. Прогноз по полученному тренду позволяет формулировать рекомендацию по практическому применению программной реализации алгоритма метода ветвей и границ с хранением матриц — при реально доступной оперативной памяти в 16 Гб и при ограничении ожидаемого среднего времени счета порядка одной минуты на современных персональных компьютерах могут быть точно решены задачи размерности не более 70.

Библиографическая ссылка: 

Ульянов М.В., Фомичев М.И. Resource characteristics of ways to organize a decision tree in the branch-andbound method for the traveling salesmen problem // Business Informatics. 2015. №. 4 (34). С. 38-46.