|
|
На основании алгоритма Флойда охарактеризуйте общий шаг решения задачи.Общий шаг k. На каждом k-ом шаге производится пересчет элементов матрицы D (кроме dik и dki): dij=min(dij, dik+dkj) 1. Если dik+dkj<dij, то qij=k; 2. Если выполняется неравенство dik+dkj>dij, то элемент qij матрицы Q – не меняется 4. Выделите кратчайшие пути между вершинами графа, представленного на рисунке:
Вопрос 11 Назовите, в чем заключается конкретный смысл алгоритма Дейкстры. Находит кратчайшее расстояние от одной из вершин графа до всех остальных. Алгоритм работает только для графов без ребер отрицательного веса. Сформулируйте основное условие алгоритма Дейкстры. Дан взвешенный ориентированный граф G (V, E) без петель и дуг отрицательного веса. Найти кратчайшие пути от некоторой вершины а графа G до всех остальных вершин этого графа. 3. Составьте условия для двух задач с использованием алгоритма Дейкстры на примере: - автомобильных дорог, - авиарейсов между городами. 1) Дана сеть автомобильных дорог, соединяющих города области. Некоторые дороги односторонние. Найти кратчайшие пути от главного города до каждого города области. 2) Имеется некоторое количество авиарейсов между городами мира, для каждого известна стоимость. Стоимость перелета из А в B может быть не равна стоимости перелета из B в А. Найти маршрут минимальной стоимости (возможно, с пересадками) от Копенгагена до Барнаула. Выделите основные шаги алгоритма Дейкстры с использованием меток. Инициализация. Метка самой вершины а полагается равной 0, метки остальных вершин – бесконечности. Это отражает то, что расстояния от а до других вершин пока неизвестны. Шаг алгоритма. Если все вершины посещены, алгоритм завершается. В противном случае, из еще непосещенных вершин выбирается вершина u, имеющая минимальную метку. Мы рассматриваем всевозможные маршруты, в которых u является предпоследним пунктом. Для каждого соседа вершины u, кроме отмеченных как посещенные, рассмотрим новую длину пути, равную сумме значений текущей метки u и длины ребра, соединяющего u с этим соседом. Если полученное значение меньше значения метки соседа, заменим значение метки полученным значением длинны. Рассмотрев всех соседей, пометим вершину u как посещенную и повторим шаг алгоритма. Вопрос 12 1. Назовите методы построения первоначального опорного плана транспортной задачи. -метод «северо-западного» угла -метод наименьшей стоимости - метод Фогеля Опишите, в чем заключается отличие метода северо-западного угла от метода наименьшего элемента. В методе минимального элемента учитываются затраты на перевозку, поэтому исходный план позволяет обеспечить суммарную стоимость перевозок, более близкую к оптимальной, чем при методе СЗ угла Охарактеризуйте метод наименьшей стоимости. При этом методе на каждом шаге построения опорного плана первою заполняется та клетка оставшейся части таблицы, которая имеет наименьший тариф. Если такая клетка не единственная, то заполняется любая из них. Затем из рассмотрения исключают либо строку, соответствующую поставщику, запасы которого полностью израсходованы, либо столбец, соответствующий потребителю, потребности которого полностью удовлетворены, либо и строку, и столбец, если израсходованы запасы поставщика и удовлетворены потребности потребителя. Из оставшейся части таблицы стоимостей снова выбирают наименьшую стоимость, и процесс размещения запасов продолжают, пока все запасы не будут распределены, а потребности удовлетворены. Смоделируйте алгоритм решения методом наименьшего элемента на примере задачи с двумя поставщиками и двумя потребителями. 1 2 Запасы 1 1 2 10 2 3 4 15 Потребности 5 20
1 2 Запасы 1 1(min) 2 10 2 3 4 15 Потребности 5 20
1 2 Запасы 1 1(5) 2 5 2 3 4 15 Потребности 5 20
Вопрос 13 1. Назовите, что представляет собой план выполнения комплекса взаимосвязанных задач. Сетевая модель   Живите по правилу: МАЛО ЛИ ЧТО НА СВЕТЕ СУЩЕСТВУЕТ? Я неслучайно подчеркиваю, что место в голове ограничено, а информации вокруг много, и что ваше право...  ЧТО ТАКОЕ УВЕРЕННОЕ ПОВЕДЕНИЕ В МЕЖЛИЧНОСТНЫХ ОТНОШЕНИЯХ? Исторически существует три основных модели различий, существующих между...  Что вызывает тренды на фондовых и товарных рынках Объяснение теории грузового поезда Первые 17 лет моих рыночных исследований сводились к попыткам вычислить, когда этот...  Система охраняемых территорий в США Изучение особо охраняемых природных территорий(ООПТ) США представляет особый интерес по многим причинам... Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте:
|
