ПОИСК Статьи Рисунки Таблицы Построение оптимальных связывающих сетей из "Моделирование процессов автоматизированного химико - технологического проектирования" Рассмотрим задачу построения эскиза системы транспортировки материальных потоков, т. е. построим связывающую сеть из прямо-дянейных отрезков, являющихся как бы осями прямолинейных участков трубопроводов, при этом не будем учитывать возможность пересечения участков трубопровода с аппаратами. Эскиз системы транспортировки используется на этапах синтеза и оптимизации при размещении аппаратов. Устранение возможных пересечений должно осуществляться на окончательных этапах компоновки. [c.140] Постановка задачи. Имеетсй множество Т точек на плоскости. Требуется связать их сетью прямолинейных отрезков, идущих от точки к точке таким образом, чтобы длина сети была минимальной. Примеры таких сетей ъ Е ш изображены на рис. Г -11. [c.140] Отметим, что в постановку задачи входит запрет на введение дополнительных точек. . [c.140] Сформулированная выше задача была решена Примом [14] и Краскалом [10]. Работа Прима [11] содержит подробное и ясное изложение задачи, всевозможные ее обобщения,и эффективные способы решения. [c.140] Так как нас будет интересовать не только случай евклидовой метрики, то рассмотрим общую задачу в абстрактных терминах теории графов (см. главу П). [c.140] Формулировка задачи. В полном неориентированном графе с весами на ребрах найти дерево, связывающее все ве ршины ж имеющее минимальную сумму весов ребер. [c.140] Минимальное связывающее дерево по Приму в графе обозначим через Др в метрическом пространстве через Д будем обозначать кратчайшее связывающее дерево без дополнительных точек. Введем матрицу М, элемент которой т,-/ является весом ребра (г, /), соединяющего г-ю вершину с /-й. . [c.140] Аналогично ближайшим соседом фрагмента является точка, которая находится от данного фрагмента на расстоянии не большем, чем любая другая точка. [c.141] Как видно из этого описания, выбор действия на каждом шаге далеко не однозначен. Эта неоднозначность позволяет создавать различные алгоритмы, каждый из которых, если он следует правилам 1 и 2, приводит к оптимуму. [c.141] В примере, изображенном на рис. VI-12, следующим шагом может быть соединение точек 1 л 2, или 2 ж 3 по правилу 1), либо присоединение фрагментов к точкам например, фрагмент 5—6 присоединить к точке 8 (по правилу 2). [c.141] Обоснование правил составляет предмет содержательной теоремы, доказательство которой имеется в работе [11]. [c.141] Программа для алгоритма составлена так, что правило 1 применяется только один раз, а затем на каждом таге единственный изолированный фрагмент соединяется с ближайшим соседом. Программа применима к любой матрице М. [c.141] Обоснование возможности применения деревьев Пр для оценки длины кратчайшего связывающего дерева. Покажем вначале, что элементарное дерево (рис. У1-13), в котором источник соединен со всеми стоками непосредственно, не может служить оценкой длины кратчайшего связывающего дерева. [c.142] Пунктиром обозначены ребра, которые могут быть построены на 4-м шаге. [c.142] Вспомогательные построения. При построении оптимальных связываюнщх деревьев расстояние от точки до фрагмента определяется другим способом и соединение точки с фрагментом происходит не с исходным, а с некоторыми дополнительно построенными точками. В двумерном случае соединение точки А с фрагментом А у, Л г) происходит так, как это показано на рис. 1-14. [c.142] Таким образом, чтобы найти I С, Ф), требуется определить рао-бтояние I 1С, и (А , А,)] от точки С до каждого обобщения отрезка и (Л , А/), входящего в Ф, и затем взять минимум. [c.143] Вычисление 1[С, II А, В)] в ж Е . Проведем построение в -мерном случае. Дан отрезок с концами А = а ,. . . ., а ) и В — (вх, вй), точка С = (сх,. . ., Ь ). [c.143] Вернуться к основной статье