@ARTICLE{26583204_174187300_2015, author = {М. В. Ульянов and М. И. Фомичев}, keywords = {, задача коммивояжера, метод ветвей и границ, временная и емкостная эффективность, структуры данныхэкспериментальное исследование}, title = {

Ресурсные характеристики способов организации дерева решений в методе ветвей и границ для задачи коммивояжера

}, journal = {Бизнес-информатика}, year = {2015}, number = {4 (34)}, pages = {38-46}, url = {https://bijournal.hse.ru/2015--4 (34)/174187300.html}, publisher = {}, abstract = {Ульянов Михаил Васильевич - доктор технических наук, профессор, ведущий научный сотрудник, Институт проблем управления им. В.А.Трапезникова РАН; профессор департамента программной инженерии, Национальный исследовательский университет «Высшая школа экономики».  Адрес: 117997, г. Москва, ул. Профсоюзная, д. 65.E-mail: muljanov@mail.ruФомичев Михаил Игоревич - студент бакалавриата образовательной программы «Программная инженерия», Национальный исследовательский университет «Высшая школа экономики». Адрес: 101000, г. Москва, ул. Мясницкая, д. 20.E-mail: mikhail.fomichev94@gmail.com      Ресурсная эффективность различных реализаций метода ветвей и границ для классической задачи коммивояжера зависит, в том числе, от способов организации поискового дерева решений, порождаемого этим методом. Классическая дилемма «время-память» реализуется здесь либо вариантом хранения усеченных матриц в вершинах дерева решений, что приводит к сокращению трудоемкости при дополнительных емкостных затратах, либо перевычислением матрицы для текущей вершины, что ведет к увеличению трудоемкости при экономии памяти. Предметом данной статьи является экспериментальное исследование временных характеристик решения задачи коммивояжера методом ветвей и границ с целью определения реального сокращения временных затрат при использовании дополнительной памяти в выбранной структуре хранения дерева решений. Конечной целью исследования является формулировка рекомендаций для реализации метода в практических задачах логистики и бизнес-информатики.      В статье на основе полученных экспериментальных данных показано, что оба рассмотренных варианта классического алгоритма решения задачи коммивояжера методом ветвей и границ порождают программные реализации с экспоненциальной зависимостью времени выполнения от длины входа. Экспериментальные результаты позволяют говорить, что возможность использования дополнительной памяти объемом не более 1 Гб приводит к значительному (до пяти раз) сокращению временных затрат. Прогноз по полученному тренду позволяет сформулировать рекомендацию по практическому применению программной реализации алгоритма метода ветвей и границ с хранением матриц - при реально доступной оперативной памяти в 16 Гб и при ограничении ожидаемого среднего времени счета порядка одной минуты на современных персональных компьютерах могут быть точно решены задачи размерности не более 70. }, annote = {Ульянов Михаил Васильевич - доктор технических наук, профессор, ведущий научный сотрудник, Институт проблем управления им. В.А.Трапезникова РАН; профессор департамента программной инженерии, Национальный исследовательский университет «Высшая школа экономики».  Адрес: 117997, г. Москва, ул. Профсоюзная, д. 65.E-mail: muljanov@mail.ruФомичев Михаил Игоревич - студент бакалавриата образовательной программы «Программная инженерия», Национальный исследовательский университет «Высшая школа экономики». Адрес: 101000, г. Москва, ул. Мясницкая, д. 20.E-mail: mikhail.fomichev94@gmail.com      Ресурсная эффективность различных реализаций метода ветвей и границ для классической задачи коммивояжера зависит, в том числе, от способов организации поискового дерева решений, порождаемого этим методом. Классическая дилемма «время-память» реализуется здесь либо вариантом хранения усеченных матриц в вершинах дерева решений, что приводит к сокращению трудоемкости при дополнительных емкостных затратах, либо перевычислением матрицы для текущей вершины, что ведет к увеличению трудоемкости при экономии памяти. Предметом данной статьи является экспериментальное исследование временных характеристик решения задачи коммивояжера методом ветвей и границ с целью определения реального сокращения временных затрат при использовании дополнительной памяти в выбранной структуре хранения дерева решений. Конечной целью исследования является формулировка рекомендаций для реализации метода в практических задачах логистики и бизнес-информатики.      В статье на основе полученных экспериментальных данных показано, что оба рассмотренных варианта классического алгоритма решения задачи коммивояжера методом ветвей и границ порождают программные реализации с экспоненциальной зависимостью времени выполнения от длины входа. Экспериментальные результаты позволяют говорить, что возможность использования дополнительной памяти объемом не более 1 Гб приводит к значительному (до пяти раз) сокращению временных затрат. Прогноз по полученному тренду позволяет сформулировать рекомендацию по практическому применению программной реализации алгоритма метода ветвей и границ с хранением матриц - при реально доступной оперативной памяти в 16 Гб и при ограничении ожидаемого среднего времени счета порядка одной минуты на современных персональных компьютерах могут быть точно решены задачи размерности не более 70. } }