2.10.2. Графические представления в решении задач

Общим методом решения задач является разбиение задачи на подзадачи (метод сведения к подзадачам), которые совместно удовлетворяют требуемым условиям. Задача считается решенной, когда каждая из подзадач в отдельности решена. Однако для решения отдельной подзадачи может быть использовано множество методов, причем каждый из них порождает новую подзадачу.

Рис. 2.17 а. Схема сведения задачи к подзадачам.

Поэтому достаточно решить какую-нибудь одну из этих новых подзадач, чтобы решить и ту подзадачу, которая их породила. Этот процесс имеет типичную древовидную структуру, и в этом случае принято говорить о дереве (оно показано на рис. 2.17 а). Эта схема позволяет наглядно представить процесс эффективного поиска решения человеком или машиной. В предельном случае (идеальном, но редко встречающемся) дерево вырождается в единственную ветвь, и в этом случае поиск становится линейным, без проверок других ветвей. В этом случае говорят об алгоритме.

Представления объектов в виде графов используются, например, в исследовании операций, где рассматриваемые объекты по своей природе являются графами, например в задаче

отыскания оптимального способа доставки почты во Франции, которая связана с наличием реальной почтовой сети. При этом исходными данными задачи являются графы железнодорожной, автомобильной или авиационной связи между селениями.

Рис. 2.17 б. Граф последовательности работ.

Рис. 2.17 в. Граф работ, которые не могут быть выполнены одновременно.

Другим примером может служить задача минимизации общего времени выполнения какого-то множества работ при условии, что наложены ограничения относительно последовательности их выполнения во времени. В этом случае удобно использовать ориентированные графы (например, в методе которые отражают эти ограничения. На рис. 2.17 б представлен граф (51), показывающий, что работа продолжительностью должна быть завершена до того, как начнет выполняться работа На рис. 2.17 в показан граф (52), означающий, что работы являются взаимно исключающими и вместе не могут быть выполнены. Тут проявляется существенное свойство любого математического моделирования: одна и та же модель может представлять различные задачи. Задачи, где присутствуют только ограничения типа (52), эквивалентны задаче о раскраске графа. Задачи, где имеются только ограничения типа (51), эквивалентны отысканию пути максимальной длины на графе.