Задача минимизации длин проводников 11

Скачать 315.37 Kb.

Название	Задача минимизации длин проводников 11
страница	5/8
Дата публикации	11.06.2014
Размер	315.37 Kb.
Тип	Задача

literature-edu.ru > Астрономия > Задача

1 2 3 4 5 6 7 8

Анализ критического пути.

Следующим шагом после построения графа ограничений является определение длиннейшего (критического) пути в графе. Основная цель одномерного сжатия - уменьшить размер топологии в направлении сжатия. Задача определения минимального размера эквивалентна задаче нахождения длиннейшего пути в граф. Если вершину Source поставить в нулевую точку, то величина длиннейшего пути от Source до некоторой вершины и будет ее минимально возможной координатой. Множество ребер, которые определяют минимальное расстояние между вершинами Source и Sink, формируют критический путь, а вершины и ребра данного пути называются критическими.

Вершины, которые не являются критическими, могут перемещаться в пределах некоторого интервала, не увеличивая размер топологии. Данный интервал называется Slack. Положение таких вершин может выбираться исходя из других критериев, таких как минимизация длины проводов, повышение выхода годных и т.д.

Положительные циклы.

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

Рис. 10 Пример положительного цикла.

На Рис. 10 a) показан пример топологии, которая порождает положительный цикл в графе ограничений. Если между объектами А и В минимальное расстояние Sp_AB=2 и А - жесткий объект, то и представляет ребро АВ длиной 3. С другой стороны и представляет ребро ВА длиной -1. Таким образом, получается положительный цикл длиной 2.

Анализируя публикации, можно выделить следующие методы борьбы с циклами:

Так называемая "заморозка". Все элементы топологии, образующие циклы, рассматриваются, как неподвижные относительно друг друга в процессе сжатия и представлены одной вершиной в графе ограничений. Данные элементы помечаются в сжатой топологии для решения конфликта пользователем.
Уменьшение длины ограничений в соответствии с их приоритетом. Обычно корректируется длина ограничений связности. Длина ограничения уменьшается на длину цикла и данное место в топологии помечается стрелкой для информирования пользователя.
Добавление излома на некоторый проводник, который приводит к разбиению соответствующей вершины цикла на две новые, не имеющих ограничений между собой.

Алгоритмы удаления положительных циклов имеют большое значение для сжатия.

Оптимизации.

Все объекты топологии, которые не принадлежат критическому пути, имеют некоторый диапазон координат, который могут принимать объекты, не нарушив при этом ни одного правила. Наличие данного диапазона будем называть слеком ( slack). Именно наличие слеков позволяет нам проводить некоторые оптимизации.

Математически оптимизация представляет собой решение системы неравенств вида (1.1) с учетом некоторой целевой функции. Известно, что решая набор неравенств можно получить некоторую область в n-мерного пространства, где n – это количество переменных в системе неравенств. Если же задать целевую функцию на данной области решений, то можно получить единственно решение, бесконечно много решений или ни одного решения. Система неравенств с заданной целевой функцией представляет собой задачу линейного программирования. В общем виде она выглядит так:

(4)

Ярким примером оптимизации является задача минимизации длин проводников

1 2 3 4 5 6 7 8

Похожие:

	Задача минимизации длин проводников 11 В данной работе я предлагаю модель, основанную на задаче линейного программирования, решение которой позволяет получить топологию...		Задача этой брошюры не описать идеологию Движения. Ее задача разъяснить... Техническим директорам, лидерам регионов и региональным руководителям Идеологического направления
	Методика выбора монтажного крана Задача № Выбор монтажного крана... Практикум предназначен для студентов направления (специальности) Строительство. Он является одним из модулей эумк по дисциплине «Строительные...		Программа курса внеурочной деятельности Авторы: Сашина нв, учитель... Задача семьи состоит в том, чтобы вовремя увидеть, разглядеть способности ребенка. Задача школы – поддержать ребенка и развить его...
	В широком смысле информационной системой можно назвать любую организационную... В широком смысле информационной системой можно назвать любую организационную структуру, задача которой состоит в работе с информацией....		Задача для WireMinimization 4 Расстояния в шаблоне, сохранение которых приводит к сохранению пропорциональности 7
	Задача: Придать интерьеру оригинальность Государственное бюджетное общеобразовательное учреждение средняя общеобразовательная школа №315		Симатова Лаззат Куанышовна Задача: Расширение кругозора знаний у детей. Привит интерес к урокам русского языка и литературы
	Задача оздоровления Анализ итогов прошедшего учебного года. Задачи и приоритетные направления работы на новый учебный год		Задача учителя в современном мире научить ребят самостоятельно приобретать... Задача учителя в современном мире – научить ребят самостоятельно приобретать знания, применять их на практике, работать с различными...

Литература