262
правки
Изменения
→Поиск максимального покрытия (maxCover)
==== Поиск максимального покрытия (maxCover)====
Основным минусом избирательного метода является то, что первый ориентир выбирается случайным образом и выбор последующих ориентиров будет сильно зависеть от первоначального.
Мы можем улучшить найденные ориентиры, если сначала, используя избирательный метод, найдём набор ориентиров в несколько (обычно, 4) раза больше, чем необходимо, а потом отсеем лишние минимизируя время запроса.
Оценим качество набора ориентиров <tex>S</tex> основываясь на покрытии дуг. Будем говорить, что ориентир <tex>L</tex> покрывает дугу <tex>(v,w)</tex>, если v находится на кратчайшем пути <tex>L \rightsquigarrow w</tex>. То есть, <tex>\ell(v,w) = dist(L,w)-dist(L,v)</tex>, тогда такой выбор ориентира даст нам нижнюю границу для всех путей, содержащих <tex>(v,w)</tex>.
Если хотя бы один ориентир из <tex>S</tex> покрывает дугу <tex>(v,w)</tex>, то и весь <tex>S</tex> покрывает эту дугу.
Этот метод является наилучшим, но является наиболее медленным. Задача выбора ориентиров в этом случае становится NP-полной.
=Ссылки=
