Devlog #91 – Fala 70: CPM/PERT, k-NN, wyboczenie, drzewo minimax, pas Van Allena i relaksacja Lloyda

Nowe symulacje

CPM/PERT: analiza ścieżki krytycznej

Harmonogramowanie projektów ma piękny szkielet teoriograficzny. Metoda ścieżki krytycznej (CPM) i technika oceny i przeglądu programu (PERT) dzielą tę samą strukturę DAG, ale różnią się sposobem obsługi niepewności czasu trwania czynności.

Sortowanie topologiczne oraz przejście w przód/w tył

Algorytm Kahna znajduje ważne uporządkowanie topologiczne DAG czynności, wielokrotnie usuwając węzły o stopniu wejściowym zero. Przejście w przód oblicza następnie czasy Wczesnego Rozpoczęcia i Wczesnego Zakończenia: ES_i = max(EF_j) po wszystkich poprzednikach j oraz EF_i = ES_i + duration_i. Przejście w tył ustala termin projektu i propaguje wstecz: LS_i = LF_i − duration_i, LF_i = min(LS_k) po wszystkich następnikach k. Czynności o zerowym zapasie (LF − EF = 0) tworzą ścieżkę krytyczną — jakiekolwiek opóźnienie tam opóźnia cały projekt.

Trójpunktowa estymacja PERT

PERT rozwiązuje problem niepewności czasu trwania za pomocą trzech estymacji na czynność: optymistycznej (o), najbardziej prawdopodobnej (m) i pesymistycznej (p). Oczekiwany czas trwania wynosi t_e = (o + 4m + p) / 6, a wariancja σ² = ((p−o)/6)². Czas zakończenia projektu jest w przybliżeniu normalny, z μ = suma oczekiwanych czasów trwania ścieżki krytycznej i σ² = suma wariancji ścieżki krytycznej. Panel prawdopodobieństwa dotrzymania terminu pokazuje dystrybuantę normalną P(T < termin).

• Przeciągaj paski czasu trwania czynności, by aktualizować ścieżkę krytyczną w czasie rzeczywistym
• Zapas (slack) pokazany dla każdej czynności niekrytycznej
• Panel PERT z rozbiciem niepewności poszczególnych czynności
• Eksport sieci jako prostej listy czynności JSON

k-NN: granice decyzyjne z lokalnego głosowania

k najbliższych sąsiadów to archetypowy klasyfikator nieparametryczny — nie czyni żadnych założeń co do rozkładu danych, przechowuje wszystkie punkty treningowe i klasyfikuje każde zapytanie przez głosowanie większościowe wśród k najbliższych sąsiadów.

Obliczanie regionów decyzyjnych

Symulacja renderuje siatkę regionów decyzyjnych 80×60 — każda komórka jest klasyfikowana niezależnie i kolorowana według klasy. Dostępne są trzy metryki odległości: euklidesowa (norma L2, sąsiedztwa koliste), Manhattan (norma L1, w kształcie rombu) i Czebyszewa (norma L∞, sąsiedztwa kwadratowe). Przy ważeniu odległości 1/d² bliżsi sąsiedzi mają silniejszy głos, co daje gładsze granice w pobliżu punktów treningowych.

Kompromis obciążenie-wariancja przez LOOCV

Walidacja krzyżowa typu leave-one-out usuwa każdy punkt treningowy, klasyfikuje go za pomocą pozostałych punktów i liczy poprawne predykcje. Krzywa dokładności k ujawnia fundamentalny kompromis: k=1 idealnie zapamiętuje zbiór treningowy (przeuczenie, wysoka wariancja), ale słabo generalizuje; duże k wygładza granicę, ale może niedouczać. Optymalne k znajduje się na szczycie krzywej.

• 5 gotowych zestawów danych: dwie Gaussowskie, cztery skupiska, sierpy księżyca, okręgi współśrodkowe, plamy XOR
• Kliknij, by dodać własne punkty treningowe w dowolnej z 4 klas
• Suwak k od 1 do 25
• Przełącznik nakładki Voronoi, by zobaczyć dokładne granice 1-NN

Wyboczenie kolumny Eulera: stateczność konstrukcji

Gdy smukła kolumna pod obciążeniem osiowym osiąga krytyczne obciążenie Eulera, wygina się bocznie w bifurkacji widłowej — proste położenie równowagi staje się niestabilne i pojawiają się dwa wygięte stany równowagi. To jeden z najważniejszych trybów awarii konstrukcyjnych w inżynierii.

Obciążenie krytyczne i długość efektywna

Wzór na obciążenie krytyczne Eulera to P_cr = π²EI / (KL)², gdzie E to moduł Younga, I to moment bezwładności przekroju względem słabej osi, L to długość fizyczna, a K to współczynnik długości efektywnej, zależny od warunków brzegowych:

• Przegub-przegub (oba końce swobodnie obrotowe): K = 1,0
• Przegub-utwierdzenie (jeden koniec utwierdzony): K = 0,7
• Utwierdzenie-utwierdzenie (oba końce zamocowane): K = 0,5
• Utwierdzenie-swobodny (maszt / wspornik): K = 2,0

Parabola Johnsona dla kolumn krępych

Wzór Eulera jest ważny tylko dla kolumn smukłych (KL/r > π√(2E/σ_y), gdzie r = √(I/A) to promień bezwładności). Dla krótszych kolumn uplastycznienie materiału następuje przed wyboczeniem sprężystym. Parabola Johnsona P_cr/A = σ_y − (σ_y²/4π²E)(KL/r)² płynnie przechodzi od granicy plastyczności do krzywej Eulera w punkcie stycznym, obejmując pełny zakres smukłości.

• Przekroje: prostokąt pełny (moment bezwładności słabej osi I = bh³/12), koło pełne (I = πd⁴/64), dwuteownik (obliczany z wymiarów pasa/środnika)
• Wykres bifurkacji widłowej: ugięcie vs obciążenie znormalizowane przez P_cr
• Wyświetlanie współczynnika bezpieczeństwa względem obciążenia projektowego
• Baza materiałów: stal, aluminium, drewno, włókno węglowe

Minimax z przycinaniem alfa-beta

Minimax to fundament przeszukiwania drzew gier przeciwstawnych: gracz maksymalizujący wybiera ruch o najwyższej wartości minimax; minimalizujący wybiera najniższą. Przycinanie alfa-beta eliminuje gałęzie, które nie mogą wpłynąć na ostateczną decyzję — bez zmiany wyniku, jedynie prędkości.

Okno alfa-beta

Każdy węzeł utrzymuje okno (α, β), gdzie α to najlepszy wynik gwarantowany maksymalizującemu, a β to najlepszy gwarantowany minimalizującemu. Przycinanie następuje, gdy β ≤ α: minimalizujący w węźle znalazł wartość ≤ α, więc maksymalizujący powyżej i tak nigdy nie odwiedzi tego węzła. Szare poddrzewa w wizualizacji pokazują dokładnie, które gałęzie są obcinane.

Moc kolejności ruchów

Skuteczność przycinania alfa-beta zależy krytycznie od kolejności ruchów. W najlepszym przypadku (najlepszy ruch zawsze wypróbowany jako pierwszy) redukuje liczbę węzłów z O(b^d) do O(b^(d/2)) — efektywnie podwajając głębokość przeszukiwania. Symulacja uruchamia jednocześnie kolejność losową i best-first, pokazując liczby odwiedzonych węzłów różniące się nawet 5-krotnie na tym samym drzewie.

• 3 gotowe drzewa: zrównoważone, głębokie jednostronne, mieszane z licznymi obcięciami
• Generator drzew losowych: współczynnik rozgałęzienia b ∈ [2,4], głębokość d ∈ [3,5]
• Tryb krok po kroku z oknami alfa, beta pokazanymi przy każdym węźle
• Licznik odwiedzonych węzłów: pełny minimax vs alfa-beta

Pas Van Allena: pułapkowanie cząstek w polu dipolowym

Pasy radiacyjne Van Allena to strefy energetycznych naładowanych cząstek uwięzionych przez ziemskie pole dipolowe. Naładowana cząstka w polu magnetycznym spiralnie porusza się wokół linii pola, odbija się między zwierciadłami magnetycznymi i powoli dryfuje wokół planety — trzy zagnieżdżone ruchy okresowe.

Pole dipolowe i siła Lorentza

Składowe dipolowego pola magnetycznego to B_r = 3rz/R⁵ i B_z = (3z²−R²)/R⁵ (we współrzędnych cylindrycznych). Integrator Lorentza aktualizuje prędkość przez rotację: pół-kopnięcie, następnie obrót v wokół B o kąt ω_c·dt (częstość cyklotronowa ω_c = qB/m), a potem drugie pół-kopnięcie. To zachowuje moment magnetyczny μ = mv²_⊥/2B dokładnie dla małego dt.

Ruch zwierciadlany i dryf

Gdy cząstka spiralnie zbliża się do bieguna magnetycznego, linie pola się zbiegają i B rośnie. Ponieważ μ jest zachowywane adiabatycznie, prostopadła energia kinetyczna musi wzrosnąć — więc równoległa energia kinetyczna maleje do zera i cząstka odbija się z powrotem. Stożek strat definiuje wzór sin²α_lc = B_równik/B_atmosfera; cząstki o kątach nachylenia wewnątrz stożka strat uderzają w atmosferę. Parametr L-shell wykorzystuje dokładny wzór B(L,λ) = (1/L³)√(1+3sin²λ)/cos⁶λ.

• Przełączaj między protonem (m = 1) a elektronem (m = 1/1836) — obserwuj różne promienie żyracji
• Wizualizuj wszystkie trzy ruchy: żyrację, odbicie zwierciadlane, dryf azymutalny
• Suwak kąta nachylenia, by zademonstrować odcięcie stożka strat
• Nakładka linii pola L-shell na widok przekroju

Relaksacja Lloyda: centroidalna triangulacja Voronoi

Algorytm Lloyda (1982) iteracyjnie ulepsza diagram Voronoi w kierunku konfiguracji centroidalnej, w której każdy punkt węzłowy znajduje się dokładnie w centroidzie swojej komórki. Wynikiem jest pięknie jednolite ułożenie kafelków, stosowane w generowaniu siatek, ditheringu i lokalizacji obiektów.

Aktualizacja centroidu i spadek energii

Każda iteracja: oblicz diagram Voronoi, znajdź centroid pola każdej komórki c = (Σw(x)·x / Σw(x)) ważony funkcją gęstości ρ(x), następnie przesuń każdy punkt węzłowy do jego centroidu. Energia kwantyzacji E = Σ_i ∫_{V_i} ρ(x)|x−c_i|² dx maleje monotonicznie — algorytm Lloyda to zejście współrzędnościowe na tej energii. Zbieżność jest gwarantowana, ale może być powolna w pobliżu równowagi; wykres energii w rogu pokazuje charakterystyczny szybki początkowy spadek, po którym następuje długi ogon.

• 4 tryby gęstości: jednolity, promieniowy (skoncentrowany w centrum), gradient poziomy, malowany przez użytkownika
• Nakładka triangulacji Delaunaya (graf dualny do Voronoi)
• Kolorowanie według pola komórki (ujawnia jednorodność), indeksu komórki lub monochromatyczne
• Odchylenie standardowe pól komórek zbiega do zera

Co dalej

Fala 71 kontynuuje z iteracją potęgową PageRank (z poprawką dla węzłów wiszących), turniejem iterowanego dylematu więźnia Axelrod round-robin z 10 kanonicznymi strategiami, figurą Lichtenberga i przebiciem dielektrycznym przez solver Laplace'a SOR, strojeniem regulatora PID z autotuningiem Zieglera-Nicholsa, zasadą Archimedesa z dokładnymi wzorami objętości zanurzonej dla trzech kształtów kadłuba oraz wzrostem pęknięć zmęczeniowych według prawa Parisa z katastrofalnym pęknięciem przy K_IC.