Всеки оптимизатор на разкрой се нарича „оптимален“. Ние публикуваме числата: три набора тестови задачи, независим оракул за малките, доказуеми долни граници за цеховите и суровия JSON с всички параметри на прогона. Последен прогон: 2026-09-17, ядро 6edd4c42bb6b.
▶ Отвори калкулатораНе е една формула, а търсене с няколко стратегии върху една и съща задача: бързите евристики (FFD, BFD, FFI, подредба по брой), динамично програмиране по шаблони, разбъркан FFD и GRASP с фиксиран seed, поглед напред (lookahead) и две точни търсения с ограничен бюджет — за малко различни дължини и за малки списъци. Всеки кандидат минава през локално подобрение (изпразване на пръти и размени), след което печели решението с най-малко материал, после с най-малко пръти. Бюджетите са в брой операции, не в секунди — резултатът е един и същ на бърз и на бавен сървър. Показваме го като „най-доброто намерено решение“; „доказано оптимално“ казваме само когато то достига математическата долна граница за задачата.
Три набора синтетични задачи с фиксиран seed (20260917), генерирани от скрипта tests/benchmark_optimal.py. (A) Точно проверими: 200 малки задачи (2–4 заготовки 60–130, 2–7 отрязъка 10–65, срез 0/1/3) с независим оракул — пълно изброяване на всички разпределения. (B) Стоманен цех: 300 спецификации — заготовки 6000 mm (90 от тях със смес 6000 + 12000), 8–30 различни дължини 250–5800 mm по 1–20 броя, срез 3 mm, мин. остатък 300 mm; средно 204 отрязъка на задача (от 55 до 393). (C) Мащаб: 50, 200, 500, 1000, 2000 отрязъка × 3 задачи. Всички режими се пускат в един процес на една машина; времето е time.perf_counter около самото извикване на ядрото.
При малките задачи оракулът знае истинския оптимум. „Пълно съвпадение“ изисква и същото разпределение на остатъците по прътите; „материал + пръти“ е това, което реално плащаш; „мин. пръти“ — дали е постигнат най-малкият възможен брой пръти.
| Алгоритъм | Пълно съвпадение с оракула | Оптимум по материал и пръти | Мин. пръти | Медианно време (s) |
|---|---|---|---|---|
| Оптимален | 100% | 100% | 100% | <0.01 |
| FFD | 42.5% | 74.5% | 84% | <0.01 |
| BFD | 42.5% | 74.5% | 84% | <0.01 |
| FFI | 32.5% | 62.5% | 76.5% | <0.01 |
| LOOK | 63% | 80.5% | 88.5% | <0.01 |
| GRASP | 64% | 79.5% | 88% | <0.01 |
| SFFD | 65.5% | 80.5% | 88.5% | <0.01 |
| Seq | 31% | 59.5% | 59.5% | <0.01 |
Тук истинският оптимум е неизвестен — сравняваме с долна граница: L1 = ⌈Σ(дължина + срез) / (6000 + срез)⌉ и по-силната L2 на Martello–Toth, която брои отрязъците над 3000 mm, неспособни да делят прът. „Доказан оптимум“ = решението достига границата. При смесен склад 6000 + 12000 броим в 6-метрови еквиваленти (12 m прът = 2) и важи само L1, затова там границата е по-хлабава. „Оптимален“ е строго по-добър от FFD в 38.3% от задачите, равен в 61.7% и по-лош в 0%; спрямо BFD — по-добър в 39.3%. Общо спестени пръти спрямо FFD в целия набор: 973. Само за задачите с единичен склад (210 бр.): доказан оптимум 31.4%, средна разлика до границата 1.67 пръта, максимална 8.
| Алгоритъм | Ср. пръти (6 m екв.) | Ср. отпадък | Доказан оптимум | Ср. разлика (пръти) | Макс. разлика | Медианно време (s) | 95-и перц. (s) |
|---|---|---|---|---|---|---|---|
| Оптимален | 110.7 | 7.7% | 26.3% | 1.79 | 12 | 3.85 | 11.34 |
| FFD | 114.0 | 10.4% | 21.3% | 5.04 | 47 | 0.03 | 0.08 |
| BFD | 114.0 | 10.5% | 21.3% | 5.05 | 47 | 0.03 | 0.08 |
| FFI | 114.3 | 10.7% | 20.7% | 5.35 | 47 | 0.04 | 0.11 |
| GRASP | 114.0 | 10.4% | 21.3% | 5.02 | 47 | 0.23 | 0.66 |
| SFFD | 114.0 | 10.4% | 20.7% | 5.06 | 47 | 0.15 | 0.47 |
| Seq | 120.3 | 15.2% | 6.3% | 11.35 | 49 | 0.01 | 0.02 |
Медианно време в секунди по 3 задачи за всеки размер (единичен склад 6000, същите параметри като в B). Ядрото има вградени гейтове: погледът напред работи до 240 отрязъка, точните търсения — до 600, затова времето не расте линейно с размера. Размери, при които „Оптимален“ надхвърля 10 s: —.
| Отрязъци | Оптимален | FFD | BFD | FFI | LOOK | GRASP | SFFD | Seq |
|---|---|---|---|---|---|---|---|---|
| 50 | 0.21 | <0.01 | <0.01 | <0.01 | 0.10 | 0.02 | 0.01 | <0.01 |
| 200 | 6.74 | 0.01 | 0.03 | 0.02 | 2.90 | 0.26 | 0.16 | 0.01 |
| 500 | 4.02 | 0.24 | 0.25 | 0.25 | 0.17 | 1.49 | 0.94 | 0.03 |
| 1000 | 5.86 | 0.28 | 0.24 | 0.30 | 0.31 | 1.52 | 1.42 | 0.08 |
| 2000 | 7.61 | 0.31 | 0.68 | 0.31 | 0.38 | 4.17 | 3.69 | 0.44 |
Задачите са случайни и синтетични. Равномерно разпределените дължини 250–5800 mm са по-тежки от типична спецификация — повечето отрязъци над 3 m не могат да делят прът, затова отпадъкът е висок при всички алгоритми; важна е разликата между тях, не абсолютната стойност. Разликата до долната граница не е доказана неоптималност — истинският оптимум е някъде между границата и намереното решение. Времената са от една машина (Python 3.14.0); сървърът може да е по-бърз или по-бавен. Реалните поръчки са различни — най-сигурният тест е твоята спецификация.
Скриптът tests/benchmark_optimal.py (само стандартна библиотека + ядрото) е част от кода на приложението, който не е публичен — теста го пускаме ние. Публичен е суровият резултат: benchmark-results.json (backend/benchmark_results.json в кода); страницата чете числата от него при стартиране — нищо не се пише на ръка. В него са seed 20260917, параметрите на генератора на задачи, лимитите и SHA-256 на ядрото 6edd4c42bb6b7ba0b5f9ee2f6d1b5f11e054c90d2c972b9a961082d945c91f4c. Пълният прогон (py -3 tests/benchmark_optimal.py) отнема около 30 минути. Алгоритъмът „Оптимален“ е достъпен в плановете Hobby и Pro; безплатният план смята с FFD и BFD от същите таблици.
Защото долната граница не е самият оптимум. При задача с много отрязъци над 3 m границата подценява нужните пръти и решението може да е оптимално, без да можем да го докажем. В набор A, където оптимумът е известен точно, съвпадението е 100%.
При случайни дължини повечето пръти се запълват еднозначно и всяка разумна евристика ги намира. Разликата идва в „стегнатите“ задачи с комбинации от 2–3 отрязъка, които еднопроходните алгоритми не виждат — там „Оптимален“ печели по един-два пръта, а на тон стомана това е реална сума.
Не — скриптът и ядрото са част от кода на приложението и не са публично достъпни. Публичен е суровият JSON на /benchmark-results.json със seed, параметрите на генератора и резултатите по задача; всяко число в таблиците е от него. Най-сигурната проверка е твоята спецификация: сравни „Оптимален“ (Hobby/Pro) с FFD/BFD в калкулатора.