РФГР: пошаговое вычисление на примере

Пример: "10x8F:0:2x3/4r,4x3,8x3,5x2/2"

Шаг 0: Парсинг

Лист 10×8, kerf=0.

Типы (ФГР не умеет вращение → фиксируем A как 2×3):

Тип	w	h	count	kₜ ∈
A	2	3	4	{0..4}
B	4	3	1	{0,1}
C	8	3	1	{0,1}
D	5	2	2	{0..2}

Подмножество D описывается кортежем (kA, kB, kC, kD). Всего: 5×2×2×3 = 60 подмножеств. Полное множество: (4,1,1,2).

Шаг 1: Определение ФГР

f(x; D) = минимальная высота полосы шириной x, в которую помещаются все детали из D гильотинными разрезами.

Представляем f как список точек излома [(x₁,h₁), (x₂,h₂), …]:

x₁ < x₂ < …, h₁ > h₂ > …
при x < x₁: f = ∞ (не помещается)
при x ∈ [xᵢ, xᵢ₊₁): f = hᵢ

Шаг 2: Базовые случаи (одна деталь каждого типа)

Подмножество	Шаговая функция	Смысл
`f(x; {A})`	`[(2, 3)]`	при x≥2 → h=3
`f(x; {B})`	`[(4, 3)]`	при x≥4 → h=3
`f(x; {C})`	`[(8, 3)]`	при x≥8 → h=3
`f(x; {D})`	`[(5, 2)]`	при x≥5 → h=2

Шаг 3: Операция H — горизонтальный разрез

Делим D = D₁ ∪ D₂, складываем две полосы одной ширины по вертикали:

f_H(x; D) = f(x; D₁) + f(x; D₂)   ← поточечное сложение

Пример: H-разрез {C} и {A}

f_H(x; {C,A}) = f(x;C) + f(x;A)
  x < 8:   ∞ + 3 = ∞    (C не лезет)
  x ≥ 8:   3 + 3 = 6
→ [(8, 6)]

Шаг 4: Операция V — вертикальный разрез

Делим D = D₁ ∪ D₂ вертикальным разрезом. Обе части имеют одинаковую высоту h, разные ширины.

Сначала вычислим квазиобратную f⁻¹(h; D) = минимальная ширина, нужная для D при высоте h:

Для V-разреза при высоте h: нужна суммарная ширина f⁻¹(h;D₁) + f⁻¹(h;D₂).

Если f(D) = [(x₁,h₁), (x₂,h₂), …], то:

f⁻¹(h; D) = x₁   если h₁ ≤ h   (самая большая ступень)
          = x₂   если h₂ ≤ h < h₁
          = ∞    если h < h_последняя
Напомним:
- x₁ < x₂ < x₃ < … < xₙ 
- h₁ > h₂ > h₃ > … > hₙ

Пример: V-разрез {C} | {A}

f⁻¹(h; C): h<3 → ∞, h≥3 → 8
f⁻¹(h; A): h<3 → ∞, h≥3 → 2

При h=3: ширина = 8+2 = 10
→ f_V(x; {C,A}) = [(10, 3)]

Итоговое f({C,A}) = min(H, V):

x ∈ [8,10):  H=6, V=∞  → 6
x ≥ 10:      H=6, V=3  → 3
→ f({C,A}) = [(8, 6), (10, 3)]

Шаг 5: Таблица ключевых подмножеств

Строим снизу вверх. Для каждого подмножества — min по всем разбиениям на D₁∪D₂.

{2A}:

H: 3+3=6 при x≥2 → [(2,6)]
V: f⁻¹(3;A)+f⁻¹(3;A)=2+2=4 → [(4,3)]
min: [(2,6),(4,3)]

{3A}:

Единственное разбиение: {A}+{2A}
H: x∈[2,4)→9, x≥4→6 → [(2,9),(4,6)]
V: f⁻¹(3;A)+f⁻¹(3;2A)=2+4=6 → [(6,3)]
min: [(2,9),(4,6),(6,3)]

{B,3A}:

Лучшее разбиение: {B}+{3A} (H) и {B}|{3A} (V)
H: x∈[4,6)→9, x≥6→6 → [(4,9),(6,6)]
V: f⁻¹(3;B)+f⁻¹(3;3A)=4+6=10 → [(10,3)]
min: [(4,9),(6,6),(10,3)]

Подмножество	x=4	x=6	x=8	x=10
`{A}`	3	3	3	3
`{B}`	3	3	3	3
`{C}`	∞	∞	3	3
`{D}`	∞	2	2	2
`{2A}`	3	3	3	3
`{3A}`	6	3	3	3
`{C,A}`	∞	∞	6	3
`{B,3A}`	9	6	6	3
`{2D}`	∞	4	4	2
`{4A,B,C}`	∞	∞	12	6
`{4A,B,C,2D}`	∞	∞	∞	8

Шаг 6: Финальное вычисление

{4A,B,C} — разбиение {C,A} + {B,3A}:

H: f({C,A})(x)+f({B,3A})(x)
- x∈[8,10): 6+6=12
- x≥10: 3+3=6
V при h=3: f⁻¹(3;{C,A})+f⁻¹(3;{B,3A})=10+10=20 → не помещается
→ [(8,12),(10,6)]

{2D} — разбиение {D}+{D} (H) и {D}|{D} (V):

H: 2+2=4 при x≥5 → [(5,4)]
V: 5+5=10 при h=2 → [(10,2)]
→ [(5,4),(10,2)]

Финал — H-разрез {4A,B,C} и {2D}:

f(10; ALL) = f({4A,B,C})(10) + f({2D})(10) = 6 + 2 = 8 ✓

Шаг 7: Итоговая раскладка

Три горизонтальных ряда (H-разрезы), внутри каждого ряда — V-разрезы:

Верх (h=2): D | D
Середина (h=3): B | A | A | A
Низ (h=3): C | A

РФГР: что добавляется

ФГР хранит только значение f(x; D). РФГР дополнительно хранит для каждой ячейки:

какое разбиение D₁/D₂ дало минимум
тип разреза (H или V)
для V: координата разреза x₁

Это позволяет восстановить полное дерево разрезов обходом от корня (4,1,1,2) вниз до одиночных деталей — и получить готовую карту раскроя.

FAQ

Как мы в РГФР в V-разрезе перешли от f⁻¹ к f?

● V-разрез шаг за шагом:

f → f⁻¹: для каждого subset имеем step-function f(D) = [(x₁,h₁),(x₂,h₂),…]. Инвертируем: f⁻¹(h;D) = минимальная ширина при высоте h.

f⁻¹(h; D) = xᵢ   где hᵢ — первый порог ≤ h
          = ∞    если h < h_last

Суммирование: для каждой кандидатной высоты h вычисляем суммарную ширину:

w(h) = f⁻¹(h; D₁) + f⁻¹(h; D₂)

f⁻¹ → f_V: кандидатные высоты — это объединение всех hᵢ из D₁ и D₂. Для каждой h (по убыванию) строим точку (w(h), h). Результат — step-function f_V:

   f_V(x; D) = h   если  w(h) ≤ x < w(h_prev)

Пример {C,A}:

h=3: w=8+2=10 → точка (10, 3)
h<3: один из f⁻¹=∞ → пропускаем
Итого: f_V = [(10, 3)]

Ключевое: кандидатные h — конечное множество (все порoги из обоих subsets), поэтому перебор прямолинейный. После перебора получаем готовую step-function в том же формате, что и f.

Графически можешь проиллюстрировать через ступенчатые функции? Интересует, как выглядит f и как f⁻¹. Также непонятно, мы переходим от f(D) к f(D₁) и f(D₂) или наоборот, от f(D₁) и f(D₂) - к f(D).

● Направление: от f(D₁) и f(D₂) → к f(D). DP снизу вверх — базовые случаи (одна деталь) → полный набор.

f(x; {C,A}) = [(8, 6), (10, 3)] — ширина полосы → минимальная высота:

f⁻¹(h; {C,A}) — доступная высота → минимальная ширина (квазиобратная):

Связь: точки излома (x=8, h=6) и (x=10, h=3) в f соответствуют точкам (h=6, w=8) и (h=3, w=10) в f⁻¹. Оси меняются местами — формы "транспонированы".

V-разрез {C} | {A}:

f⁻¹(h; C):   h ≥ 3 → w=8,   h < 3 → ∞
f⁻¹(h; A):   h ≥ 3 → w=2,   h < 3 → ∞
h=3: w(3) = 8 + 2 = 10  →  f_V({C,A}) = [(10, 3)]

H-разрез {C} + {A}:

f_H(x):  x ≥ 8 → 3+3 = 6  →  f_H({C,A}) = [(8, 6)]

Итог (min по обоим):

x ∈ [8,10):  min(H=6, V=∞)  = 6
x ≥ 10:      min(H=6, V=3)  = 3
→ f({C,A}) = [(8, 6), (10, 3)]

Почему достаточно рассматривать их, а не все комбинации подмножеств? Почему tuple (kA, kB, kC, kD), а не 2^n подмножеств?

Детали одного типа неразличимы. Не важно, какие именно 2 из 4 штук A попали в субрегион — важно только сколько. Поэтому состояние = кол-во каждого типа.

Без группировки по типам: 2^(4+1+1+2) = 256 вариантов
С группировкой: 5×2×2×3 = 60 вариантов

Для реальных задач (много деталей, мало типов) выигрыш огромный.

Как выделяются ключевые подмножества?

"Ключевые" подмножества — не отбор заранее. DP считает все 60 подмножеств, снизу вверх. В туториале показаны только те, что попали на оптимальный путь декомпозиции от корня (4,1,1,2) до листьев (отдельные детали):

(4A,B,C,2D)
├── (4A,B,C)      ← f = [(8,12),(10,6)]
│       ├── (C,A)     ← f = [(8,6),(10,3)]
│       └── (B,3A)    ← f = [(4,9),(6,6),(10,3)]
└── (2D)          ← f = [(5,4),(10,2)]

Остальные 49 субнаборов посчитаны, но на оптимальном дереве не оказались.

Сколько разбиений внутри одного подмножества?

Для подмножества (kA, kB, kC, kD) разбиение D = D₁ ∪ D₂ означает выбрать для каждого типа, сколько отдать в D₁:

разбиений = (kA+1)(kB+1)(kC+1)(kD+1) / 2 (делим на 2: D₁↔D₂ симметрично)

Для полного набора (4,1,1,2): 5×2×2×3/2 = 30 разбиений, каждое проверяется в H и V вариантах. Берём min по всем.

nlinker/gpf_step1.svg

Select an option

No results found