если N большое, то известно что примерно мы увидим… или если N какое-нибудь круглое, типа 4 или 9… а если N какое-нибудь дурное, типа 11?
как найти оптимум, блуждая по пространству конфигураций? есть два радикально разных подхода: 1) двигаться в случайном направлении, если получилось поставить рекорд — записать его в книжечку; 2) сдвигаться в новую точку только если в ней лучше, чем в старой
первый подход не может работать потому что оптимальные конфигурации очень конкретные, случайно туда не попадаешь; второй подход не может работать, потому что есть много локальных экстремумов (жестких конфигураций) и из первого же нам не уйти
в simulated annealing эти две идеи смешаны: сначала температура высокая и мы делаем достаточно случайные переходы, потом температура понижается и ухудшающие ситуацию переходы становятся всё менее вероятными… и всё магическим образом работает
это оказалось не особо сложно реализовать… но в зависимости от параметров магия либо работает, либо не работает, и надо как-то подбирать их либо наобум (долго и мучительно), либо из опыта, либо из глубокого понимания происходящего… мне, увы, доступен только первый вариант
вот, собственно, практически весь код:
def simulated_annealing(N, max_iter, T=0.2, cooling=0.9975):
centers = np.random.uniform(0, 1, (N, 2))
best_centers = centers.copy()
best_R = R = max_radius(centers)
history = [R]
for step in range(max_iter):
i = step%N
old_pos = centers[i].copy()
old_dist = point_dist(i, centers)
step_size = min(T**0.5,0.04)
centers[i] += np.random.normal(0, step_size, 2)
centers[i] = np.clip(centers[i], 0.0, 1.0)
delta = point_dist(i, centers) - old_dist
if delta > 0 or np.random.random() < np.exp(delta / T):
R = max_radius(centers)
if R > best_R:
best_R = R
best_centers = centers.copy()
else:
centers[i] = old_pos
T *= cooling
history.append(R)
return best_centers, best_R, history
(кто дочитал досюда, может заметить, что реализован не буквально отжиг… но если двигать точки по одной, работает лучше — и даже интуитивно понятно, почему)
на наилучшие известные упаковки можно посмотреть на странице erich-friedman.github.io/packing/ — мб кто-то из читателей сможет что-то из рекордов улучшить ;