О кратчайшем пути на графе II
(или случайные блуждания как оценка расстояния до целевой вершины)

Альтернативный путь к предыдущему посту дают случайные блуждания. Кубик Рубика очень легко разобрать, и гораздо сложнее собрать, поэтому попробуем делать 1≤K≤(~ диаметр графа) случайных шагов из целевой вершины n блуждающими, а затем пытаться это K нашей моделью восстановить.

На графиках показан разброс значений K который мы получаем для разных дистанцией d. Если вершина встретилась несколько раз, то возьмём минимальный K, так большие n будут приводить к разметке окрестности целевой вершины. Видна некоторая монотонность K(d) и их коррелированность, что в конечном итоге позволяет предсказывая по вершинам K эффективно собирать кубик!)

P.S. Аккуратнее с корреляцией, как с метрикой связи между величинами)