Планарные остовы ограниченной степени с малыми весами: различия между версиями
Перейти к навигации
Перейти к поиску
Irina (обсуждение | вклад) м (→Применение) |
Irina (обсуждение | вклад) |
||
| Строка 76: | Строка 76: | ||
а) Вначале узел u сортирует всех своих BLACK-соседей в N(u), если таковые имеются, по порядку возрастания расстояния, а затем сортирует всех WHITE-соседей N(u), если таковые имеются, подобным же образом. После этого отсортированные результаты восстанавливаются в N(u); вначале записывается отсортированный список BLACK-соседей, а затем – отсортированный список WHITE-соседей. | а) Вначале узел u сортирует всех своих BLACK-соседей в N(u), если таковые имеются, по порядку возрастания расстояния, а затем сортирует всех WHITE-соседей N(u), если таковые имеются, подобным же образом. После этого отсортированные результаты восстанавливаются в N(u); вначале записывается отсортированный список BLACK-соседей, а затем – отсортированный список WHITE-соседей. | ||
б) Узел u сканирует отсортированный список N(u) слева направо. На каждом шагу он сохраняет в списке текущего указываемого соседа w, но удаляет каждый конфликтующий узел v из оставшейся части списка. «Узел v конфликтует с w» означает, что этот узел v принадлежит к <math> \theta\ </math>-доминирующей области узла w. Здесь <math>\theta\ = 2 \pi\ / k</math>, где <math>k \ge 9</math> – настраиваемый параметр. | б) Узел u сканирует отсортированный список N(u) слева направо. На каждом шагу он сохраняет в списке текущего указываемого соседа w, но удаляет каждый конфликтующий узел v из оставшейся части списка. «Узел v конфликтует с w» означает, что этот узел v принадлежит к <math> \theta\ </math>-доминирующей области узла w. Здесь <math>\theta\ = 2 \pi\ / k</math>, где <math>k \ge 9</math>, – настраиваемый параметр. | ||
Затем узел u помечает себя меткой BLACK, т.е. «обработанный», и уведомляет каждый удаленный соседний узел v из N(u) при помощи широковещательного сообщения UPDATEN. | Затем узел u помечает себя меткой BLACK, т.е. «обработанный», и уведомляет каждый удаленный соседний узел v из N(u) при помощи широковещательного сообщения UPDATEN. | ||