120
правок
Изменения
→Маленький мир
Для маленького мира на точках в Евклидовом пространстве, жадный поиск K ближайших соседей будет выглядеть так:
'''knn'''(request, m, k)''':'''
'''for''' i = 1 '''to''' m
'''while''' ''true''
'''break'''
'''for''' v e : смежные с current u вершины '''if''' !visited.contains(v)e <tex>{\notin}</tex> V candidates.add(v)C = C <tex>\bigcup</tex> e visited.add(v)V = V <tex>\bigcup</tex> e tempNearest.add(v) V = V <tex>\bigcup</tex> e nearest.addAll(tempNearest)W = W <tex>\bigcup</tex> TN '''return''' k первых вершин из nearestW
Очевидный недостаток этого алгоритма {{---}} опасность свалиться в локальный минимум, остановившись в каком-то кластере. С увеличением числа m, вероятность такого застревания экспоненциально падает.
