Każdy optymalizator rozkroju nazywa się „optymalnym”. My publikujemy liczby: trzy zestawy zadań testowych, niezależną wyrocznię dla małych, dowodliwe dolne ograniczenia dla warsztatowych oraz surowy JSON ze wszystkimi parametrami przebiegu. Ostatni przebieg: 2026-09-17, silnik 6edd4c42bb6b.
▶ Otwórz kalkulatorTo nie jeden wzór, lecz przeszukiwanie kilkoma strategiami tego samego zadania: szybkie heurystyki (FFD, BFD, FFI, porządek wg ilości), programowanie dynamiczne po wzorcach, tasowany FFD i GRASP ze stałym seedem, podgląd naprzód (look-ahead) oraz dwa dokładne przeszukiwania z ograniczonym budżetem — jedno dla niewielu różnych długości, drugie dla krótkich list. Każdy kandydat przechodzi lokalne ulepszanie (opróżnianie prętów i zamiany), po czym wygrywa rozwiązanie z najmniejszą ilością materiału, a następnie z najmniejszą liczbą prętów. Budżety liczone są w operacjach, nie w sekundach — wynik jest identyczny na szybkim i na wolnym serwerze. Pokazujemy go jako „najlepsze znalezione rozwiązanie”; „udowodnione optimum” mówimy tylko wtedy, gdy osiąga matematyczne dolne ograniczenie zadania.
Trzy zestawy syntetycznych zadań ze stałym seedem (20260917), generowane przez tests/benchmark_optimal.py. (A) Dokładnie weryfikowalne: 200 małych zadań (2–4 pręty 60–130, 2–7 elementów 10–65, rzaz 0/1/3) z niezależną wyrocznią — pełne wyliczenie wszystkich przydziałów. (B) Stalownia: 300 list cięć — pręty 6000 mm (90 z nich z mieszanką 6000 + 12000), 8–30 różnych długości 250–5800 mm po 1–20 sztuk, rzaz 3 mm, min. resztka 300 mm; średnio 204 elementów na zadanie (od 55 do 393). (C) Skalowanie: 50, 200, 500, 1000, 2000 elementów × 3 zadania. Wszystkie tryby działają w jednym procesie na jednej maszynie; czas mierzy time.perf_counter wokół samego wywołania silnika.
Dla małych zadań wyrocznia zna prawdziwe optimum. „Pełna zgodność” wymaga też tego samego rozkładu resztek na prętach; „materiał + pręty” to to, za co realnie płacisz; „min. prętów” — czy osiągnięto najmniejszą możliwą liczbę prętów.
| Algorytm | Pełna zgodność z wyrocznią | Optimum materiał + pręty | Min. prętów | Mediana czasu (s) |
|---|---|---|---|---|
| Optymalny | 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 |
Tu prawdziwe optimum jest nieznane — porównujemy z dolnym ograniczeniem: L1 = ⌈Σ(długość + rzaz) / (6000 + rzaz)⌉ oraz silniejszym L2 Martello–Totha, które liczy elementy powyżej 3000 mm, niemogące dzielić pręta. „Udowodnione optimum” = rozwiązanie osiąga ograniczenie. Przy mieszanym magazynie 6000 + 12000 liczymy w ekwiwalentach 6 m (pręt 12 m = 2) i obowiązuje tylko L1, więc ograniczenie jest tam luźniejsze. „Optymalny” jest ściśle lepszy od FFD w 38,3% zadań, równy w 61,7% i gorszy w 0%; wobec BFD — lepszy w 39,3%. Pręty zaoszczędzone względem FFD w całym zestawie: 973. Tylko zadania z jedną długością pręta (210 szt.): udowodnione optimum 31,4%, średnia różnica do ograniczenia 1,67 pręta, maksymalna 8.
| Algorytm | Śr. prętów (ekw. 6 m) | Śr. odpad | Udowodnione optimum | Śr. różnica (pręty) | Maks. różnica | Mediana czasu (s) | 95. percentyl (s) |
|---|---|---|---|---|---|---|---|
| Optymalny | 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 |
Mediana czasu w sekundach z 3 zadań dla każdego rozmiaru (tylko pręty 6000, te same parametry co w B). Silnik ma wbudowane progi: podgląd naprzód działa do 240 elementów, przeszukiwania dokładne do 600 — dlatego czas nie rośnie liniowo z rozmiarem. Rozmiary, przy których „Optymalny” przekracza 10 s: —.
| Elementy | Optymalny | 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 |
Zadania są losowe i syntetyczne. Równomiernie rozłożone długości 250–5800 mm są trudniejsze niż typowa lista cięć — większość elementów powyżej 3 m nie może dzielić pręta, więc odpad jest wysoki dla każdego algorytmu; liczy się różnica między nimi, nie wartość bezwzględna. Różnica do dolnego ograniczenia nie jest udowodnioną nieoptymalnością — prawdziwe optimum leży gdzieś między ograniczeniem a znalezionym rozwiązaniem. Czasy pochodzą z jednej maszyny (Python 3.14.0); serwer może być szybszy lub wolniejszy. Prawdziwe zlecenia są inne — najpewniejszy test to Twoja własna lista cięć.
Skrypt tests/benchmark_optimal.py (tylko biblioteka standardowa + silnik) jest częścią kodu aplikacji, który nie jest publiczny — test uruchamiamy sami. Publiczny jest surowy wynik: benchmark-results.json (backend/benchmark_results.json w kodzie); strona czyta liczby z tego pliku przy starcie — nic nie jest wpisywane ręcznie. Zapisane są w nim seed 20260917, parametry generatora zadań, limity i SHA-256 silnika 6edd4c42bb6b7ba0b5f9ee2f6d1b5f11e054c90d2c972b9a961082d945c91f4c. Pełny przebieg (py -3 tests/benchmark_optimal.py) trwa około 30 minut. Algorytm „Optymalny” jest dostępny w planach Hobby i Pro; plan darmowy liczy FFD i BFD z tych samych tabel.
Bo dolne ograniczenie nie jest samym optimum. Przy zadaniu z wieloma elementami powyżej 3 m ograniczenie zaniża potrzebną liczbę prętów, więc rozwiązanie może być optymalne, choć nie potrafimy tego udowodnić. W zestawie A, gdzie optimum jest znane dokładnie, zgodność wynosi 100%.
Przy losowych długościach większość prętów wypełnia się w oczywisty sposób i każda rozsądna heurystyka to znajduje. Różnica pojawia się w „ciasnych” zadaniach z kombinacjami 2–3 elementów, których algorytmy jednoprzebiegowe nigdy nie widzą — tam „Optymalny” wygrywa jeden–dwa pręty, a na tonę stali to realne pieniądze.
Nie — skrypt i silnik są częścią kodu aplikacji i nie są publicznie dostępne. Publiczny jest surowy JSON pod /benchmark-results.json z seedem, parametrami generatora i wynikami dla każdego zadania; każda liczba w tabelach pochodzi z niego. Najpewniejszy sprawdzian to Twoja własna lista cięć: porównaj „Optymalny” (Hobby/Pro) z FFD/BFD w kalkulatorze.