Методы локальной пользовательской маршрутизации

Страницы работы

Уважаемые коллеги! Предлагаем вам разработку программного обеспечения под ключ.

Опытные программисты сделают для вас мобильное приложение, нейронную сеть, систему искусственного интеллекта, SaaS-сервис, производственную систему, внедрят или разработают ERP/CRM, запустят стартап.

Сферы - промышленность, ритейл, производственные компании, стартапы, финансы и другие направления.

Языки программирования: Java, PHP, Ruby, C++, .NET, Python, Go, Kotlin, Swift, React Native, Flutter и многие другие.

Всегда на связи. Соблюдаем сроки. Предложим адекватную конкурентную цену.

Заходите к нам на сайт и пишите, с удовольствием вам во всем поможем.

Содержание работы

Лекция 10

Методы локальной пользовательской маршрутизации

Алгоритм Дейкстры

Эти методы обеспечивают оптимальный маршрут прохождения пакета между отдельной парой абонентов. Введем обозначения: D(v) – суммарная стоимость минимального пути от источника (узел с номером 1) до получателя (узел с номером v), l(i,j) – стоимость канала от узла i до узла j. Определена только для смежных узлов. Для несмежных равна ¥. Это подход является алгоритмом Дейкстры для сетевой маршрутизации.

Шаг0. Строится множество N, содержащее номер одного узла (первого). Строится таблица: строки таблицы – итерации, столбцы – номер операции, множество N, номера узлов (начиная со второго). В строке для нулевой итерации, в столбце для узла v фиксируется значение D1(v) = l(1,v). Нижний индекс показывает номер узла, через который достигается текущее оптимальное значение. Строиться корень дерева с узлом 1.

Шаг k (k = 1,2,3,…). В текущей строке выбираем узел v такой, что он не из множества N, но является смежным с каким-либо из узлов множества N и такой, что значение Dp(v) минимально. Узел v включается во множество N. В дереве добавляется узел с номером v в качестве потомка узла с номером p. Далее формируется новая строка таблицы, делается пересчет. Для всех узлов wÏN проверяем, изменилось ли стоимость маршрута по следующему правилу: , w* – любое, , если было оставлено старое значение,  иначе.

Алгоритм заканчивает работу, исчерпав все множество вершин.

Пример:

Nитер

N

2

3

4

5

6

0

1

21

51

11

¥1

¥1

1

1, 4

21

44

11

24

45

2

1, 4, 2

21

35

11

24

45

3

1, 4, 2, 5

21

35

11

24

45

4

1, 4, 2, 5, 3

21

35

11

24

45

5

1, 4, 2, 5, 3, 6

Похожие материалы

Информация о работе

Уважаемые коллеги! Предлагаем вам разработку программного обеспечения под ключ.

Опытные программисты сделают для вас мобильное приложение, нейронную сеть, систему искусственного интеллекта, SaaS-сервис, производственную систему, внедрят или разработают ERP/CRM, запустят стартап.

Сферы - промышленность, ритейл, производственные компании, стартапы, финансы и другие направления.

Языки программирования: Java, PHP, Ruby, C++, .NET, Python, Go, Kotlin, Swift, React Native, Flutter и многие другие.

Всегда на связи. Соблюдаем сроки. Предложим адекватную конкурентную цену.

Заходите к нам на сайт и пишите, с удовольствием вам во всем поможем.