Данная диаграмма должна быть проверена с точки зрения возможности получения всех
справок, указанных в техническом задании или показанных на диаграмме потоков данных
разрабатываемой системы (см. рис. 4.14).
4.6. Математические модели задач, разработка
или выбор методов решения
Для задач, алгоритм решения которых не очевиден, используют разного рода математические
модели. Процесс построения такой модели включает:
• анализ условия задачи;
• выбор математических абстракций, адекватно, т. е. с требуемой точностью и полнотой
представляющих исходные данные и результаты;
• формальную постановку задачи;
• определение метода преобразования исходных данных в результат, т. е. метода решения
задачи.
Для многих задач, которые часто встречаются на практике, в математике определены как
модели, так и методы решения. К таким задачам, например, относится большинство задач
аналитической геометрии на плоскости и в пространстве, задачи моделирования дискретных
систем и т. д.
Основная проблема в подобных случаях - обоснование применимости той или иной
математической модели для решения конкретной задачи.
В ряде случаев формальная постановка задачи однозначно определяет метод ее решения, но,
как правило, методов решения существует несколько, и тогда для выбора метода решения может
потребоваться специальное исследование. При выборе метода учитывают:
• особенности данных конкретной задачи, связанные с предметной областью (погрешность,
возможные особые случаи и т. п.);
• требования к результатам (допустимую погрешность);
• характеристики метода (точный или приближенный, погрешности результатов,
вычислительную и емкостную сложности, сложность реализациии т. п.).
Пример 4.8. Выполнить формальную постановку задачи поиска цикла минимальной длины
(задачи коммивояжера).
Вспомним, что задача коммивояжера или поиска цикла минимальной длины в простейшем
варианте формулируется следующим образом. Задан список городов и дорог, соединяющих
данные города. Известны расстояния между городами. Необходимо объехать все города, не
заезжая ни в какой город дважды, и вернуться в исходный город так, чтобы суммарная длина пути
была минимальной.
Анализ условия задачи показывает, что математической моделью объектов системы и
существующих или возможных связей между ними может являться взвешенный ориентированный
или неориентированный граф G(X, <U, L>), где X, U, L - множества вершин, ребер и весов ребер
соответственно.
Для перехода от объектов задачи к их математическим моделям необходимо [55]:
• сформулировать правила соответствия компонентов объекта компонентам модели;
• определить вид этих соответствий (взаимно однозначные, однозначные, многозначные);
• определить способ отображения свойств и характеристик компонентов объекта в
характеристики выбранной математической абстракции.
Все это определяется, исходя из отношений, существующих между компонентами объекта, а
также свойств объекта и характеристик его компонентов.
В графе G множество Э объектов системы (городов) поставлено во взаимно однозначное
соответствие множеству X, а множеству связей С между парами объектов (дорог) поставлено в
такое же соответствие множество ребер U. Расстояние между городами
ji
ээ ,
интерпретируется