Når man bygger en lille app, er det sjovt at arbejde med et problem, der findes uden for skærmen.
Et godt eksempel er tilskæring af trælister.
Forestil dig, at du skal bruge flere stykker træ i forskellige længder. Materialerne bliver leveret i standardlængder, men de færdige stykker skal passe til bestemte mål.
Hvordan fordeler du stykkerne, så du bruger færrest mulige hele lister?
Det spørgsmål kan vi arbejde med i JavaScript.
I denne tutorial bygger vi en simpel skæreliste-beregner. Vi bruger en algoritme, der hedder First-Fit Decreasing, og tager højde for materialet, som savbladet fjerner ved hvert snit.
Vi skal ikke bygge et professionelt produktionssystem. Målet er at lære en praktisk algoritme og forstå dens begrænsninger.
Problemet: Flere stykker fra én liste
Lad os sige, at en træbutik leverer lister i længder på 240 cm.
Vi skal bruge følgende stykker:
| Stykke | Længde |
|---|---|
| A | 120 cm |
| B | 95 cm |
| C | 80 cm |
| D | 70 cm |
| E | 50 cm |
Det samlede behov er 415 cm.
To standardlister giver i alt 480 cm.
Men kan vi faktisk fordele stykkerne på to lister?
Det afhænger af, hvordan vi kombinerer dem.
Vi skal også huske, at der forsvinder en lille mængde materiale, hver gang saven skærer.
I vores eksempel regner vi med 0,3 cm pr. snit.
Det er en forenklet antagelse. Det faktiske savsnit afhænger af det anvendte værktøj og den konkrete skæreproces.
1. Vælg en enkel algoritme
Vi bruger First-Fit Decreasing, ofte forkortet FFD.
Algoritmen arbejder i tre trin:
- Sortér stykkerne fra længst til kortest.
- Find den første eksisterende liste, hvor næste stykke kan være.
- Brug en ny liste, hvis stykket ikke passer i nogen af de eksisterende.
Det er en heuristik.
Den finder en brugbar løsning, men garanterer ikke altid det absolut mindste antal standardlister.
Det gør den stadig interessant til små beregningsprojekter.
2. Skriv vores JavaScript-funktion
Vi bruger centimeter som enhed.
Funktionen modtager:
- En liste med ønskede længder.
- Standardlistens længde.
- En antaget bredde for hvert savsnit.
Her er hele funktionen:
function planCuts(lengths, stockLength, kerf = 0.3) {
const validNumber = value =>
typeof value === "number" &&
Number.isFinite(value);
if (
!validNumber(stockLength) ||
stockLength <= 0 ||
!validNumber(kerf) ||
kerf < 0
) {
throw new Error("Ugyldig standardlængde eller savsnit.");
}
if (
!Array.isArray(lengths) ||
lengths.some(length =>
!validNumber(length) || length <= 0
)
) {
throw new Error("Alle ønskede længder skal være positive tal.");
}
const sorted = [...lengths].sort((a, b) => b - a);
const boards = [];
for (const length of sorted) {
const required = length + kerf;
if (required > stockLength) {
throw new Error(
`Stykket på ${length} cm passer ikke.`
);
}
let placed = false;
for (const board of boards) {
if (board.remaining + 1e-9 >= required) {
board.cuts.push(length);
board.remaining -= required;
placed = true;
break;
}
}
if (!placed) {
boards.push({
cuts: [length],
remaining: stockLength - required
});
}
}
return {
boards,
boardCount: boards.length,
totalRequired: lengths.reduce(
(sum, length) => sum + length, 0
),
totalKerf: lengths.length * kerf,
totalRemaining: boards.reduce(
(sum, board) => sum + board.remaining, 0
)
};
}
Lad os gennemgå nogle af de vigtigste dele.
Hvorfor sorterer vi først?
Denne linje placerer de længste stykker først:
const sorted = [...lengths].sort((a, b) => b - a);
Vi bruger [...lengths] for at oprette en kopi.
På den måde ændrer sorteringen ikke det oprindelige array.
Når de lange stykker bliver placeret først, får algoritmen bedre mulighed for at kombinere kortere stykker med den resterende plads.
Det giver ofte en god løsning, men er ikke et bevis for optimal udnyttelse.
Hvad gør remaining?
Hver standardliste gemmes som et objekt:
{
cuts: [120, 95],
remaining: 24.4
}
cuts indeholder længderne på de stykker, som er placeret på listen.
remaining viser den længde, der endnu ikke er brugt.
Når vi tilføjer et stykke, trækker vi både stykkets længde og det antagne savsnit fra.
const required = length + kerf;
Vi bruger altså et savsnit pr. færdigt stykke.
Det giver en enkel og lidt konservativ model. I praksis kan den faktiske mængde afhænge af, hvordan snittene udføres, og om eksisterende ender kan bruges.
3. Test beregningen
Nu bruger vi længderne fra vores eksempel.
const result = planCuts(
[120, 95, 80, 70, 50],
240,
0.3
);
console.log(result);
Algoritmen giver to standardlister.
Den første indeholder:
120 cm + 95 cm
Den anden indeholder:
80 cm + 70 cm + 50 cm
Med et antaget savsnit på 0,3 cm pr. stykke bliver resultatet:
| Beregning | Resultat |
|---|---|
| Antal standardlister | 2 |
| Samlet købt længde | 480 cm |
| Samlet færdig længde | 415 cm |
| Samlet savsnit | 1,5 cm |
| Resterende længde | 63,5 cm |
Tallene hænger sammen:
480 - 415 - 1,5 = 63,5 cm
Vi har nu en simpel beregner, der både fordeler stykkerne og viser, hvor meget materiale der er tilbage.
4. Gør resultatet nemmere at læse
Et objekt i konsollen er fint under udvikling.
Men vi kan gøre outputtet mere forståeligt.
function printCutPlan(result) {
console.log(
`Antal standardlister: ${result.boardCount}`
);
result.boards.forEach((board, index) => {
console.log(
`Liste ${index + 1}: ` +
board.cuts.join(" + ") +
` cm | Rest: ${board.remaining.toFixed(1)} cm`
);
});
console.log(
`Resterende materiale: ` +
`${result.totalRemaining.toFixed(1)} cm`
);
}
printCutPlan(result);
Outputtet bliver:
Antal standardlister: 2
Liste 1: 120 + 95 cm | Rest: 24.4 cm
Liste 2: 80 + 70 + 50 cm | Rest: 39.1 cm
Resterende materiale: 63.5 cm
Nu er resultatet mere anvendeligt.
Det er stadig en foreløbig beregning, men den viser en mulig fordeling af stykkerne.
5. Hvad sker der, hvis et stykke er for langt?
Vi skal også håndtere forkerte eller umulige input.
Prøv eksempelvis:
planCuts([250], 240, 0.3);
Funktionen kaster en fejl.
Det er med vilje.
Hvis et færdigt stykke skal være længere end standardlisten, kan vores algoritme ikke fremstille det fra den valgte længde.
Vi kan heller ikke automatisk antage, at flere korte stykker må samles til ét længere.
Det afhænger af den konkrete anvendelse og eventuelle krav til samlinger, styrke og funktion.
Derfor er det bedre at stoppe beregningen end at vise en skæreplan, der ikke kan udføres som forudsat.
6. Hvorfor er dette ikke en komplet skæreliste til byggearbejde?
Vi har lavet en matematisk model.
Den tager ikke højde for alle forhold ved fysisk tilskæring.
Eksempelvis mangler den:
Materialefejl
En standardliste kan indeholde skader eller andre forhold, som gør dele af den uegnede.
Retning og udseende
Træets åretegning eller produktets overflade kan påvirke, hvordan stykkerne bør skæres.
Endekapning
Nogle materialer kræver, at enderne bearbejdes før den endelige tilskæring.
Praktisk savning
Savtype, sikker fastspænding og arbejdsmetode kan påvirke, hvilke snit der er realistiske.
Forskellige materialekvaliteter
To lister med samme længde er ikke nødvendigvis udskiftelige, hvis de har forskellige egenskaber.
Konstruktive krav
Algoritmen vurderer ikke, om materialerne er egnede til bærende eller andre sikkerhedskritiske formål.
Beregneren skal derfor bruges som et læringsværktøj eller et tidligt planlægningshjælpemiddel.
Den erstatter ikke en fagligt kontrolleret skæreplan.
7. Hvorfor er problemet interessant for udviklere?
Det særlige ved dette eksempel er, at problemet findes i mange andre brancher.
Samme grundidé kan bruges til at undersøge fordeling af:
- Metalprofiler.
- Kabelstykker.
- Rør.
- Emballagematerialer.
- Andre produkter i faste længder.
Selve optimeringsproblemet kaldes ofte one-dimensional cutting stock.
Vores metode er en praktisk heuristik til dette problem.
Hvis vi vil forbedre programmet, kan vi undersøge andre algoritmer og sammenligne resultaterne.
Vi kunne for eksempel udvikle et testprogram, der prøver forskellige kombinationer og sammenligner det opnåede materialeforbrug.
Det ville gøre projektet mere interessant fra et algoritmisk perspektiv.
8. Fra kode til praktisk tømrerplanlægning
En digital beregning kan være nyttig, når man arbejder med gentagne mål og standardlængder.
Men det er vigtigt at kende grænsen mellem software og faglig vurdering.
Ved tømrerarbejde afhænger materialeforbruget ikke kun af længderne på de enkelte stykker.
Opmåling, træets egenskaber, fastgørelser og den eksisterende konstruktion kan ændre den endelige plan.
Tømrerfirmaet Cronberg ApS har base i Odense og arbejder med blandt andet gulve, døre, køkkenrenovering og andre træopgaver.
For boligejere, der undersøger et tømrerfirma i Odense, er det nyttigt at forstå, at materialeberegning kun er én del af planlægningen.
Den endelige løsning bør tage udgangspunkt i de faktiske mål og de tekniske krav til arbejdet.
Vores JavaScript-funktion kan give et overslag.
Den kan ikke fortælle, om en bestemt trædimension er korrekt til en bestemt konstruktion.
9. Idéer til næste version
Hvis du vil arbejde videre med koden, er der flere oplagte forbedringer.
Flere standardlængder
Lad brugeren vælge mellem eksempelvis 240, 300 og 360 cm.
Materialepris
Tilføj en pris pr. liste, så programmet kan beregne en foreløbig materialeomkostning.
Grafisk skæreplan
Vis hver standardliste som en vandret bjælke med farvede sektioner for hvert stykke.
CSV-eksport
Giv brugeren mulighed for at eksportere en oversigt over mål og beregninger.
Sammenligning af algoritmer
Undersøg, om en anden strategi giver færre standardlister eller mindre spild.
Automatisk test
Skriv testcases for blandt andet tomme arrays, ugyldige længder og situationer, hvor et stykke ikke kan være på en standardliste.
Det er især den sidste forbedring, der er interessant, hvis du bruger projektet til at øve softwareudvikling.
Et program skal ikke kun give det rigtige svar på ét eksempel.
Det skal også håndtere dårlige input og uventede situationer på en fornuftig måde.
Hvad har vi lært?
Vi har bygget en enkel JavaScript-beregner, som:
- Sorterer ønskede stykker efter længde.
- Fordeler dem på standardlister.
- Medregner en antaget savsnitsbredde.
- Beregner resterende materiale.
- Afviser ugyldige eller umulige input.
- Viser resultatet i et læsbart format.
Vi har også set, hvorfor en algoritme kan være matematisk nyttig uden at være en komplet løsning på et fysisk problem.
Det er en vigtig erfaring i softwareudvikling.
En god beregning kræver ikke kun korrekt kode. Den kræver også korrekte antagelser om virkeligheden.

Top comments (0)