Сетевой научный журнал "Философские проблемы
информационных технологий
и киберпространства" (ISSN:2305-3763)

Адекватность математических моделей на примере задачи коммивояжера // стр. 4

Автор: Макаркин С.Б., Мельников Б.Ф.

Аннотация: В статье рассматривается один из возможных подходов к проблеме адекватности математических моделей – на примере входных данных, использующихся при создании и анализе алгоритмов решения задачи коммивояжера для возникающих на практике частных случаев этой проблемы. Авторы считают, что т.н. псевдогеометрическая версия этой проблемы более адекватно описывает множество ее частных случаев, встречающихся в большинстве предметных областей, чем значительно более распространенная геометрическая версия. Это утверждение обусловливается следующими фактами. В ходе разработки алгоритмов (а также в целях оценки их эффективности) для конкретных предметных областей необходимо принимать во внимание, насколько данные, сгенерированные выбранным методом, репрезентативны для исследуемой предметной области. Как правило, тестовые дан-ные задаются набором случайных величин с заданным распределением. При этом используется некая идеализированная модель входных данных, чаще всего с равномерными или нормальными распределениями значений характеристик. Однако на практике входные данные, как правило, поступают в соответствии с некоторым вероятностным распределением, отличным от равномерного или нормального. В результате производительность алгоритма на реальных данных – причем как в среднем, так и в худшем случае – неадекватна. Самый важный вывод, который хотели бы сделать авторы данной статьи, состоит в следующем. Существуют различные области – как в теоретической информатике, так и в математике, – в которых основные направления исследований, проводимых самыми разными научными группами, в действительности являются мало похожими на реальные задачи, возникающие в различных областях на практике. И «увлечение» многих математиков-программистов последовательным улучшением алгоритмов и программ, предназначенных для решения геометрической версии задачи коммивояжера (вместо псевдогеометрической ее версии), – это один из многих подобных примеров.

Ключевые слова: математическая модель; адекватность; задача коммивояжера; псевдогеометрическая версия.





← Назад в выпуск