Информатика. 11 класс. Поляков К.Ю. § 6. Модели и моделирование
К какому типу можно отнести модель, построенную при решении задачи с путешественником? Обоснуйте ответ.
Ответ
Задача коммивояжёра (или путешественника) относится к классу задач оптимизации, где необходимо найти кратчайший маршрут, проходящий через все заданные точки (города) ровно один раз и возвращающийся в исходную точку. Модель, построенная для решения этой задачи, является графовой моделью.
Обоснование:
- Граф: В задаче коммивояжёра города представляются вершинами графа, а пути между городами — рёбрами графа с соответствующими весами (например, расстоянием или стоимостью перемещения). Задача сводится к поиску гамильтонова цикла минимальной длины в этом графе.
- Математическое представление: Задача коммивояжёра может быть математически сформулирована с использованием матриц смежности или весовых матриц, где каждая строка и столбец представляют город, а элементы матрицы — расстояние между этими городами. Это также указывает на табличное представление данных.
Таким образом, графовая модель описывает задачу с коммивояжёром через структуру данных «граф», что позволяет применять методы теории графов и алгоритмы для поиска оптимального решения.