← На главную

Schadt и Ellsworth: рекорды упаковки квадратов с simulated annealing

24.05.2026 13:20 · hackernews

В задаче упаковки единичных квадратов в минимальный квадрат (packing squares in a square) за последние месяцы достигнуты новые рекорды. Thomas Schadt и David Ellsworth с помощью программ simulated annealing нашли улучшенные упаковки для десятков значений n. Работа ведётся с конца 1970-х: первые результаты получили Frits Göbel, Walter Trump, Charles F. Cottingham, позже — Erich Friedman, David W. Cantrell, Joe DeVincentis, Károly Hajba и другие.

С декабря 2025 по февраль 2026 Schadt и Ellsworth обновили рекорды для n=28, 29, 39, 41, 50, 51, 55, 68, 71, 103, 105, 126, 129, 131, 132, 154, 155, 156, 171, 179, 180, 181, 182, 206, 207, 208, 209, 210, 238, 239, 240, 241 и многих других. Ellsworth использовал модифицированные версии программ Schadt, стартуя со случайных конфигураций. Некоторые упаковки оказались «doubly semi‑primitive» — только неповёрнутые квадраты по левому и правому краям, но повёрнутые квадраты, выходящие за верхнюю и нижнюю стороны. Первую такую упаковку для n=146 нашёл David W. Cantrell в январе 2025.

Отдельно выделяются упаковки с рациональной длиной стороны, найденные благодаря пифагоровым тройкам. Например, s=50 (тройка {3,4,5}) и s=230 (тройка {20,21,29}) — вторая и третья рекордные рациональные упаковки. Первую рациональную, но не рекордную, получил Ellsworth в декабре 2024 для n=104.

Многие старые рекорды были улучшены: s(53) (Cantrell, Ellsworth), s(69) (Morandi, затем Cantrell), s(83), s(87), s(88), s(102), s(106), s(108), s(123), s(126), s(128), s(130), s(152), s(172), s(177), s(205), s(228), s(235), s(236), s(266), s(268) и другие. Для некоторых упаковок (s(37), s(88), s(123)) разработана новая техника улучшения, независимо найденная Cantrell и Ellsworth в январе 2025. Её планируется применить ещё к двадцати упаковкам, которые считались законченными.

Результаты M.Z. Arslanov, S.A. Mustafin и Z.K. Shangitbayev (март 2019) для n=132, 156, 182, 210, 240, 241 также были улучшены Ellsworth. Многие новые упаковки пока не оптимизированы аналитически — их значения s получены численно.

Читать оригинал →