120
правок
Изменения
→Поиск ближайших соседей в слое
Жадно идём по уровню в сторону запроса.
'''searchLayer'''(q, ep, ef, layer)''':'''
<font color="green">// Входные данные: иерархия графов hnsw, запрос q, входные точки ep, искомое количество ближайших соседей ef, номер слоя layer.</font> <font color="green">// Возвращает: ef ближайших соседей q в слое layer.</font> W = <tex>\emptyset</tex> <font color="green">// ближайшие Ближайшие к q вершины . </font> C = <tex>\emptyset</tex> <font color="green">// вершиныВершины, которые предстоит посетить . </font> V = <tex>\emptyset</tex> <font color="green">// посещённые Посещённые вершины . </font>
'''while''' C != <tex>\emptyset</tex>
u = {q1 | <tex>\forall</tex> q2 <tex>\in</tex> C, |q - q1| <= |q - q2|} <font color="green">// Ближайшая к q вершина из C . </font> f = {q1 | <tex>\forall</tex> q2 <tex>\in</tex> W, |q - q1| >= |q - q2|} <font color="green">// Самая дальняя от к q вершина из W . </font>
'''if''' |u - q| > |f - q|
'''break''' <font color="green">// Мы в локальном минимуме. </font>
'''if''' e <tex>{\notin}</tex> V
V = V <tex>\bigcup</tex> e
f = {q1 | <tex>\forall</tex> q2 <tex>\in</tex> W, |q - q1| >= |q - q2|} <font color="green">// Самая дальняя от к q вершина из W . </font>
'''if''' |e - q| < |f - q| or |W| < ef
C = C <tex>\bigcup</tex> e
