Задача нахождения кратчайшего пути с помощью алгоритма минимального остовного дерева.
Решение.
Сначала находим минимальное остовное дерево для данного графа: AD = 1, DG = 1, DE = 2, EH = 2, BE = 2, BC = 3, CF = 1.
Полученный путь обхода точек будет ADGDEHEBCFCBEDA, его длина равна 2*(1 + 1 + 2 + 2 + 2 + 3 + 1) = 24.
Однако, обойти все точки и вернуться в исходную можно короче: ADGEHEBCFCBA. Длина пути при этом будет равна: 1 + 1 + 2 + 2 + 2 + 2 + 3 + 1 + 1 + 3 + 2 = 20.
Путь удалось сократить на 100 % * (24-20) / 24 = 16,7 %.
Кратчайший путь обхода вершин в данном графе: ADGEHFCBA. Его длина равна 1 + 1 + 2 + 2 + 3 + 1 + 3 + 2 = 15.
Коэффициент аппроксимации (approximation factor) в данном случае равен: 20/15 = 1, 33.
Сначала находим минимальное остовное дерево для данного графа: AD = 1, DG = 1, DE = 2, EH = 2, BE = 2, BC = 3, CF = 1.
Полученный путь обхода точек будет ADGDEHEBCFCBEDA, его длина равна 2*(1 + 1 + 2 + 2 + 2 + 3 + 1) = 24.
Однако, обойти все точки и вернуться в исходную можно короче: ADGEHEBCFCBA. Длина пути при этом будет равна: 1 + 1 + 2 + 2 + 2 + 2 + 3 + 1 + 1 + 3 + 2 = 20.
Путь удалось сократить на 100 % * (24-20) / 24 = 16,7 %.
Кратчайший путь обхода вершин в данном графе: ADGEHFCBA. Его длина равна 1 + 1 + 2 + 2 + 3 + 1 + 3 + 2 = 15.
Коэффициент аппроксимации (approximation factor) в данном случае равен: 20/15 = 1, 33.
Комментариев нет:
Отправить комментарий