p = x*i.
Шаг 5. (i) (Если надо найти лишь путь от s к t) Если p = t, то l(p) является длиной кратчайшего пути.
Останов.
Если , перейти к шагу 2.
(ii) (Если требуется найти пути от s ко всем остальным вершинам). Если вершины отмечены как постоянные, то эти пометки дают длины кратчайших путей. Останов. Если некоторые пометки являются временными, перейти к шагу 2.
Как только длины кратчайших путей от s будут найдены (они будут заключительными значениями пометок вершин), сами пути можно получить при помощи рекурсивной процедуры с использованием соотношения
l(x'i) + c(x'i,xi) = l(xt).
Так как вершина x'i непосредственно предшествует вершине хi
в кратчайшем пути от s к xi, то для любой вершины xi
соответствующую вершину x'i можно найти как одну из оставшихся вершин, для которой
l(x'i) + c(x'i,xi) = l(xt). (3.1)
Если кратчайший путь от s до любой вершины xi является единственным, то дуги (x'i,xi) этого кратчайшего пути образуют ориентированное дерево с корнем s. Если существует несколько
"кратчайших" путей от s к какой-либо другой вершине, то при некоторой фиксированной вершине x'i соотношение (3.1) будет выполняться для более чем одной вершины xi. В этом случае выбор может быть либо произвольным (если нужен какой-то один кратчайший путь между s и xi), либо таким, что рассматриваются все дуги (x'i,xi), входящие в какой-либо из кратчайших путей, и при этом совокупность всех таких дуг образует не ориентированное дерево, а общий граф.
ВЫВОДЫ ПО ТРЕТЬЕЙ ГЛАВЕ.
1. Предложены способы упрощения сетей Петри, позволяющие понижать размерность задачи построения сокращенного графа достижимости за счет представления линейных участков сети макровершинами.
2. Для получения оптимального маршрута в сокращенном графе достижимости разработан алгоритм "обратной волны", позволяющий с использованием знаний о структуре сети Петри системы удалить из весов дуг и вершин полученного маршрута те переходы и позиции, которые не используются для реализации проекта.
3. В качестве критериев априорной оптимизации предложены критерии - память, быстродействие, а для вычислительных процедур
- точность, которые объдинены в интегральный критерий. Отмечено, что все эти критерии являются характеристиками используемых модулей и зависят от типа модулей, моделей и размерностей решаемых задач.
4. Показано, что задача поиска оптимального пути в сокращенном графе достижимости между двумя классами вершин
(класс вершин, покрывающих конечную маркировку Мt и класс вершин, покрываемых начальной маркировкой Мо) сводится к задаче нахождения кратчайшего пути между двумя вершинами.
Глава 4. ПРОГРАММНАЯ СИСТЕМА "ИНТЕЛЛЕКТУАЛЬНЫЙ
ПРОЕКТИРОВЩИК САПР".
На основе предложенных методов интеллектуального управления процессом проектирования была предложена архитектура, и разработаны инструментальные прграммные средства
"Интеллектуальный проектировщик САПР". Программы написаны на языке C++ и рассчитаны на применение на IBM совместимых компьютерах в операционной среде MS DOS.
Разработанный пакет инструментальных средств
"Интеллектуальный проектировщик САПР" был внедрен в практику проектных работ в КБ "Аметист" в составе комплекса инструментальных средств САПР Электронных систем и использован для проектирования реакций биохимического синтеза.
4.1. Архитектура системы автоматизированного проектирования проектов САПР.
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.