 |
|
Алгоритм решения задачи
1. Определить множество пар узлов 
, между которыми необходимо существование путей (каналов) передачи информации.
2. Выбрать очередную пару узлов.
3. Определить все возможные пути передачи информации между ними.
4. Для каждого пути подсчитать значение F.
5. Выбрать путь, имеющий наименьшее значение F.
6. Если все пары узлов из U, рассмотрены, то перейти к пункту 7, иначе к пункту 2.
7. Выбрать очередную пару узлов.
8. Если между парой узлов существует более двух путей, то перейти к пункту 10, иначе к пункту 9.
9. Добавить путь.
10. Если все пары узлов из U рассмотрены, то перейти к пункту 7.
11. Конец.
Пример
Таблица 8
| Узлы связи | объём информации | стоимость аренды канала |
| 1-2 | ||
| 1-3 | ||
| 1-4 | ||
| 2-3 | ||
| 2-4 | ||
| 3-4 |
Для сети из 4 узлов связи заданы параметры, представленные в таблице 8. Пропускная способность канала t=5.
Согласно алгоритму решения задачи определяем 6 пар узлов, между которыми необходимо существование пути передачи информации. Выбираем пару 1-2. Для нее возможно 5 путей: (1-2; 1-3-2; 1-4-2; 1-3-4-2; 1-4-3-2).
Поскольку t=5, то для передачи необходимо 6 однопроводных каналов и значения:
Для обмена информацией между узлами 1-2 наиболее целесообразно использовать путь 1-4-2.
После определения путей для каждой пары узлов получается результат, представленный в таблице 9.
Таблица 9
| узлы связи | путь |
| 1-2 | 1-4-2 |
| 1-3 | 1-3 |
| 1-4 | 1-4 |
| 2-3 | 2-3 |
| 2-4 | 2-4 |
| 3-4 | 3-4 |
Индивидуальное задание.
В соответствии с вариантами заданий, приведенными в таблице 10-11, определить оптимальную конфигурацию сети и полученный вариант представить в виде таблицы.
Таблица 10
| вариант | ||||||
| узлы связи | 
|
|
|
|
|
|
| 1-2 | 20 30 | 30 35 | 20 20 | 25 25 | 35 10 | 40 20 |
| 1-3 | 10 20 | 40 30 | 40 25 | 30 20 | 70 15 | 30 10 |
| 1-4 | 15 5 | 5 60 | 15 30 | 35 10 | 10 5 | 15 15 |
| 1-5 | 20 10 | 10 5 | 20 40 | 35 15 | 80 25 | 25 30 |
| 2-3 | 30 10 | 15 10 | 25 10 | 40 20 | 90 35 | 30 25 |
| 2-4 | 40 15 | 30 25 | 30 15 | 10 10 | 10 40 | 40 15 |
| 2-5 | 5 25 | 20 30 | 40 20 | 15 25 | 5 5 | 20 30 |
| 3-4 | 10 30 | 10 70 | 50 25 | 20 10 | 15 10 | 15 10 |
| 3-5 | 15 40 | 15 5 | 20 30 | 25 15 | 20 15 | 10 5 |
| 4-5 | 25 25 | 20 10 | 10 10 | 30 10 | 25 20 | 15 15 |
Таблица 11
| вариант | |||||||
| узлы связи |
|
|
|
|
|
|
|
| 1-2 | 33 30 | 20 30 | 20 25 | 25 30 | 35 10 | 40 20 | 50 35 |
| 1-3 | 45 35 | 15 25 | 30 35 | 35 15 | 60 15 | 30 10 | 40 30 |
| 1-4 | 5 60 | 15 5 | 15 30 | 35 10 | 20 5 | 15 25 | 5 60 |
| 1-5 | 10 5 | 20 10 | 20 40 | 35 15 | 80 25 | 45 30 | 10 5 |
| 2-3 | 15 10 | 30 10 | 25 10 | 40 20 | 90 35 | 30 25 | 25 10 |
| 2-4 | 30 25 | 40 15 | 30 15 | 10 15 | 10 40 | 40 15 | 35 20 |
| 2-5 | 20 30 | 5 25 | 40 20 | 15 25 | 5 10 | 20 30 | 20 35 |
| 3-4 | 10 70 | 10 30 | 50 25 | 20 10 | 15 10 | 15 10 | 20 70 |
| 3-5 | 15 5 | 15 40 | 20 30 | 25 15 | 20 15 | 10 5 | 15 5 |
| 4-5 | 20 10 | 25 30 | 10 20 | 30 10 | 25 20 | 15 15 | 30 10 |
Лабораторная работа №4.