Обход графа в ширину

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

Для работы такого алгоритма необходимо поддерживать очередь необработанных вершин (именно очередь, т.к. выбор вместо нее стека превратит наш алгоритм в поиск в глубину). Кроме того, чуть-чуть усложняется восстановление найденного пути — нам известно множество вершин, обрабатываемых на каждом шаге, поэтому чтобы точно восстановить путь, нам придется хранить список использованных дуг.

По алгоритму листинг 2, поиск продолжается пока не будут обработаны все доступные вершины (п. 2), либо не будет найдена нужная вершина (п.4). Функция breadth выбирает вершину из начала очереди обработки (п.3), и добавляет новые в конец (п.8) — за счет этого обеспечивается требуемый порядок обхода — чем более узел удален от стартовой вершины — тем позже он будет обработан. Для устранения зацикливания алгоритма, в очередь добавляются только вершины, которые не были обработаны или добавлены в очередь обработки на предыдущих шагах (п.6).

Приведенный алгоритм возвращает не путь, а список дуг, по которому можно восстановить кратчайшие пути между стартовой и всеми обработанными вершинами

46. Перечислите шаги алгоритма Дейкстры

Алгори́тм Де́йкстры (англ. Dijkstra’s algorithm) — алгоритм на графах, изобретённый нидерландским ученым Э. Дейкстрой в 1959 году. Находит кратчайшее расстояние от одной из вершин графа до всех остальных. Алгоритм работает только для графов без рёбер отрицательного веса. Алгоритм широко применяется в программировании и технологиях. Пусть требуется найти кратчайшие расстояния от 1-й вершины до всех остальных.

Первый шаг. Рассмотрим шаг алгоритма Дейкстры для нашего примера. Минимальную метку имеет вершина 1. Её соседями являются вершины 2, 3 и 6.

Первый по очереди сосед вершины 1 — вершина 2, потому что длина пути до неё минимальна. Длина пути в неё через вершину 1 равна сумме кратчайшего расстояния до вершины 1, значению её метки, и длины ребра, идущего из 1-й в 2-ю, то есть 0 + 7 = 7. Это меньше текущей метки вершины 2, бесконечности, поэтому новая метка 2-й вершины равна 7. Все соседи вершины 1 проверены. Текущее минимальное расстояние до вершины 1 считается окончательным и пересмотру не подлежит (то, что это действительно так, впервые доказал Э. Дейкстра). Вычеркнем её из графа, чтобы отметить, что эта вершина посещена.

Второй шаг. Шаг алгоритма повторяется. Снова находим «ближайшую» из непосещенных вершин. Это вершина 2 с меткой 7.

Дальнейшие шаги. Повторяем шаг алгоритма для оставшихся вершин. Это будут вершины 6, 4 и 5, соответственно порядку.

Завершение выполнения алгоритма. Алгоритм заканчивает работу, когда нельзя больше обработать ни одной вершины. В данном примере все вершины зачеркнуты, однако ошибочно полагать, что так будет в любом примере - некоторые вершины могут остаться незачеркнутыми, если до них нельзя добраться.

49. Основные компоненты параметризованного синтеза в системах

Структурно-параметрический синтез – это процесс, в результате которого определяется структура объекта и находятся значения параметров составляющих ее элементов, таким образом, чтобы были удовлетворены условия задания на синтез (технического задания). В процессе структурно-параметрическом синтеза изменяются как параметры объекта, так и его структура.

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