[PHP] Algoritme voor optimale ruimtebenutting

[NeilForeal]

Hoi Tweakers,

Ik ben mijn hoofd aan het breken op een leuk wiskundig probleem. Ik wil het graag oplossen met PHP, maar ik krijg een uitwerking nog niet op papier. Het probleem is als volgt:

Er is sprake van een totale hekbreedte. Voor het voorbeeld even 5000mm.

Daarnaast zijn er 4 hekelementen. Een element van 488mm, 1022mm, 1286mm en 1552mm.

Nu moet ik een programma schrijven dat de optimale benutting van de 5000mm aangeeft in hekelementen. Alle mogelijkheden moeten gechecked worden. Dat zijn er dus VEEL!

Er is daarnaast ook sprake van tussenpalen van 40mm. De berekening daarvan moet bij de oplossing worden opgeteld, en moet BINNEN de 5000mm vallen. Bij 10 elementen zijn de tussenpalen dus 11 x 40mm = 440mm.

Voorbeeld uitwerking

code:

<?php
$totaal_hek = 5000;

$tussenpaal = 40;
$element1 = 448;
$element2 = 1022;
$element3 = 1286;
$element4 = 1552;

Bij 5000mm is het maximale aantal elementen als volgt te bereken:

$max_elementen = ($totaal_hek - $tussenpaal) / ($element1 + $tussenpaal);
$max_elementen_afgerond = ceil($max_elementen);
?>

Voor het minimaal aantal elementen kan hetzelfde worden gedaan, maar dan met element 4. Dan hebben we dus een min en max. Maar ALLE mogelijkheden die ertussen zitten moeten ook berekend worden. Daar moet een lijst uitkomen waar wij dan zelf de meest ideale oplossing uit kunnen halen.

Ik zat aan iets te denken als:

code:

<?php
$maxel = 1
while($maxel <= $max_elementen_afgerond){
    // Rekenen met maxel 11
        while($hek < $totaal_hek){
            // Ingewikkelde berekening, etc
        }
    $maxel++;
}
?>

Resultaat
Het uiteindelijk resultaat moet dus een lijst zijn met alle mogelijkheden voor de opgegeven minimale heklengte, met als grensen het minimale en maximale aantal elementen (om een infinite loop te voorkomen).

Welk geniaal brein kan mij helpen met het oplossen van dit probleem?

Very much appreciated.

[Janoz]

Het aantal mogelijkheden valt anders nog best wel mee en met een simpele brutforce kun je zo alle benodigde configuraties bij langs.

Gebruik gewoon een recursieve functie die een overgebleven lengte neemt en daar dan alle hekken achter zet incl de paal. Is de lengte van dat hek plus de paal gelijk aan de overgebleven lengte, dan druk je de configuratie af/voeg je hem toe aan de lijst. Is die lengte langer dan de overgebleven lengte dan doe je niks en is de lengte korter dan de overgelbeven lengte dan reken je de nieuwe overgebleven lengte uit en roep je de functie met de nieuwe overgebleven lengte aan.

Al dat gepiel met minimaal en maximaal aantal elementen is niet nodig. Zolang je geen paal breedte van 0 hebt en 1 hek met breedte 0 zal de overgebleven lengte altijd kleiner worden en zal je dus nooit in een infinite loop terecht komen.

[ Voor 18% gewijzigd door Janoz op 16-03-2010 14:28 ]

[Verwijderd]

Als elk hek een paal heeft dan kan je beter een segment (paal+hek) gebruiken:

$segment1 = $lengtehek1 + $paal

de afstand die je segmenten dan moeten dekken is de lengte van je hek - de laatste paal

ofwel

$spacetofill = $totaal_hek - $paal


Dit maakt je probleem als weer een stapje overzichtelijker.
----

Begrijp ik het goed als je dan een lijst wilt met alle mogelijkheden die binnen de opgegeven lengte passen?

1x 488 (+40) =< 5000(-40) ..... wil je dit soort resultaten (dus 2 palen met een klein hek) ook meenemen?

[SLeddert]

Gewoon doen wat de bovenstaande poster al meldt: $spacetofill = $totaal_hek - $paal

Alle opties recursive aflopen en de optie met de beste combinatie onthouden (en bij een betere optie weer vervangen)

[sjorsjuhmaniac]

NeilForeal schreef op dinsdag 16 maart 2010 @ 14:15:

Er is daarnaast ook sprake van tussenpalen van 40mm. De berekening daarvan moet bij de oplossing worden opgeteld, en moet BINNEN de 5000mm vallen. Bij 10 elementen zijn de tussenpalen dus 11 x 40mm = 440mm.

Voorbeeld uitwerking

code:

<?php
$totaal_hek = 5000;

$tussenpaal = 40;
$element1 = 448;
$element2 = 1022;
$element3 = 1286;
$element4 = 1552;

Bij 5000mm is het maximale aantal elementen als volgt te bereken:

$max_elementen = ($totaal_hek - $tussenpaal) / ($element1 + $tussenpaal);
$max_elementen_afgerond = ceil($max_elementen);
?>

Voor het minimaal aantal elementen kan hetzelfde worden gedaan, maar dan met element 4. Dan hebben we dus een min en max. Maar ALLE mogelijkheden die ertussen zitten moeten ook berekend worden. Daar moet een lijst uitkomen waar wij dan zelf de meest ideale oplossing uit kunnen halen.

De max die je zo uitrekend komt in totaal over de lengte van totaal_hek en je zegt zelf dat het een voorwaarde is dat alles binnen die waarde moet vallen

Janoz zijn suggestie is eenvoudig uit te voeren met behulp van de modulus.
http://php.net/manual/en/language.operators.arithmetic.php

[steffex]

wil je ook rekening houden met minimale element grootte? wat mag de verdeling zijn van de elementen (wil je dat alle elementen zo gelijk mogelijk verdeeld zijn? of mag het laatste element aanzienlijk kleiner zijn?)?

dit zijn allemaal dingen waar je eerst over na wil denken, want bij sommige getallen lijkt het misschien dat het mooi uitkomt, maar je kan dus ook andere waardes krijgen waardoor de uitkomst dan totaal niet naar wens is.

Als je voor jezelf helemaal duidelijk hebt wat de randvoorwaarden zijn, dan kun je dit pas goed gaan omzetten naar een stuk code.

het is in mijn ogen nog net te vaag om je de goede richting in te helpen...

[ Voor 6% gewijzigd door steffex op 16-03-2010 15:02 ]

[Janoz]

@stef-o: Grappig. Je verzint er zelf een aantal extra requirements bij (gelijk verdeeld en/of moetook leuk ogen). Concludeert dat die requirements niet in de startpost staan en zegt vervolgens dat het te vaag is .

Opdracht in de topicstart is imho duidelijk zat (alhoewel de enige kanttekening die nog geplaatst zou kunnen worden is dat er misschien best een beetje speling in de totale breedte zou kunnen zitten. Iets smaller zou in de praktijk ook wel mogen, zeker wanneer er geen exacte oplossing mogelijk is). Alle requirements die jij stelt worden eigenlijk al afgedekt doordat uit de gegenereerde lijst door de gebruiker een keuze gemaakt wordt.

[NeilForeal]

Ik zal het proberen nog iets toe te lichten

Bovenstaande formule is inderdaad net iets makkelijker, maar nog lang niet volledig.

Het gewenste resultaat geeft binnen de totale breedte ALLE mogelijkheden.

Mogelijkheden kunnen zijn:
10 x element1
8 x element 1, 1 x element 2
4x element 3, 2 x element 1
5 x element 3, 1 keer element 4
etc etc etc

Dat zijn er dus honderden. Ik krijg het niet voor elkaar daar een logische formule voor te schrijven.

Update
Overigens hoeft het ook niet precies te passen. Te klein kan niet, iets groter wel. Een hek kan inmiddels wel iets vanaf, maar niet iets bij. Hij moet gewoon via een bepaalde volgorde elementen gaan plaatsen, net zolang tot het over de 5000 is in dit geval.

Je krijgt dus honderden mogelijkheden van elementcombinaties die allemaal net iets over de 5000mm zijn (of misschien precies 5000).

[ Voor 30% gewijzigd door NeilForeal op 16-03-2010 15:57 ]

[Janoz]

NeilForeal schreef op dinsdag 16 maart 2010 @ 15:39:
Ik zal het proberen nog iets toe te lichten

Bovenstaande formule is inderdaad net iets makkelijker, maar nog lang niet volledig.

Het gewenste resultaat geeft binnen de totale breedte ALLE mogelijkheden.

Mogelijkheden kunnen zijn:
10 x element1
8 x element 1, 1 x element 2
4x element 3, 2 x element 1
5 x element 3, 1 keer element 4
etc etc etc

Ik begrijp hier even niet wat je met gewenst resultaat bedoeld. Ik neem aan dat het lijstje wat je hier opsomt niet de gewenste resultaten zijn aangezien ze niet een totale breedte hebben van 5000mm.

Dat zijn er dus honderden. Ik krijg het niet voor elkaar daar een logische formule voor te schrijven.

honderden mogelijkheden doorrekenen is voor een computer natuurlijk peanuts. Je moet iig af van het idee dat je daar een formule voor kunt schrijven. Die is er namelijk niet. Mij lijkt toch echt de recursieve functie de meest voor de hand liggende oplossing. Zoek daar eens op op google.

[pedorus]

NeilForeal schreef op dinsdag 16 maart 2010 @ 15:39:
4x element 3, 2 x element 1
5 x element 3, 1 keer element 4

Dat zijn er dus honderden. Ik krijg het niet voor elkaar daar een logische formule voor te schrijven.

Na 4x element 3 heb je de lengte toch al, waarom zou je dan doorgaan? Verder: Ik tel er maar 39?

spoiler:

function printpossibilities($remaining, $parts, $starttext='', $minused=PHP_INT_MAX) {
    $max = (int) (($remaining - 1) / $parts[0] + 1);
    if (count($parts)==1) {
        if (-($remaining - $parts[0] * $max) < $minused)
            echo "$starttext-$max\n";
    } else {
        printpossibilities($remaining, array_slice($parts, 1), "$starttext-0", $minused);
        for ($i = 1; $i <= $max; $i++)
            printpossibilities($remaining - $parts[0] * $i, array_slice($parts, 1),
                 "$starttext-$i", min($minused, $parts[0]));
}}
printpossibilities(4960, array(528, 1062, 1326, 1592));

[Leonardo123]

@pedorus, jou oplossing lijkt mij niet geheel correct, aangezien de oplossing 10-0-0-0 erin voorkomt.
Dat patroon is niet geldig gezien [528, 1062, 1326, 1592] * [10, 0, 0, 0]' = 5280, welk groter is dan 4860.

Verder kun je het genereren van de patronen ook niet recursief aanpakken. Dit door uit te gaan van een set van nog geldige oplossingen en daar systematisch elementen aan toe te voegen.
Hier is wat matlab code welk het demonstreerd.
maxUsage = 4860
sizes = [528, 1062, 1326, 1592]'

code:

function [A, c] = calculatePatterns(maxUsage, sizes)

length = size(sizes,1);
pattern = zeros(length, 1);
A = pattern;
sizesInv = sizes';
c = maxUsage - sizesInv * pattern;

for i=1:length
    
    newPatterns = [];
    
    for v=1:size(A, 2)
        currentPattern = A(:, v);
        currentPattern(i) = currentPattern(i) + 1;
        usage = sizesInv * currentPattern;
        
        while(usage <= maxUsage)
            newPatterns = [newPatterns currentPattern];
            c = [c (maxUsage - usage)];
            
            currentPattern(i) = currentPattern(i) + 1;
            usage = sizesInv * currentPattern;
        end
    end
    
    A = [A newPatterns];
end

Daarbij krijg je dan een array A welk alle geldige patronen bevat (dit zijn er 89) en een vector c welk het overschot bevat. Dat overschot wil je uiteraard minimalizeren.

Mocht ik iets stoms gezecht hebben, of heb je een verbetering voor de matlab code, dan hoor ik het graag.

[pedorus]

Leonardo123 schreef op dinsdag 16 maart 2010 @ 20:26:
@pedorus, jou oplossing lijkt mij niet geheel correct, aangezien de oplossing 10-0-0-0 erin voorkomt.
Dat patroon is niet geldig gezien [528, 1062, 1326, 1592] * [10, 0, 0, 0]' = 5280, welk groter is dan 4860.

Die 8 in 4860 was een tikfout, en moest 9 zijn (oplossingen blijven gelijk). Overigens valt uit de TS niet helemaal op te maken of het 488 of 528 moet zijn. Daarnaast:

NeilForeal schreef op dinsdag 16 maart 2010 @ 15:39:
Overigens hoeft het ook niet precies te passen. Te klein kan niet, iets groter wel. Een hek kan inmiddels wel iets vanaf, maar niet iets bij. Hij moet gewoon via een bepaalde volgorde elementen gaan plaatsen, net zolang tot het over de 5000 is in dit geval.

Oftwel: groter mag wel, kleiner niet. Je genereert nu alle 89 oplossingen die kleiner zijn (ook in jouw geval maakt die tikfout niet uit), dus dat lijkt me niet correct. Verder heeft een niet-recursieve oplossing ook in php de voorkeur, maar dat was wat meer tik-/denkwerk. En in weze blijft het achterliggende concept recursie, enkel is het dan anders uitgeschreven.

Mocht ik iets stoms gezecht hebben

offtopic:
Precies daar

[roy-t]

Als je dit sem-bruteforce maar wel efficient wilt oplossen kun je eens kijken naar dynamic programming, maar misschien is er ook wel een heuristiek te bedenken die werkt (denk het niet, dit lijkt haast een knapsack probleem).

[Verwijderd]

Als ik 't goed begrijp is dit ongeveer wat je zoekt als resultaat?

mbGH:~ guido$ php /srv/www/hekken.php
1552*4 => -1408, 
1552*3 => 184, 1286*1 => -1142, 
1552*3 => 184, 1022*1 => -878, 
1552*3 => 184, 448*1 => -304, 
1552*2 => 1776, 1286*2 => -876, 
1552*2 => 1776, 1286*1 => 450, 1022*1 => -612, 
1552*2 => 1776, 1286*1 => 450, 448*1 => -38, 
1552*2 => 1776, 1022*2 => -348, 
1552*2 => 1776, 1022*1 => 714, 448*2 => -262, 
1552*2 => 1776, 448*4 => -176, 
1552*1 => 3368, 1286*3 => -610, 
1552*1 => 3368, 1286*2 => 716, 1022*1 => -346, 
1552*1 => 3368, 1286*2 => 716, 448*2 => -260, 
1552*1 => 3368, 1286*1 => 2042, 1022*2 => -82, 
1552*1 => 3368, 1286*1 => 2042, 1022*1 => 980, 448*3 => -484, 
1552*1 => 3368, 1286*1 => 2042, 448*5 => -398, 
1552*1 => 3368, 1022*4 => -880, 
1552*1 => 3368, 1022*3 => 182, 448*1 => -306, 
1552*1 => 3368, 1022*2 => 1244, 448*3 => -220, 
1552*1 => 3368, 1022*1 => 2306, 448*5 => -134, 
1552*1 => 3368, 448*7 => -48, 
1286*4 => -344, 
1286*3 => 982, 1022*1 => -80, 
1286*3 => 982, 448*3 => -482, 
1286*2 => 2308, 1022*3 => -878, 
1286*2 => 2308, 1022*2 => 184, 448*1 => -304, 
1286*2 => 2308, 1022*1 => 1246, 448*3 => -218, 
1286*2 => 2308, 448*5 => -132, 
1286*1 => 3634, 1022*4 => -614, 
1286*1 => 3634, 1022*3 => 448, 448*1 => -40, 
1286*1 => 3634, 1022*2 => 1510, 448*4 => -442, 
1286*1 => 3634, 1022*1 => 2572, 448*6 => -356, 
1286*1 => 3634, 448*8 => -270, 
1022*5 => -350, 
1022*4 => 712, 448*2 => -264, 
1022*3 => 1774, 448*4 => -178, 
1022*2 => 2836, 448*6 => -92, 
1022*1 => 3898, 448*8 => -6, 
448*11 => -408, 

Met een simpel stukkie PHP:

PHP:

$totaal = 5000;
$tussenpaal = 40;
$totaal -= $tussenpaal; // de "beginpaal" eraf... :9

$hekken[] = 1552;
$hekken[] = 1286;
$hekken[] = 1022;
$hekken[] = 448;

function hekken($resterend, $hekken, $tussenpaal, $result = '')
{
    if ($resterend > 0)
    {
        $num = count($hekken);
        for ($i = 0; $i < $num; $i++)
        {
            $hek = array_shift($hekken);
            for ($x = ceil($resterend / ($hek+$tussenpaal)); $x > 0; $x--)
            {
                $newResult = $result.$hek.'*'.$x.' => '.($resterend - ($hek + $tussenpaal) * $x).', ';
                hekken($resterend - ($hek + $tussenpaal) * $x, $hekken, $tussenpaal, $newResult);
            }
        }
    }
    else
    {
        echo $result.PHP_EOL;
    }
}
hekken($totaal, $hekken, $tussenpaal);

Het is toch geen schoolopdracht he?

offtopic:
Ah, jij bent 't...

[ Voor 92% gewijzigd door Verwijderd op 16-03-2010 23:08 ]

[pedorus]

@GuidoH: je telt een 'tussenpaal' te weinig waardoor je niet dezelfde resultaten krijgt als ik (9-1-0-0 ipv 8-1-0-0). Vreselijk die Nederlandse namen

[Verwijderd]

pedorus schreef op dinsdag 16 maart 2010 @ 22:36:
@GuidoH: je telt een 'tussenpaal' te weinig waardoor je niet dezelfde resultaten krijgt als ik (9-1-0-0 ipv 8-1-0-0). Vreselijk die Nederlandse namen

Ik zie 't, vergeet de "beginpaal". Maar wat bedoel je met 9-1-0-0?
Haha, eigenlijk wel he. Maar ze kunnen erger, heb nu nog niet Engels en Nederlands door elkaar heen volgens mij...

[Soundless]

Ik dnek dat pedorus bedoelt dat je een tussenpaal te veel hebt

hekken($totaal + $tussenpaal, $hekken, $tussenpaal);

[Leonardo123]

Ik zag het probleem meer als een vorm van de cutting stock problem, waar je niet over de maximum waarde heen mag gaan, aldus zijn al mijn gegenereerde oplossingen onder dat maximum. Wel zou je met dezelfde code maar met een ander maximum alsnog alle gewenste oplossingen kunnen berekenen.

[Verwijderd]

Soundless schreef op dinsdag 16 maart 2010 @ 23:32:
Ik dnek dat pedorus bedoelt dat je een tussenpaal te veel hebt

hekken($totaal + $tussenpaal, $hekken, $tussenpaal);

Lijkt me niet...
Bij elk hek dat er toegevoegd wordt:

code:

hekken($resterend - ($hek + $tussenpaal) * $x, $hekken, $tussenpaal, $newResult);

Gaat er een hek en een tussenpaal af, dus de eindpaal heb je ook al automatisch. Dan krijg je alleen nog een paal aan het begin die er mist. Tenminste, ga er van uit dat je aan het begin en eind een paal nodig hebt?

Wel grappig zulke dingen, zijn er geen sites met heel veel van zulke "problemen"? edit: utfg!

offtopic:
Pedorus, lekkere naam heb jij zeg, ga er maar even van uit dat je geen Rus bent?

[Soundless]

ik ging er juist vanuit dat tussenpalen alleen tussen de hekken horen en niet op het begin/eind (vandaar de naam 'tussenpaal' dacht ik dus)

en anders doe je dus gewon hetzelfde maar dan met een -

(bedtijd)

[Verwijderd]

Soundless schreef op woensdag 17 maart 2010 @ 00:29:
ik ging er juist vanuit dat tussenpalen alleen tussen de hekken horen en niet op het begin/eind (vandaar de naam 'tussenpaal' dacht ik dus)

en anders doe je dus gewon hetzelfde maar dan met een -

(bedtijd)

Tja, had ook gekund. Dat doe ik al bovenaan nu.

[pedorus]

Verwijderd schreef op woensdag 17 maart 2010 @ 00:04:
[...]

Lijkt me niet...

Als je een aparte 'beginpaal' hebt, dan zou je toch verwachten dat je ook een 'eindpaal' hebt, en de palen ertussenin zijn dan 'tussenpalen'. Je ziet nu de 'eindpaal' als 'tussenpaal', dus de naamgeving klopt niet. Dit is natuurlijk afhankelijk van waar het hek precies komt te staan.

offtopic:
Pedorus, lekkere naam heb jij zeg, ga er maar even van uit dat je geen Rus bent? [afbeelding]

offtopic:
Al zou je het zo afbreken, dan meet een pedometer zeker in hoeverre je pedofiel bent?

[Verwijderd]

pedorus schreef op woensdag 17 maart 2010 @ 00:39:
[...]

Als je een aparte 'beginpaal' hebt, dan zou je toch verwachten dat je ook een 'eindpaal' hebt, en de palen ertussenin zijn dan 'tussenpalen'. Je ziet nu de 'eindpaal' als 'tussenpaal', dus de naamgeving klopt niet. Dit is natuurlijk afhankelijk van waar het hek precies komt te staan.

Tja, kan allebei, had eerst alleen aan het eind een paal en aan het begin niet. Zie dat jij dat ook hebt, maar goed, zijn details he..

[Soultaker]

En als je een rond hek bouwt heb je een begin- noch eindpaal.

Re: TS: de twee zinnige opties lijken me of door middel van dynamic programming een optimale oplossing genereren, of een ad-hoc algoritme implementeren (zoals recursief combineren) als je problemen niet al te ingewikkeld zijn, en je de verschillende opties toch nog handmatig wil nakijken.

[ Voor 10% gewijzigd door Soultaker op 17-03-2010 01:27 ]

[Verwijderd]

Soultaker schreef op woensdag 17 maart 2010 @ 01:26:
En als je een rond hek bouwt heb je een begin- noch eindpaal.

Dan was mijn eerste oplossing goed, daar had ik geen beginpaal en was de "eindpaal" een tussenpaal.

[NeilForeal]

Veel reacties! Goed om te zien Het is geen schoolopdracht al heeft het er in de verte wel iets mee te maken. Het is een case voor een bedrijf waar ik momenteel stage loop. Die moeten alle orders handmatig verwerken en berekenen, en ze waren benieuwd of ik dat slimmer kon oplossen.

Ik kwam er zelf niet helemaal uit, vandaar het topic.

Mensen geven een maat op, en het script moet uitrekenen welke mogelijkheden er zijn om die ruimte vol te krijgen met de 4 verschillende hekken. Mijn voorbeelden uit de vorige post waren niet berekend, was puur ter illustratie.

Binnen 5 meter moet je dus niet uitkomen op een heklengte van 4.9m, dat gaat niet passen. Ideaal zou zijn precies 5 meter, of 5.1, 5.01 etc. Zo dicht mogelijk bij de 5, maar dan niet korter.

Het script moet dus uitrekenen welke mogelijkheden er zijn met alle hekcombinaties binnen het opgegeven aantal meters. Guido, ik begrijp dat jouw script dat doet?

[ Voor 0% gewijzigd door NeilForeal op 17-03-2010 10:24 . Reden: typo ]

[Bolukan]

Dan zou je ook de prijzen moeten tellen, en een penalty voor het extra werk als je niet precies uitkomt en de kosten van het in de grond meppen van een paaltje. Dan kun je uit de 39 oplossingen uit het voorbeeld, ook de goedkoopste selecteren.

[Janoz]

Volgens mij zijn er in dit topic al legio beschrijvingen van algorithmen en handvatten om dit op te pakken langs gekomen. Het toevoegen van een marge lijkt mij dan ook niet een heel groot probleem. Wat begrijp je precies niet aan de gegeven handvatten als :
Recursief combineren
Dynamisch programmeren

Dat je uit wilt zoeken hoe dit werkt vind ik geen probleem, het is hier echter niet de bedoeling dat de oplossing compleet voorgekauwd moet worden.

[dwilmer]

[nerd-modus]
Dit is zo te zien een NP-probleem. Voor dit specifieke probleem kun je het best een pseudo-polynomiaal algoritme gebruiken
[/nerd-modus]

Je beste oplossing ligt bij recursie of (in de praktijk iets sneller) Dynamisch programmeren. Met wikipedia zou je al een heel eind moeten komen, google doet de rest.

Nog een tip hierbij: Dynamisch programmeren is pseudo-polynomiaal. Dat houdt in dat het langer duurt als je er grotere getallen in stopt. Nu valt het nog wel mee met het voorbeeld dat jij geeft, maar zodra het (te) lang gaat duren kan het helpen om af te kappen op centimeters ipv millimeters. Daar zou het wel eens tien keer sneller van kunnen gaan (in ieder geval theoretisch, ik weet niet hoe het praktisch zit).

[ Voor 1% gewijzigd door dwilmer op 17-03-2010 10:56 . Reden: iets beter formulering in nerd-modus ]

[NeilForeal]

@Janoz

Daar heb je uiteraard helemaal gelijk in. Ik zit momenteel hard te stoeien met het script, ben al een stuk verder door jullie hulp. Het is even een bepaalde manier van denken, miste zelf net even wat linkjes hier en daar. Zodra ik een definitief werkend script heb post ik het wel even hier voor de geïnteresseerden.

[Ram0n]

Ik heb een soortgelijk probleem (op veel grotere schaal) ooit aangepakt zien worden met een Evolutionary Strategy, na veel tests kwamen daar de beste resultaten uit.

[Voutloos]

Ram0n schreef op woensdag 17 maart 2010 @ 15:11:
Ik heb een soortgelijk probleem (op veel grotere schaal) ooit aangepakt zien worden met een Evolutionary Strategy, na veel tests kwamen daar de beste resultaten uit.

De recursieve aanpak (bijvoorbeeld) levert alle resultaten op, dus ook deze 'beste resultaten'. Blijkbaar scoort je evolutionaire algoritme op een ander criterium goed (exec tijd of ontwikkeltijd) maar voor dit specifieke geval betwijfel ik dat.

Maar goed, het kibbelen gaat hier maar door terwijl er al genoeg tips gegeven zijn voor een implementatie.

[Ram0n]

Vandaar dat ik ook meldde dat het daar op een veel grotere schaal toegepast werd, waar de andere technieken niet meer toereikend waren.

[roy-t]

dwilmer schreef op woensdag 17 maart 2010 @ 10:55:
[nerd-modus]
Dit is zo te zien een NP-probleem. Voor dit specifieke probleem kun je het best een pseudo-polynomiaal algoritme gebruiken
[/nerd-modus]

Je beste oplossing ligt bij recursie of (in de praktijk iets sneller) Dynamisch programmeren. Met wikipedia zou je al een heel eind moeten komen, google doet de rest.

Het hele idee van dynamisch programmeren is de al uitgerekende data zo efficient mogelijk gebruiken en het is meestal een stuk sneller dan gewoon recursief bruteforcen, niet maar ietjes .

[dwilmer]

roy-t schreef op woensdag 17 maart 2010 @ 16:07:
[...]
Het hele idee van dynamisch programmeren is de al uitgerekende data zo efficient mogelijk gebruiken en het is meestal een stuk sneller dan gewoon recursief bruteforcen, niet maar ietjes .

Dan moet ik mijn algoritmiek maar weer eens op gaan poetsen...
*boek erbij pakt*

Je hebt inderdaad gelijk. Waar recursie domweg exponentieel is, iets van O((aantal heksoorten)^(maximaal aantal stukken)), werkt dit pseudo-polynomiaal. Het knapsack-probleem, dat erop lijkt, kan worden opgelost in O((aantal heksoorten)*(totale lengte)). Mijn tip om de totale lengte kleiner te maken (dus cm ipv mm) klopt dan weer wel.

[roy-t]

dwilmer schreef op woensdag 17 maart 2010 @ 21:22:
[...]


Dan moet ik mijn algoritmiek maar weer eens op gaan poetsen...
*boek erbij pakt*

Je hebt inderdaad gelijk. Waar recursie domweg exponentieel is, iets van O((aantal heksoorten)^(maximaal aantal stukken)), werkt dit pseudo-polynomiaal. Het knapsack-probleem, dat erop lijkt, kan worden opgelost in O((aantal heksoorten)*(totale lengte)). Mijn tip om de totale lengte kleiner te maken (dus cm ipv mm) klopt dan weer wel.

Als je van mm naar cm gaat wordt het niet sneller omdat de relatieve grote gelijk blijft, of bedoel je iets anders? Totale lengte moet je hier zien als kleinste deelbaar deel. (Dus de lengte/kleinste hek)

[pedorus]

Het lijkt me sterk dat dynamisch programmeren hier veel snelheidswinst zal gaan geven ten opzichte van een ad-hoc algoritme. Je hebt niet zoveel combinaties die op dezelfde lengte uitkomen, dus het zal eerder trager zijn. Verder is het knapsack-probleem NP-compleet, net als dit probleem trouwens.

Verwijderd schreef op woensdag 17 maart 2010 @ 01:02:
Tja, kan allebei, had eerst alleen aan het eind een paal en aan het begin niet. Zie dat jij dat ook hebt, maar goed, zijn details he..

Ik doe überhaupt niet aan palen. Alsof je laminaat gaat leggen, maar de randen nog moet gaan zitten maken. Ik doe aan voorgemonteerde onderdelen.

Net even wat getest met een andere versie (niet-recursief). Heel veel efficiënter dan dit gaat het niet worden denk ik:

PHP:

class arrangement {
    public $length;
    public $partsused;

    public function addparts($number, $partlength) {
        $this->partsused = $this->partsused !== null ?
            "$number-$this->partsused" : $number;
        $this->length += $number * $partlength;
    }
    public function withparts($number, $partlength) {
        $result = clone $this;
        $result->addParts($number, $partlength);
        return $result;
    }
    public function __toString() {
        return "$this->length\t$this->partsused\n";
    }
    public function __construct($length = 0) {
        $this->length = $length;
    }
}
function printpossibilities($minlength, $parts, $initiallength = 0) {
    $solutions = array(new arrangement($initiallength));
    while ($part = array_pop($parts)) {
        for ($i = count($solutions) - 1; $i >= 0; $i--) {
            $solution = $solutions[$i];
            $max = max(0, (int) (($minlength - $solution->length - 1) / $part + 1));
            if (!empty($parts))
                for ($j = 0; $j < $max; $j++)
                    $solutions[] = $solution->withparts($j, $part);
            $solution->addparts($max, $part);
        }
    }
    sort($solutions);
    foreach ($solutions as $solution) echo $solution;
}
printpossibilities(5000, array(488, 1062, 1326, 1592), 40);

[Verwijderd]

pedorus schreef op woensdag 17 maart 2010 @ 22:48:
Het lijkt me sterk dat dynamisch programmeren hier veel snelheidswinst zal gaan geven ten opzichte van een ad-hoc algoritme. Je hebt niet zoveel combinaties die op dezelfde lengte uitkomen, dus het zal eerder trager zijn. Verder is het knapsack-probleem NP-compleet, net als dit probleem trouwens.

[...]

Ik doe überhaupt niet aan palen. Alsof je laminaat gaat leggen, maar de randen nog moet gaan zitten maken. Ik doe aan voorgemonteerde onderdelen.

Ik ook niet, vandaar dat elk hek al één paal voorgemonteerd heeft, zo hoeft hij alleen aan de paal van het vorige hek vastgemaakt worden. En dan blijft er aan het begin (of einde, als je ze omdraait) een plek over voor nog één paal.

Net even wat getest met een andere versie (niet-recursief). Heel veel efficiënter dan dit gaat het niet worden denk ik:

PHP:

class arrangement {
    public $length;
    public $partsused;

    public function addparts($number, $partlength) {
        $this->partsused = $this->partsused !== null ?
            "$number-$this->partsused" : $number;
        $this->length += $number * $partlength;
    }
    public function withparts($number, $partlength) {
        $result = clone $this;
        $result->addParts($number, $partlength);
        return $result;
    }
    public function __toString() {
        return "$this->length\t$this->partsused\n";
    }
    public function __construct($length = 0) {
        $this->length = $length;
    }
}
function printpossibilities($minlength, $parts, $initiallength = 0) {
    $solutions = array(new arrangement($initiallength));
    while ($part = array_pop($parts)) {
        for ($i = count($solutions) - 1; $i >= 0; $i--) {
            $solution = $solutions[$i];
            $max = max(0, (int) (($minlength - $solution->length - 1) / $part + 1));
            if (!empty($parts))
                for ($j = 0; $j < $max; $j++)
                    $solutions[] = $solution->withparts($j, $part);
            $solution->addparts($max, $part);
        }
    }
    sort($solutions);
    foreach ($solutions as $solution) echo $solution;
}
printpossibilities(5000, array(488, 1062, 1326, 1592), 40);

Ook een mooie oplossing, ook een stukje sneller dan de oplossing die ik had. Denk inderdaad dat het niet veel efficiënter kan, volgens mij is een simpele oplossing als deze in dit geval een stuk doeltreffender dan een heel uitgebreid algoritme.

[Nick The Heazk]

roy-t schreef op woensdag 17 maart 2010 @ 22:23:
Als je van mm naar cm gaat wordt het niet sneller omdat de relatieve grote gelijk blijft, of bedoel je iets anders? Totale lengte moet je hier zien als kleinste deelbaar deel. (Dus de lengte/kleinste hek)

Hangt er een beetje vanaf. Waarop dwilmer doelt is dat de tijdscomplexiteit van het DP algoritme om deze variante van het knapsack probleem op te lossen (laten we even veronderstellen dat hij wil weten of we een hek van exact x meter wilt vinden; het is eenvoudig aan te passen als je een wat langer hek wilt toelaten) afhankelijk is van de totale lengte van je hek. In dat algoritme ga je namelijk voor elke lengte een kolom intoduceren. Dan maakt het dus wel degelijk een verschil of je tevreden bent met dm, cm of mm. Het scheelt je respectievelijk een factor 100, 10 of 1 op het aantal kolommen t.o.v. rekenen in mm.

[ Voor 10% gewijzigd door Nick The Heazk op 18-03-2010 01:05 ]

[NeilForeal]

pedorus schreef op woensdag 17 maart 2010 @ 22:48:
Het lijkt me sterk dat dynamisch programmeren hier veel snelheidswinst zal gaan geven ten opzichte van een ad-hoc algoritme. Je hebt niet zoveel combinaties die op dezelfde lengte uitkomen, dus het zal eerder trager zijn. Verder is het knapsack-probleem NP-compleet, net als dit probleem trouwens.

[...]

Ik doe überhaupt niet aan palen. Alsof je laminaat gaat leggen, maar de randen nog moet gaan zitten maken. Ik doe aan voorgemonteerde onderdelen.

Net even wat getest met een andere versie (niet-recursief). Heel veel efficiënter dan dit gaat het niet worden denk ik:

PHP:

class arrangement {
    public $length;
    public $partsused;

    public function addparts($number, $partlength) {
        $this->partsused = $this->partsused !== null ?
            "$number-$this->partsused" : $number;
        $this->length += $number * $partlength;
    }
    public function withparts($number, $partlength) {
        $result = clone $this;
        $result->addParts($number, $partlength);
        return $result;
    }
    public function __toString() {
        return "$this->length\t$this->partsused\n";
    }
    public function __construct($length = 0) {
        $this->length = $length;
    }
}
function printpossibilities($minlength, $parts, $initiallength = 0) {
    $solutions = array(new arrangement($initiallength));
    while ($part = array_pop($parts)) {
        for ($i = count($solutions) - 1; $i >= 0; $i--) {
            $solution = $solutions[$i];
            $max = max(0, (int) (($minlength - $solution->length - 1) / $part + 1));
            if (!empty($parts))
                for ($j = 0; $j < $max; $j++)
                    $solutions[] = $solution->withparts($j, $part);
            $solution->addparts($max, $part);
        }
    }
    sort($solutions);
    foreach ($solutions as $solution) echo $solution;
}
printpossibilities(5000, array(488, 1062, 1326, 1592), 40);

Hier wordt ik heel blij van

Had met de functie van Guido van pagina 1 ook al een behoorlijke oplossing in elkaar gezet, maar deze werkt ook erg goed!

Genoeg oplossingen, blijft een interessant vraagstuk gezien de theorycrafting die er losbarst. Ik ben er in ieder geval helemaal uit nu. Bedankt voor alle hulp!

[roy-t]

Nick The Heazk schreef op donderdag 18 maart 2010 @ 01:03:
[...]

Hangt er een beetje vanaf. Waarop dwilmer doelt is dat de tijdscomplexiteit van het DP algoritme om deze variante van het knapsack probleem op te lossen (laten we even veronderstellen dat hij wil weten of we een hek van exact x meter wilt vinden; het is eenvoudig aan te passen als je een wat langer hek wilt toelaten) afhankelijk is van de totale lengte van je hek. In dat algoritme ga je namelijk voor elke lengte een kolom intoduceren. Dan maakt het dus wel degelijk een verschil of je tevreden bent met dm, cm of mm. Het scheelt je respectievelijk een factor 100, 10 of 1 op het aantal kolommen t.o.v. rekenen in mm.

Ehm nee, het is even langzaam (150m is 0,150km). Lengte is toch echt relatieve lengte (kleinste eenheid = kleinste hek, legte = totale afstand/kleinste hek). Je kunt niet meer dan alleen maar kleinste hekken achter elkaar zetten als oplossing. Zelfs als je getallen achter de komma gaat weg gooien zal er niet veel veranderen.

Anders zou een knapsack probleem van grote 1M^3 met kleinste element van 0,1M^3 langzamer zijn dan een met grote 10M^3 en kleinste element 1M^3. Neem lengte niet te letterlijk.

(Kan iemand dit misschien even verifiëren/netter opschrijven (logisch bewijs?)).

[Nick The Heazk]

De tijdscomplexiteit waar dwilmer lijkt op te doelen is deze van een DP waarbij je voor elke integer een kolom introduceerd. Het aantal kolommen is gelijk aan het gewicht dat je wil bekomen met je knapsack. In dat geval verschilt de tijdscomplexiteit wel met de eenheidsmaat die je gebruikt. Het is belangrijk om je te realiseren dat voor de analyse van de tijdscomplexiteit van dat DP algoritme de invoergrootte n, het aantal bits is dat je nodig hebt om het gewenste gewicht voor te stellen. De grootte van de getallen is dan wel relevant en bijgevolg afhankelijk van meten (en afronden tot; je gaat het fractioneel deel niet behouden!) in dm, cm of mm.

Ik denk dat jij wilt zeggen dat om gewicht 100.000 met kleinste afstand 1 te berekenen, niet meer werk hebt dan om gewicht 1 te berekenen met kleinste afstand 0.00001. In beide gevallen, claim jij, zou je maar maximaal 100.000 kolommen in je DP nodig hebben. Dat klopt natuurlijk. Ik doel op afronden tot dm, cm of mm.

Stel bijvoorbeeld dat we 500mm willen bekomen met een hek van 100mm, 50mm, 20mm, 10mm. Het zal dan wel degelijk moeilijker zijn dan hetzelfde probleem oplossen maar dan in cm: 50cm met hekken van 10cm, 5cm, 2cm, 1cm. Je gaat in dit geval duidelijk van 500 kolommen naar 50 kolommen.

Ik wil dus zeggen dat de nauwkeurigheid van je resultaat mee de moeilijkheid van je probleem bepaalt. Wil je een resultaat dat correct is tot op 1nm, 1mm, 1cm, 1dm, 1m? Hoe nauwkeuriger, hoe meer kolommen, hoe hoger de uitvoeringstijd.

Voor het voorbeeld van de TS zouden we bijvoorbeeld de volgende problemen kunnen oplossen (van meeste naar minste werk en tevens van meest nauwkeurig naar minst nauwkeurig):
5000mm bekomen met elementen van 488mm, 1022mm, 1286mm en 1552mm.
500cm bekomen met elementen van 49cm, 102cm, 129cm en 155cm.
50dm bekomen met elementen van 5dm, 10dm, 13dm en 15dm.
5m bekomen met elementen van 1m.

[ Voor 11% gewijzigd door Nick The Heazk op 18-03-2010 13:24 ]

[Soultaker]

Als je toch gaat programmeren lijkt een nauwkeurigheid van millimeters me niet problematisch. Dan kun je nog kilometers hekwerk op de millimeter nauwkeurig plaatsen zonder dat 't echt veel tijd of geheugen gaat kosten.

Je kunt natuurlijk wel om te beginnen je nauwkeurigheid reduceren met de grootste gemene deler van de gegeven afmetingen in millimeters (2mm, in dit geval); dat levert je toch een factor twee winst op zonder dat de nauwkeurigheid er onder lijdt.