120
правок
Изменения
→Маленький мир
Чёрные ребра {{---}} короткие связи с ближайшими соседями, красные рёбра {{---}} длинные связи, обеспечивающие малое мат. ожидание длины пути.
[https://www.hse.ru/mirror/pubs/lib/data/access/ram/ticket/30/1551306415713d428dca7fd05f3d108fe8e66042c4/Approximate%20nearest%20neighbor%20algorithm%20based%20on%20navigable%20(Information%20Systems).pdf Оригинал]]]
'''Маленький мир''' <ref>[https://en.wikipedia.org/wiki/Small-world_network Статья о маленьком мире на википедии]</ref> (англ. ''Small World'') {{---}} граф, в котором мат. ожидание кратчайшего пути между двумя случайно выбранными вершинами растёт пропорционально <tex>\log{N}</tex>. Но при этом средняя степень вершины мала.
Для маленького мира на точках в Евклидовом пространстве жадный поиск K ближайших соседей будет выглядеть так:
