Har ett klurigt (?) problem som jag inte lyckas ställa upp riktigt. Säg att jag har ett antal rör i olika längder, exempelvis 2, 5 och 8 meter långa. Sedan ska jag sätta ihop ett rör med en total längd av 28 meter.
Vad jag vill få fram nu är hur många rör jag behöver av varje längd för att uppnå minsta möjliga spill (närmast över om man inte kan få ut det exakt). Dessutom, ett 6 meter långt rör är att föredra framför 2*3-metersrör.
Svaret ovan skulle alltså bli 3*8 rör samt 2*2 rör, enkelt att räkna ut i huvudet med dessa enkla mått förstås. Men om man har 7 olika knepiga längder med decimaler och ska ha en längd på 13455 meter, inte lika lätt.
Går det att ställa upp detta mha en fiffig algoritm?
För övrigt skulle inte webforum kunna ha ett matematik-forum? Det ligger ju väldigt nära ämnet tycker jag och här finns säkert många som är duktiga på matematik och logik! :q
Går det att ställa upp detta mha en fiffig algoritm?
Ja, ställ upp en diofantisk ekvation och använd dig av Euklides algoritm för att hitta en lösning. Höjer dock ett finger för att det kan tänkas finnas flera lösningar på just ditt exempel.
Edit, stavfel.
Jo, man vet alltså längderna på varje enskilt rör och hur långt rör man ska sätta ihop... det jag behöver veta är hur många rör av de olika längderna man behöver för minsta spill!
Jo, man vet alltså längderna på varje enskilt rör ...
Ja, du vet men vi vet inte! Om längderna är 1,2,4,8,16,32,64 så vore problemet lätt men om de är 2,3,5,7,11,13,17 så är det inte lika uppenbart hur algoritmen ser ut, så de verkliga längderna kan vara av intresse om man vill ha en rimligt enkel algoritm.
Jo, man vet alltså längderna på varje enskilt rör och hur långt rör man ska sätta ihop... det jag behöver veta är hur många rör av de olika längderna man behöver för minsta spill!
Okej, vad är det du inte förstår då? Har du intelärt dig diofantiska ekvationer i skolan?
Då är det kanske något så här enkelt du är ute efter.
Psudokod för att generera en plocklista.
KvarAttBygga = Totalängd
För varjae rörlängd (ordnade från längsta till kortaste)
l = aktuella längden
n = max antal av enheten utan att överskrida KvarAttBygga
KvarAttBygga = KvarAttBygga - n * l
notera n och l i plocklistan
tills man gått igenom all längder
Om KvarAttBygga > 0
lägg till en enhet av den kortaste typen
uppdatera plocklistan
spill = längd av kortaste röret - KvarAttBygga
notera spill plocklistan
annars
spill = 0
notera spill plocklistan
Presentera plocklistan
Tänk, jag trodde det fanns algoritmer för allt... :)
Bara du har en modell så finns det en algoritm. :-)
Modellen måste då innehålla en möjlighet att kunna göra en jämförelse mellan "kostnad för extra skarvar" med "kostnad för spill" (förmodligen relativt totallängden och totala antalet skarvar).
Som exempel
du har har längderna 1 och 3 och skall leverera totallängden 2
du har har längderna 1 och 10 och skall leverera totallängden 9
du har har längderna 1 och 100 och skall leverera totallängden 99
Det är förmodligen, men inte uppenbart sant, bara i första fallet som den rena "Mindre spill än minsta rörlängd" algoritmen ovan är den bästa.
Tack i2n2, det får bli något sådant istället! Tänk, jag trodde det fanns algoritmer för allt... :)
Jo alltså, det finns väldokumenterade lösningssätt, men du tycks ju inte ta till dig det jag skriver. Då är det klart att du upplever det som att det inte finns algoritmer/lösningssätt för den typ av problem du beskriver.
überfuzz, du kan inte använda euklides algoritm för att hitta en lösning på det problemet - i och med att det inte är en diofantisk ekvation (det är för många obekanta).
Var det bara jag som inte kunde stå emot driften och faktiskt skriva ett program som löste det här problemet? :)
Jag har mest tänkt på hur många frågor om förutsättningarna som kan finnas som skulle ge olika lösningar. T.ex.
Vad är de verkliga optimeringsvillkoren.
Värdering av spill/skarv "kostnad" enligt ovan.
Variationer på kortaste tillgängligt rör och minsta enhet vid beställning.
Vad är spill, kan det eller delar därav återanvändas vid nästa beställning.
Dvs som vanligt, när man verkligen formulerat sitt problem så är man mycket närmare lösningen på detta.
För att återgå till rubriken så funderade jag lite på om det finns något intressant matematisk problem som ligger i närheten som är NP-fullständigt (utan att komma på något).
Detta kan lösas med vanlig linjärprogrammering tillsammans med till exempel cutting-plane för att erhålla en heltalslösning.
Kort MATLAB-kod med YALMIP som löser problemet:
L = [7 11 13 17];
wanted = 451;
n = length(L);
x = intvar(1,n);
constraint = [sum(x.*L) >= wanted; ...
x >= 0];
solvesdp(constraint,sum(x.*L));
x = double(x);
x
sum(x.*L)
Då är det kanske något så här enkelt du är ute efter.
Jag vet inte om det var ditt syfte, men din algoritm ger inte alltid den optimala lösningen. Tex. Längderna 2 och 9, med önskad längd 10. Din algorithm kommer då ge svaret 9 och 2, istället för 5*2.
Jag vet inte om det var ditt syfte, men din algoritm ger inte alltid den optimala lösningen. Tex. Längderna 2 och 9, med önskad längd 10. Din algorithm kommer då ge svaret 9 och 2, istället för 5*2.
Ok, det är ju en dålig egenskap för mitt förslag till algoritm (som jag väl aldrig sagt att det är en korrekt lösning)
Din lösning, hanterar väl inte det villkor som inspiro ställde att, i dina beteckningar, sum(x_i) också skall minimeras (så få skarvar som möjligt) eller är det jag som bör läsa på lite om MATLAB som jag tyvärr aldrig haft möjligheten att arbeta med.
Din lösning, hanterar väl inte det villkor som inspiro ställde att, i dina beteckningar, sum(x_i) också skall minimeras (så få skarvar som möjligt) eller är det jag som bör läsa på lite om MATLAB som jag tyvärr aldrig haft möjligheten att arbeta med.
Nej, det är riktigt. Som det ser ut ovan minimeras bara den överskjutande delen. Om man dessutom vill minimera antalet skarvar kommer målfunktionen se ut som:
sum(x.*L) + lambda*sum(x)
där lambda är ett litet, positivt tal, så litet att det inte kan få den överskjutande delen att bli längre. Detta funkar fint.
252 ms totalt · 4 externa anrop · v20260731065814-full.e96017d9
