[C++] Recursief algoritme voor Japanse puzzel

zondag 23 januari 2005 18:58

Topicstarter

Verwijderd schreef op zondag 23 januari 2005 @ 18:44:
Misschien zou je je algoritme uit kunnen leggen.

Dit algoritme probeert niet de puzzel op te lossen, maar maakt alle combinaties zodat ze nagelopen kunnen worden.

Ik vermoed echter dat je gewoon bruteforce alle mogelijkheden probeert die mogelijk zijn voor een rij. Dat is inderdaad duur.

Dit is wat in feite ook gebeurt als je zelf een dergelijke puzzel oplost. Maar het is geen bruteforce, mijn programma lost puzzels op zoals een mens ze ook zou oplossen (mogelijkheden bekijken --> alles wat in alle mogelijkheden overeenkomt opschrijven --> volgende rij/kolom).

Probeer een algoritme te implementeren zoals je zo'n puzzel ook met de hand oplost; begin met de rijen met de grootste waardes. Vervolgens kan je al heleboel uitsluiten en verder gaan.

Mijn programma begint als eerste met het bepalen van een algehele volgorde met de rijen en kolommen die het meest kunnen opleveren. Ik heb er wel over nagedacht, hoor

maar deze functie is gewoon de bottleneck. Mijn programma kan álle puzzels (die zowel mét als zonder gokken op te lossen zijn) binnen korte tijd oplossen, maar zodra de puzzel groter wordt (nu al vele uren bezig op een puzzel van 80x45) moet deze functie ook harder werken, terwijl kleinere puzzels (zeg 25x25) in een fractie van een seconde opgelost worden omdat het aantal combinaties gewoonweg kleiner is.

Acties:

Alarmnummer

-= Tja =-

[algemeen]
Een oplossing voor dit soort problemen is snoeien in de oplossingsruimtes. Dus probeer geen stappen te nemen die al genomen zijn, of probeer geen stappen te nemen die geen oplossing tot gevolg heeft.

Dit zijn problemen die je vaak terug ziet binnen de ai. Een andere 'ruimere' mogelijkeheid is om misschien een aantal keren een oplossing te zoeken. Dat je eerst een oplossing probeert te vinden die het meest voor de hand ligt... kan je dit niet vinden omdat je algoritme nu eenmaal mogelijke oplossingsroutes heeft overgeslagen, ga je het nog een keer proberen, maar dan met een uitgebreider algoritme.

Ik zie verder dat je ook vaak arrays aanspreekt zonder die elementen op te slaan in een tijdelijke variable. Vroeger...

toen was dat namelijk nogal een performance verzieker.

ps:
ik ben niet inhoudelijk op het algoritme ingegaan omdat ik eigelijk geen tijd/zin heb om me erin te verdiepen.

[ Voor 43% gewijzigd door Alarmnummer op 23-01-2005 19:02 ]

zondag 23 januari 2005 19:02

Acties:

zondag 23 januari 2005 19:06

Topicstarter

Alarmnummer schreef op zondag 23 januari 2005 @ 18:58:
[algemeen]
Een oplossing voor dit soort problemen is snoeien in de oplossingsruimtes. Dus probeer geen stappen te nemen die al genomen zijn, of probeer geen stappen te nemen die geen oplossing tot gevolg heeft.

Mijn volgende test is het maken van een functie die dit doet. Ik heb namelijk altijd gedacht dat de extra checks de performance alleen maar terug zouden brengen, maar met een slimme opzet zou dit wel moeten gaan lukken ja.

Ik zie verder dat je ook vaak arrays aanspreekt zonder die elementen op te slaan in een tijdelijke variable. Vroeger... toen was dat namelijk nogal een performance verzieker.

En kan gcc met -O3 dit voorkomen?

Acties:

Alarmnummer

-= Tja =-

JeRa schreef op zondag 23 januari 2005 @ 19:02:
[...]

Mijn volgende test is het maken van een functie die dit doet. Ik heb namelijk altijd gedacht dat de extra checks de performance alleen maar terug zouden brengen,

Dat doen ze ook.. maar iedere check zal een veelvoud van die check kosten besparen als je kunt bepalen dat je een oplossingsroute niet hoeft te proberen. Als jij al zo vroeg mogelijk in een oplossingsroute kunt bepalen dat die route geen oplossing tot gevolg heeft, kan het je een enorme besparing opleveren.

En kan gcc met -O3 dit voorkomen?

Ik zou het niet weten... dit stamt nog helemaal uit het turbo c 2.0 tijdperk

... toen ik nog zoveel mogelijk code in zo weinig mogelijk regels probeerde te prakken.

[edit]
Stel dat jij 1 keer wilt gaan wandelen, dan hoeft het check algoritme niet waterdicht te zijn. Zolang je er maar voor zorgt dat je geen goeie oplossingspaden afkeurt.... Als jij foute oplossingspaden goedkeurt.. tja.. dan moet je onnodig rekenen.. maar er zijn geen oplossingen verloren gegaan.

[ Voor 20% gewijzigd door Alarmnummer op 23-01-2005 19:09 ]

zondag 23 januari 2005 19:11

Acties:

zondag 23 januari 2005 19:17

Topicstarter

Alarmnummer schreef op zondag 23 januari 2005 @ 19:06:
Stel dat jij 1 keer wilt gaan wandelen, dan hoeft het check algoritme niet waterdicht te zijn. Zolang je er maar voor zorgt dat je geen goeie oplossingspaden afkeurt.... Als jij foute oplossingspaden goedkeurt.. tja.. dan moet je onnodig rekenen.. maar er zijn geen oplossingen verloren gegaan.

Ik heb twee functies, ngmPos en ngmComp. De eerste functie kan dus nieuwe mogelijkheden genereren, en de tweede controleert of de gevonden combinatie wel tot de mogelijkheden kan behoren (vergelijkt het met de puzzel, dus).

Ik ben nu dus van plan om die tweede functie overbodig te maken door alle checks in de eerste functie te doen en de foute mogelijkheden bij voorbaat al uit te sluiten (door ze gewoonweg niet te genereren als één van de blokken niet kan). Bedankt voor het nieuwe inzicht!

[ Voor 9% gewijzigd door JeRa op 23-01-2005 19:12 ]

Acties:

Alarmnummer

-= Tja =-

JeRa schreef op zondag 23 januari 2005 @ 19:11:
[...]
Ik heb twee functies, ngmPos en ngmComp. De eerste functie kan dus nieuwe mogelijkheden genereren, en de tweede controleert of de gevonden combinatie wel tot de mogelijkheden kan behoren (vergelijkt het met de puzzel, dus).

Ik ben nu dus van plan om die tweede functie overbodig te maken door alle checks in de eerste functie te doen en de foute mogelijkheden bij voorbaat al uit te sluiten (door ze gewoonweg niet te genereren als één van de blokken niet kan). Bedankt voor het nieuwe inzicht!

Als je echt geinteresseerd bent in dit soort problematiek, dan moet je eens gaan spelen met Prolog. Prolog is een taal waarin backtracken ingebouwd zit en waar operators (oa de cut) aanwezig zijn waarmee je direct in de oplossingsruimtes kunt snoeien.

Alhoewel Prolog als algemene taal imho volslagen zinloos is, is het wel een perfecte taal voor bepaalde soorten problemen, oa combinatorische problemen. Dat is ook de reden dat Prolog veel wordt gebruikt bij AI-achtige problematiek. Bij AI heb je ook vaak oplossingruimtes en te veel oplossingen. Het is dan ook vaak kwestie om zoveel mogelijk te proberen te snoeien.

Rekentijd kan daardoor van dagen naar fracties van secondes gaan.

zondag 23 januari 2005 19:39

Acties:

H!GHGuY

Try and take over the world...

JeRa schreef op zondag 23 januari 2005 @ 18:08:

C++:

bool ngmPos(unsigned char *vals, unsigned int size, unsigned int len, unsigned int *pos, unsigned int id)
{
    if (((id == size - 1) && (len - pos[id] > vals[id]))
     || ((id < size - 1) && (pos[id + 1] - pos[id] - 1 > vals[id]))) {
        pos[id]++;
    } else {
        if (id == 0)
            return false;
        if (!ngmPos(vals, size, len, pos, id - 1))
            return false;
        pos[id] = pos[id - 1] + vals[id - 1] + 1;
    }
    return true;
}

ik zou deze code herschikken naar dit:

C++:

bool ngmPos(unsigned char *vals, unsigned int size, unsigned int len, unsigned int *pos, unsigned int id)
{
    if (((id == size - 1) && (len - pos[id] > vals[id]))  || ((id < size - 1) && (pos[id + 1] - pos[id] - 1 > vals[id]))) 
    {
        pos[id]++;
    } 
    else if (id == 0 || !ngmPos(vals, size, len, pos, id - 1))
            return false;
    else
        pos[id] = pos[id - 1] + vals[id - 1] + 1;
    }
    return true;
}

en proberen om ook zoveel mogelijk de 'beslissende factoren' bij een if voorwaarde vooraan te zetten. (dit heb je mss gedaan. daarvoor snap'k niet genoeg van waar je mee bezig bent, en wat alles is...)
dus

C++:

1 2	if (a && b) doeiets(a,b)

dan moet je hebben dat: kans(a == false) > kans (b==false)
dit is nl een handig bijkomstigheid van lazy evaluation. (wetende dat theoretisch een IF duur is)
(bij een OR ligt dit anders natuurlijk)

ook kun je proberen recursiviteit uit de functie te halen, ze is niet zo lang en je kan er misschien baat bij hebben.

dan krijg je iets in de trant van:

C++:

bool ngmPos(unsigned char *vals, unsigned int size, unsigned int len, unsigned int *pos, unsigned int id)
{
    register bool vw1, vw2;
a:  vw1 = ((id == size - 1) && (len - pos[id] > vals[id]))  || ((id < size - 1) && (pos[id + 1] - pos[id] - 1 > vals[id]))
    vw2 = (id == 0)
    if (vw1) 
    {
        pos[id]++;
        return true
    } 
    else if (vw2)
            return false;
    else if (!vw1 && !vw2)
    {
        pos[id] = pos[id - 1] + vals[id - 1] + 1;
        return true
    }
    else
    {
         id--; goto a;
    }
}

dit heb'k maar even redelijk snel bedacht en uitgekiend. De volgorde van de if-'s goedzetten, evt fouten eruit halen.
(er kunen zeker fouten in zitten (ik moet de theorie over verwijderen van recursie nog eens goe doornemen morgen voor et examen van overmorgen) en dus moet je, als je dit wil proberen toepassen zeker goed testen/corrigeren)

[ Voor 10% gewijzigd door H!GHGuY op 23-01-2005 19:42 ]

ASSUME makes an ASS out of U and ME

maandag 24 januari 2005 08:47

Acties:

MisterData

Als je even zoekt op GoT naar de 'GPC' (GoT Programming Contest) dan kom je een topic tegen waar als wedstrijdopdracht deze puzzels werden opgelost. Staat misschien ook wat nuttige info in

maandag 24 januari 2005 12:41

Acties:

Verwijderd

HIGHGuY schreef op zondag 23 januari 2005 @ 19:39:
[...]

ik zou deze code herschikken naar dit:

C++:

bool ngmPos(unsigned char *vals, unsigned int size, unsigned int len, unsigned int *pos, unsigned int id)
{
    if (((id == size - 1) && (len - pos[id] > vals[id]))  || ((id < size - 1) && (pos[id + 1] - pos[id] - 1 > vals[id]))) 
    {
        pos[id]++;
    } 
    else if (id == 0 || !ngmPos(vals, size, len, pos, id - 1))
            return false;
    else
        pos[id] = pos[id - 1] + vals[id - 1] + 1;
    }
    return true;
}

De oorspronkelijke functie kan inderdaad eenvoudiger worden opgeschreven, maar dit klopt niet helemaal. Het moet volgens mij zijn:

C++:

bool ngmPos(unsigned char *vals, unsigned int size, unsigned int len, unsigned int *pos, unsigned int id) 
{ 
    if (((id == size - 1) && (len - pos[id] > vals[id]))  || ((id < size - 1) && (pos[id + 1] - pos[id] - 1 > vals[id])))  
    { 
        pos[id]++; 
    }  
    else {
        if (id == 0 || !ngmPos(vals, size, len, pos, id - 1)) 
            return false; 
        pos[id] = pos[id - 1] + vals[id - 1] + 1; 
    } 
    return true; 
}

Verder heeft optimaliseren van de functie niet echt heel veel zin, omdat het algoritme op zichzelf al niet erg optimaal lijkt (waarom zou je alle mogelijk posities af willen lopen?).

[ Voor 3% gewijzigd door Verwijderd op 24-01-2005 12:41 ]

maandag 24 januari 2005 12:48

Acties:

Verwijderd

goto a? Auw auw.. zijn we hier met GoT golf bezig?

maandag 24 januari 2005 15:45

Acties:

H!GHGuY

Try and take over the world...

Verwijderd schreef op maandag 24 januari 2005 @ 12:41:
[...]

De oorspronkelijke functie kan inderdaad eenvoudiger worden opgeschreven, maar dit klopt niet helemaal. Het moet volgens mij zijn:
C++:
1
2
3
4
5
6
7
8
9
10
11
12
13
bool ngmPos(unsigned char *vals, unsigned int size, unsigned int len, unsigned int *pos, unsigned int id) 
{ 
    if (((id == size - 1) && (len - pos[id] > vals[id]))  || ((id < size - 1) && (pos[id + 1] - pos[id] - 1 > vals[id])))  
    { 
        pos[id]++; 
    }  
    else {
        if (id == 0 || !ngmPos(vals, size, len, pos, id - 1)) 
            return false; 
        pos[id] = pos[id - 1] + vals[id - 1] + 1; 
    } 
    return true; 
}
Verder heeft optimaliseren van de functie niet echt heel veel zin, omdat het algoritme op zichzelf al niet erg optimaal lijkt (waarom zou je alle mogelijk posities af willen lopen?).

beide stukken code zijn afaik gelijkwaardig behalve dat ik een 3ledige if-else heb en jij een if binnen een else. dus behalve wat mooier ogen is er in praktijk toch geen verschil

Verwijderd schreef op maandag 24 januari 2005 @ 12:48:
goto a? Auw auw.. zijn we hier met GoT golf bezig?

Dit is enkel bedoeld om de recursie eruit te halen. Het oogt lelijk (spaghettiecode) maar wanneer et juist is kan et wel eens die extra percentjes eruit knijpen die je verliest met functieoproepen en -returns. Ik heb trouwens net het studeren van het stuk over verwijderen van recursie achter de rug

Ik moet er mss wel nog bijzeggen dat wanneer je een goeie compiler gebruikt het wel eens kan zijn dat de compiler dit zelf doet zonder dat je het weet, maar eens testen kan altijd tof zijn natuurlijk

ASSUME makes an ASS out of U and ME

maandag 24 januari 2005 17:35

Acties:

maandag 24 januari 2005 18:49

Because he doesn't row...

HIGHGuY schreef op maandag 24 januari 2005 @ 15:45:
Dit is enkel bedoeld om de recursie eruit te halen. Het oogt lelijk (spaghettiecode) maar wanneer et juist is kan et wel eens die extra percentjes eruit knijpen die je verliest met functieoproepen en -returns. Ik heb trouwens net het studeren van het stuk over verwijderen van recursie achter de rug

Een goto is nooit nodig, je kan altijd equivalente code schrijven met loops. Je kan bv al een while (1) loop schrijven, met 2 breaks. Maar je kan het zeker ook op een andere manier doen, zonder breaks. Je hebt ook nog grote kans dat je compiler niet correct kan optimalizeren vanwege de goto, en korte loops worden bv unrolled door je compiler, iets dat met goto niet bepaald kan worden. Kortom, goto is evil

Acties:

H!GHGuY

Try and take over the world...

Zoijar schreef op maandag 24 januari 2005 @ 17:35:
[...]

Een goto is nooit nodig, je kan altijd equivalente code schrijven met loops. Je kan bv al een while (1) loop schrijven, met 2 breaks. Maar je kan het zeker ook op een andere manier doen, zonder breaks. Je hebt ook nog grote kans dat je compiler niet correct kan optimalizeren vanwege de goto, en korte loops worden bv unrolled door je compiler, iets dat met goto niet bepaald kan worden. Kortom, goto is evil

daar heb je'n heel goed punt... alhoewel het in sommige gevallen niet anders kan dan met een goto statement... en daarbij: uiteindelijk is een if nix anders dan een vgl + goto

maar een while kan een compiler "zo goed als nooit" unrollen ten opzichte van "de vele keren" waarbij dit met een for wel kan.

ASSUME makes an ASS out of U and ME

maandag 24 januari 2005 19:28

Acties:

maandag 24 januari 2005 19:53

Bij het maken van zo'n soort algoritme kan je het beste kijken hoe je het zelf zou doen.

Bij Japanse puzzels doe ik het altijd zo:
In mijn hoofd plaats ik alles zoveel mogelijk aan de linkerkant
In mijn hoofd plaats ik alles zoveel mogelijk aan de rechterkant
Hokjes die in beide plaatjes in hetzelfde grote blok vallen kleur ik dan zwart.
In hokjes die in beide plaatjes tussen dezelfde grote blokken vallen zet ik een streepje.
Zelfde voor boven en onder.
Alles herhalen tot er niets meer verandert.

Dit lost veel op, maar nog niet alles. Zoiets werkt bijvoorbeeld niet:

code:

3 3  [...-X........]
. = nog niets
- = niet
X = wel

Mijn algoritme geeft namelijk:

code:

links
3 3  [XXX-XXX------]
rechts
3 3  [----XXX---XXX]
samen
3 3  [...-X........]

Terwijl dit gezegd kan worden:

code:

1	3 3 [...-XXX-.....]

Ik heb het ooit nog eens in QuickBasic gezet. Het loste ongeveer 50% op (Veel meer kan ik zelf ook niet).

edit:
Bijvoorbeeld de hele puzzel:

code:

1
2
3

    1 1 1 0 2 1 1 0 1 1 1
1 3 . . . . . . . . . . .
3 3 . . . . . . . . . . .

[ Voor 8% gewijzigd door Daos op 24-01-2005 20:28 ]

Acties:

Sjaaky

Volgens mij kan je op basis van dat voorbeeldje helemaal nog niets concluderen.
Niets gezegd

[ Voor 12% gewijzigd door Sjaaky op 25-01-2005 09:46 ]

maandag 24 januari 2005 22:11

Acties:

dinsdag 25 januari 2005 15:28

Topicstarter

Mijn algoritme werkt als volgt. Op basis van een bepaalde volgorde (die er nu niet toe doet) gaat mijn programma de rijen en kolommen af, en doet het volgende (zonder te gokken, dat zit er ook nog in) per rij of kolom:

1. Haal de rij/kolom op uit de puzzel (het grid)
2. Bepaal welke mogelijkheden er zijn voor deze rij/kolom
3. Vergelijk alle mogelijkheden en hou bij in 2 masks welke posities altijd áán of úit staan
4. Schrijf het resultaat hiervan weg naar de puzzel
5. Kies een nieuwe rij/kolom en ga naar stap 1

Nu zit dit natuurlijk iets complexer in elkaar met een hoop optimizaties, maar de bottleneck zit 'm natuurlijk in stap 2 en 3 (tijdens het profilen duurde het genereren en het vergelijken van de masks ongeveer even lang).

Daarom heb ik een nieuw algoritme bedacht dat de mogelijkheden bedenkt d.m.v. functies als findFirstPos en findNextPos. findFirstPos vindt de éérste positie die een blok met een bepaalde lengte in een bepaalde rij/kolom kan innemen. findNextPos probeert de eerstvolgende positie van een blok te bepalen en itereert zonodig over de andere blokken om nieuwe mogelijkheden te genereren. Deze methode werkt (theoretisch) beter voor rijen en kolommen waarvan al iets bekend is, want dan kan het aantal mogelijkheden drastisch worden teruggebracht al tijdens het bedenken van de mogelijkheden. Echter, voor rijen en kolommen waar alles nog onbekend is heb je te maken met een performance hit.

Ik weet nog niet of het gaat opwegen tegen mijn oude systeem, omdat ik het simpelweg nog niet goed geïmplementeerd heb. Een probleem waar ik tegenaan loop is bijvoorbeeld de functie findFirstPos; deze moet de eerste mogelijke positie van een blok moeten kunnen vinden in een string met tekens. Met plaatsen waar het bekend is dat een blok niet kan is het makkelijk:

Een blok van 3 in de volgende reeks:

code:

1	?-???-????-

Is makkelijk als volgt in te passen:

code:

1	?-XXX-????-

...omdat je simpelweg kunt controleren op de aanwezigheid van de '-', de hokjes waar je zeker van bent dat het niet gekleurd is. Echter heb ik nog geen idee hoe ik om moet gaan met de hokjes waarvan ik zeker weet dat ze wél gekleurd zijn, want deze mogen natuurlijk overlappen of aansluiten bij een bepaald blok (of bij een ander blok, maar hoe bepaal je dat tijdens het genereren van mogelijkheden?). Thoughts anyone?

Acties:

dinsdag 25 januari 2005 16:44

Zoiets?:

Verplaats het meest rechtse blok links van het meest linkse lege hokje die gevuld had moeten zijn naar rechts zodat het net over dat hokje gaat.
Herhaal totdat er geen lege hokjes die gevuld hadden moeten zijn meer zijn

Iets anders:
Hoe roep jij die ngmPos(..) aan?
Ik heb dit geprobeerd:

int main() {
/*
vals: de lengtes van de blokken (in het voorbeeld 1 en 3)
size: het aantal blokken (in het voorbeeld 2)
len: de lengte van de rij of kolom (in het voorbeeld 8 )
pos: de huidige positie van de blokken, 0-based
id: het blok dat één positie naar rechts moet worden verschoven, 0-based
*/
unsigned char vals[] = {1, 3};
unsigned int size = 2;
unsigned int len = 8;
unsigned int pos[] = {0, 2};
unsigned int id = 0;

printf("pos[0] = %d, pos[1] = %d\n", pos[0], pos[1]);
ngmPos(vals, size, len, pos, id);
printf("pos[0] = %d, pos[1] = %d\n", pos[0], pos[1]);

Acties:

dinsdag 25 januari 2005 17:08

JeRa schreef op maandag 24 januari 2005 @ 22:11:
Mijn algoritme werkt als volgt. Op basis van een bepaalde volgorde (die er nu niet toe doet) gaat mijn programma de rijen en kolommen af, en doet het volgende (zonder te gokken, dat zit er ook nog in) per rij of kolom:
1. Haal de rij/kolom op uit de puzzel (het grid)
2. Bepaal welke mogelijkheden er zijn voor deze rij/kolom
3. Vergelijk alle mogelijkheden en hou bij in 2 masks welke posities altijd áán of úit staan
4. Schrijf het resultaat hiervan weg naar de puzzel
5. Kies een nieuwe rij/kolom en ga naar stap 1

Volgens mij is dit algoritme veel te beperkt om een zinnige klasse van problemen op te lossen (zelfs de relatief simpele variant die altijd in puzzelboekjes staat). Wat doe je als je niet op basis van een afzonderlijke kolom of rij kan beslissen dat je een vakje mag kleuren?
Bijvoorbeeld:

code:

  1 2 2
2 X X .
2 . X X
1 . . X

Nu zit dit natuurlijk iets complexer in elkaar met een hoop optimizaties, maar de bottleneck zit 'm natuurlijk in stap 2 en 3 (tijdens het profilen duurde het genereren en het vergelijken van de masks ongeveer even lang).

Raar dat daar de bottleneck in zit. Ik zou zeggen dat je eerst voor iedere rij of kolom de mogelijkheden genereerd. Die hoef je daarna nooit opnieuw te berekenen. Wel moet je na het inkleuren van een vakje de mogelijkheden verwijderen die niet meer mogelijk zijn.

Op die manier hoeft het zoeken naar de beginmogelijkheden niet zo veel tijd te kosten, ten opzichte van het veel grotere aantal combinaties van mogelijkheden dat je moet beschouwen.

Trouwens, het oplossen van deze puzzels is in het algemeen NP-compleet, wat betekent dat er geen efficiënt algoritme voor te verzinnen is. Je moet je dus hoe dan ook beperken tot een versimpelde variant. (De puzzels in puzzelboekjes zijn relatief simpel, qua berekenbaarheid, ook al kan ik ze bijna nooit oplossen.

)

Acties:

dinsdag 25 januari 2005 17:27

Topicstarter

Daos schreef op dinsdag 25 januari 2005 @ 15:28:
Iets anders:
Hoe roep jij die ngmPos(..) aan?
[/code]

Voor zover ik kan zien doe je dat goed, behalve id. Het algoritme kan itereren over de blokken die links van het aangeroepen blok liggen, dus je moet met het meest rechtste blok beginnen. M.a.w.,

id = 0;

moet

id = 1;

worden

Soultaker schreef op dinsdag 25 januari 2005 @ 16:44:
[...]

Volgens mij is dit algoritme veel te beperkt om een zinnige klasse van problemen op te lossen (zelfs de relatief simpele variant die altijd in puzzelboekjes staat). Wat doe je als je niet op basis van een afzonderlijke kolom of rij kan beslissen dat je een vakje mag kleuren?

Als een puzzel zonder gokken opgelost kan worden, dan vindt mijn algoritme het. Zonder enige twijfel. Als het mét gokken (of zoals jij zegt, als je niet van een afzonderlijke kolom of rij kunt afleiden of je een vakje mag kleuren) op te lossen is zal mijn programma de status van het grid onthouden en gaan itereren over de mogelijkheden. Als er een oplossing is, zal het algoritme het zeker vinden.

Raar dat daar de bottleneck in zit.

Vind ik niet, die functies worden immers het vaakst aangeroepen doordat er zoveel mogelijkheden zijn.

Ik zou zeggen dat je eerst voor iedere rij of kolom de mogelijkheden genereerd.

Dat doe ik. Daar maak ik nu een nieuw algoritme voor, zie boven, waar ik dus niet helemaal uit kom.

Die hoef je daarna nooit opnieuw te berekenen.

Ze worden ook allemaal in een cache gestopt, behalve als een mogelijkheid niet kan natuurlijk.

Wel moet je na het inkleuren van een vakje de mogelijkheden verwijderen die niet meer mogelijk zijn.

Dat gebeurt ook al. Er is heus wel over nagedacht, hoor

het gaat er nu alleen om hoe ik in het aantal mogelijkheden kan kappen door tijdens het genereren van de mogelijkheden kan bepalen welke posities van blokken overgeslagen kunnen worden. Aan de hand van vakjes die het zeker niet zijn kan ik nu wel, maar aan de hand van vakjes die het zeker wél zijn wordt wat lastiger.

Acties:

dinsdag 25 januari 2005 17:30

Topicstarter

Daos schreef op dinsdag 25 januari 2005 @ 15:28:
Zoiets?:

Verplaats het meest rechtse blok links van het meest linkse lege hokje die gevuld had moeten zijn naar rechts zodat het net over dat hokje gaat.
Herhaal totdat er geen lege hokjes die gevuld hadden moeten zijn meer zijn

Ik moest even goed lezen voordat ik hem begreep, maar het lijkt me de oplossing

ik ga het meteen implementeren.

Acties:

dinsdag 25 januari 2005 17:52

Because he doesn't row...

Soultaker schreef op dinsdag 25 januari 2005 @ 16:44:
Trouwens, het oplossen van deze puzzels is in het algemeen NP-compleet, wat betekent dat er geen efficiënt algoritme voor te verzinnen is. Je moet je dus hoe dan ook beperken tot een versimpelde variant.

Nou, niet helemaal. NP stelt alleen dat een oplossing van een willekeurig probleem uit de klasse in polynomiale tijd kan worden geverifieerd; de compleetheid stelt dat elk ander NP probleem tot dit probleem te herleiden is. Als je dus een polynomiale oplossing kan vinden voor een NPC probleem, dan bestaat er een polynomiale oplossing voor alle NPC problemen. Er wordt nooit gesteld dat er geen polynomiale oplossing bestaat, daar is geen enkel bewijs voor. Slechts het feit dat het tegendeel tot nu toe niet is bewezen, zegt niets. (maar geeft wel een mate van geloof in het niet bestaan aan) Maar als de japanse puzzel NPC is, en de TS vindt plotseling wel een efficient algoritme; dan kan hij de fields medal ook meteen ophalen.

Acties:

dinsdag 25 januari 2005 18:07

Akkoord, maar om nu even en passant het bewijs voor P == NP te leveren gaat voor de TS waarschijnlijk wat te ver.

Tenzij 'ie de moderne Einstein is hoeft hij dus niet te hopen op een algoritme dat in polynomiale tijd werkt (dat de oplossing in polynomiale tijd te verifiëren is, is duidelijk).

Oh trouwens, je hoeft maar één NP-compleet probleem te reduceren tot het probleem in kwestie, omdat uit de NP-compleetheid van dat probleem al volgt dat alle andere problemen indirect ook te reduceren zijn tot het probleem waarvan je bewijst dat het NP-compleet is.

[ Voor 36% gewijzigd door Soultaker op 25-01-2005 17:57 ]

Acties:

dinsdag 25 januari 2005 18:26

Soultaker schreef op dinsdag 25 januari 2005 @ 16:44:

Volgens mij is dit algoritme veel te beperkt om een zinnige klasse van problemen op te lossen (zelfs de relatief simpele variant die altijd in puzzelboekjes staat). Wat doe je als je niet op basis van een afzonderlijke kolom of rij kan beslissen dat je een vakje mag kleuren?
Bijvoorbeeld:
code:
1
2
3
4
  1 2 2
2 X X .
2 . X X
1 . . X

Dat is geen goed voorbeeld. Dit kan namelijk ook:

code:

  1 2 2
2 . X X
2 . X X
1 X . .

Nieuw voorbeeld:

code:

1
2
3

    1 1 1 1
1 1 X . . X
  2 . X X .

Acties:

dinsdag 25 januari 2005 18:30

Topicstarter

Daos schreef op dinsdag 25 januari 2005 @ 18:07:
[...]

Nieuw voorbeeld:
code:
1
2
3
    1 1 1 1
1 1 X . . X
  2 . X X .

Mijn algoritme gaat daar als volgt mee om:

1. Sorteer de rijen/kolommen op aantal mogelijkheden, oplopend --> items
2. Onthoud de huidige status van de puzzel
3. Kies een item
4. Kies een mogelijkheid
5. Vul deze mogelijkheid in en ga 'normaal' verder met het oplossen van de puzzel
6. Lopen we vast? Zet dan de status van de puzzel terug en ga naar 4
7. Alle mogelijkheden gehad? Zet dan de status van de puzzel terug en ga naar 3

Op deze manier worden álle mogelijkheden behandeld en weet je zeker dat het die en andere puzzels kan oplossen. Is dit een goede manier?

Acties:

dinsdag 25 januari 2005 19:15

Because he doesn't row...

Soultaker schreef op dinsdag 25 januari 2005 @ 17:52:
Oh trouwens, je hoeft maar één NP-compleet probleem te reduceren tot het probleem in kwestie, omdat uit de NP-compleetheid van dat probleem al volgt dat alle andere problemen indirect ook te reduceren zijn tot het probleem waarvan je bewijst dat het NP-compleet is.

offtopic:
Ja, ik bedoelde met 'allen', dat het niet om een specifiek probleem mag gaan. Dus niet bv een speciaal geconstrueerd SAT probleem; maar de hele klasse van SAT problemen. Hierop is 'knapsack' encryptie bv op de mist in gegaan, omdat ze van specifieke vorm waren en die sub klasse dus niet NPC bleek te zijn (maar wel NP, want dat is vrijwel elk probleem dat niet te complex is)

Acties:

dinsdag 25 januari 2005 21:30

Topicstarter

Daos schreef op dinsdag 25 januari 2005 @ 15:28:
Zoiets?:

Verplaats het meest rechtse blok links van het meest linkse lege hokje die gevuld had moeten zijn naar rechts zodat het net over dat hokje gaat.
Herhaal totdat er geen lege hokjes die gevuld hadden moeten zijn meer zijn

Ik heb deze methode nog eens overdacht, maar hoe gaat hij hier mee om?

Moet worden:

"..X.XX....XXX"

Op dit moment bekend:

".    X       "

Eerst gevonden mogelijkheid:

".X XX XXX    "

Volgens jouw methode zou nu het 2-blok naar rechts worden verschoven. Nu ontstaat daar een 5-blok, niet de bedoeling dus. Nu kun je daar wel extra checks overheen gooien, maar volgens mij moet het gewoon anders.

Acties:

dinsdag 25 januari 2005 21:32

JeRa schreef op dinsdag 25 januari 2005 @ 18:26:
Mijn algoritme gaat daar als volgt mee om:

1. Sorteer de rijen/kolommen op aantal mogelijkheden, oplopend --> items
2. Onthoud de huidige status van de puzzel
3. Kies een item
4. Kies een mogelijkheid
5. Vul deze mogelijkheid in en ga 'normaal' verder met het oplossen van de puzzel
6. Lopen we vast? Zet dan de status van de puzzel terug en ga naar 4
7. Alle mogelijkheden gehad? Zet dan de status van de puzzel terug en ga naar 3

Op deze manier worden álle mogelijkheden behandeld en weet je zeker dat het die en andere puzzels kan oplossen. Is dit een goede manier?

Of het een goede manier is kan ik niet echt vertellen. Ik weet wel zeker dat je op deze manier een explosie van combinatorische mogelijkheden krijgt en dat het genereren van de mogelijkheden per rij daarbij in het niet vallen.

Acties:

dinsdag 25 januari 2005 22:15

Topicstarter

Soultaker schreef op dinsdag 25 januari 2005 @ 21:30:
[...]

Of het een goede manier is kan ik niet echt vertellen. Ik weet wel zeker dat je op deze manier een explosie van combinatorische mogelijkheden krijgt en dat het genereren van de mogelijkheden per rij daarbij in het niet vallen.

In de praktijk valt dat wel mee. Stel dat hij begint met een rij waar maar twéé mogelijkheden zijn, en hij kiest de verkeerde, dan zal de puzzel al snel vastlopen (mits die oplossing niet mogelijk is) doordat er bijvoorbeeld geen mogelijkheden meer zijn voor een bepaalde rij of kolom. Het aantal mogelijkheden is inderdaad gigantisch, maar in de praktijk wordt de goede oplossing er al snel tussenuit gepikt.

Acties:

dinsdag 25 januari 2005 22:40

Ik denk dat dat in het algemene geval heel erg tegenvalt. Maar zoals ik al zei, die puzzels uit boekjes zijn veel simpeler dan het gemiddelde geval, dus als je die er mee wil oplossen kom je waarschijnlijk wel een heel eind.

Acties:

dinsdag 25 januari 2005 22:55

Topicstarter

En toen kwam alles terug op de reden waarom ik dit topic geopend had, een puzzel van 80x45 die het wachten niet waard is (vele uren tegenover een paar seconden bij een (moeilijke, niet uit een boekje) puzzel van 25x25) en waarbij ik dus een advies zocht m.b.t. het algoritme om mogelijkheden te genereren. Met mijn kennis zou ik op het moment geen andere manier weten te verzinnen om deze puzzel op te lossen dan mijn huidige aanpak, en hoogstens de manier om mogelijkheden te verzinnen te verbeteren.

Ik ben nu dus bezig met ngmPos() die oorspronkelijk dus álle mogelijkheden afloopt, maar nu dus tijdens het genereren rekening houdt met posities die niet kunnen en posities die móeten worden ingevuld. Met die laatste zit ik nu vast, maar als dit werkt sla ik vele mogelijkheden over en zou als het goed is de gemiddelde tijd om een puzzel op te lossen drastisch moeten worden teruggebracht.

Acties:

tekno

Soultaker schreef op dinsdag 25 januari 2005 @ 17:52:
Oh trouwens, je hoeft maar één NP-compleet probleem te reduceren tot het probleem in kwestie, omdat uit de NP-compleetheid van dat probleem al volgt dat alle andere problemen indirect ook te reduceren zijn tot het probleem waarvan je bewijst dat het NP-compleet is.

En die reductie dient dan ook nog eens in polynomiale tijd plaats te vinden!

Verder is het oplossen van deze puzzels inderdaad interessant, helaas is de source van de toenmalige winnaar van de programming contest niet meer beschikbaar. Welke gebruik maakte van backtracking en toch zeker efficient te noemen was. Zeker in verhouding tot de zooi die ik toendertijd heb ingeleverd.

dinsdag 25 januari 2005 22:59

Acties:

woensdag 26 januari 2005 04:04

Topicstarter

Wat was het principe achter dat backtracken?

Acties:

woensdag 26 januari 2005 12:16

JeRa: ik gok ruwweg hetzelfde als wat jij van plan was. Er was toen ook getest met puzzels uit boekjes, dus met een paar keer backtracken kom je dan altijd wel goed uit. Het blijft een combinatorisch probleem en dat los je op met backtracken gecombineerd met handig afkappen. De kwaliteit van het algoritme valt en staat bij hoe efficiënt je mogelijkheden sorteert en afkapt.

Wat dat betreft zit je dus wel redelijk op de goede weg, denk ik, maar ik weet niet of er voor deze toepassing nog slimme trucs toe te passen zijn. Heel veel combinatorische problemen zijn gewoon NP-compleet (of gewoon in NP).

(Wat trouwens wel leuk is om over na te denken is een variant, waarbij op de rijen en kolomen alleen het totale aantal ingekleurde vakjes gegevens is (in plaats van dit totaal uitgesplitst naar complete runs). Als zo'n puzzel een unieke oplossing heeft, is die wel in polyomiale tijd te vinden; zelfs heel erg efficiënt geloof ik (of het lineair was weet ik niet meer). Misschien is het een idee om te beginnen met zo'n probleem (want dat kun je makkelijk genereren) en dan alle oplossingen die niet voldoen te verwerpen. Geen idee hoe efficiënt dat is.)

[ Voor 9% gewijzigd door Soultaker op 26-01-2005 04:05 ]

Acties:

woensdag 26 januari 2005 12:31

JeRa schreef op dinsdag 25 januari 2005 @ 21:32:
[...]

In de praktijk valt dat wel mee. Stel dat hij begint met een rij waar maar twéé mogelijkheden zijn, en hij kiest de verkeerde, dan zal de puzzel al snel vastlopen (mits die oplossing niet mogelijk is) doordat er bijvoorbeeld geen mogelijkheden meer zijn voor een bepaalde rij of kolom. Het aantal mogelijkheden is inderdaad gigantisch, maar in de praktijk wordt de goede oplossing er al snel tussenuit gepikt.

Dat valt vaak niet mee. Verder in de puzzel kan het nog vaker voorkomen dat je moet gokken.

Bijvoorbeeld:
[code]
[/code]

[ Voor 109% gewijzigd door Daos op 03-02-2005 20:42 . Reden: Voorbeeld was niet uniek ]

Acties:

woensdag 26 januari 2005 12:44

Because he doesn't row...

Soultaker schreef op woensdag 26 januari 2005 @ 04:04:
Wat dat betreft zit je dus wel redelijk op de goede weg, denk ik, maar ik weet niet of er voor deze toepassing nog slimme trucs toe te passen zijn. Heel veel combinatorische problemen zijn gewoon NP-compleet (of gewoon in NP).

Hehe, doe je het weer

NP staat niet voor "non-polynomial" maar voor "non-deterministic polynomial". Het sorteren van een set is ook een NP probleem, want ik kan van elke set in polynomiale (lineaire) tijd verifieren of de set gesorteerd is. Toch weten we voor dit probleem dat het in O(nlogn) is op te lossen, polynomiaal dus. Het gaat om het bestaan van een polynomiaal algoritme, met non-deterministische input. Een oracle machine dus, die voor een brute force algoritme altijd meteen de eerst keer goed gokt.

Dat deze puzzel daaraan voldoet is duidelijk; je kan namelijk elke rij en kolom lineair afscannen op correctheid, dus dat is een kwadratische operatie, en dus NP. Of het NPC is weet ik niet, ik denk het wel, want ik vermoed dat je het satisfiability probleem op een redelijk simpele wijze hierheen kan herleiden

Acties:

woensdag 26 januari 2005 13:03

Zoijar schreef op woensdag 26 januari 2005 @ 12:31:
Hehe, doe je het weer NP staat niet voor "non-polynomial" maar voor "non-deterministic polynomial". Het sorteren van een set is ook een NP probleem, want ik kan van elke set in polynomiale (lineaire) tijd verifieren of de set gesorteerd is. Toch weten we voor dit probleem dat het in O(nlogn) is op te lossen, polynomiaal dus. Het gaat om het bestaan van een polynomiaal algoritme, met non-deterministische input. Een oracle machine dus, die voor een brute force algoritme altijd meteen de eerst keer goed gokt.

Zoals ik het begrijp; heb je in de overkoepelende klasse NP een subklasse P (problemen oplosbaar in polynomiale tijd met een algoritme voor een deterministische machine) en een subklasse NPC (problemen oplosbaar in polynomiale tijd met een algoritme voor een non-deterministische machine en te verifiëren in P).

Voor het sorteren van een set is een oplossing in P. Dat is wel een subklasse van NP maar als ik het over een NP-algoritme heb dan bedoel ik dus "NP behalve P". Kun je bovendien het probleem herleiden tot een NPC probleem dan weet je vrij zeker dat het onmogelijk in polynomiale tijd in een deterministische machine op te lossen is (als je er van uitgaat dat P != NP, wat eigenlijk niet bewezen is).

Vandaar dat ik er van uit ga dat NPC problemen niet in polynomiale tijd op te lossen zijn. Klopt toch, denk ik? Of maak ik weer een fout?

Acties:

vrijdag 28 januari 2005 22:46

Because he doesn't row...

Ja ok, daar zit wel wat in, maar het is niet echt netjes. Ten eerste als P=NP, dan bestaan er geen problemen "NP behalve P", en kies je uit een lege set. Ten tweede is een probleem niet niet-P, als je aantoont dat het NP is. Dat voorkom jij door NP te definieren als NP-P, maar dan zit je weer bij punt 1. Verder 'geloof' ik erin dat de vraag onbeslisbaar is, in dat geval zouden jouw uitspraken dat ook zijn met deze definitie. (En nu maak ik dezelfde fout, maar anders, dus dat haal ik even weg

)

[ Voor 12% gewijzigd door Zoijar op 26-01-2005 13:05 ]

Acties:

donderdag 3 februari 2005 09:07

Topicstarter

Ik wilde even mededelen dat ik nu het algoritme slechts zó heb gewijzigd dat 't de plekken waar het zeker niet kan overslaat, en daarmee dus een hoop combinaties niet hoeft te maken.

De resultaten zijn schokkend. Alhoewel ik het in PHP heb getest en eigenlijk letterlijk in C++ heb overgenomen (erg lelijk gecode), is de parsetime van een puzzel van 80x45 van 62 uur naar 3 minuten teruggebracht. Ik ben blij.

Acties:

tekno

Daos schreef op woensdag 26 januari 2005 @ 12:16:
[...]

Dat valt vaak niet mee. Verder in de puzzel kan het nog vaker voorkomen dat je moet gokken.

Bijvoorbeeld:

code:

                  1 1 1 1   1 1 1 1   1 1 1 1   1 1 1 1   1 1 1 1   1 1 1 1 
                  1 1 1 1   1 1 1 1   1 1 1 1   1 1 1 1   1 1 1 1   1 1 1 1 
                  1 1 1 1   1 1 1 1   1 1 1 1   1 1 1 1   1 1 1 1   1 1 1 1 
                  1 1 1 1   1 1 1 1   1 1 1 1   1 1 1 1   1 1 1 1   1 1 1 1 
1 1 2 1 1 2 1 1 2 X . . X . . X X . . X . . X . . X X . . X . . X . . X X . 
2 1 1 2 1 1 2 1 1 . X X . . X . . X . . X X . . X . . X . . X X . . X . . X 
                  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
2 1 1 2 1 1 2 1 1 . X X . . X . . X . . X X . . X . . X . . X X . . X . . X 
1 1 2 1 1 2 1 1 2 X . . X . . X X . . X . . X . . X X . . X . . X . . X X . 
                  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
1 1 2 1 1 2 1 1 2 X . . X . . X X . . X . . X . . X X . . X . . X . . X X . 
2 1 1 2 1 1 2 1 1 . X X . . X . . X . . X X . . X . . X . . X X . . X . . X 
                  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
2 1 1 2 1 1 2 1 1 . X X . . X . . X . . X X . . X . . X . . X X . . X . . X 
1 1 2 1 1 2 1 1 2 X . . X . . X X . . X . . X . . X X . . X . . X . . X X .

Enige probleem is dan weer dat deze puzzel meerdere oplossingen heeft

donderdag 3 februari 2005 10:40

Acties:

joepP

JeRa schreef op vrijdag 28 januari 2005 @ 22:46:
Ik wilde even mededelen dat ik nu het algoritme slechts zó heb gewijzigd dat 't de plekken waar het zeker niet kan overslaat, en daarmee dus een hoop combinaties niet hoeft te maken.

De resultaten zijn schokkend. Alhoewel ik het in PHP heb getest en eigenlijk letterlijk in C++ heb overgenomen (erg lelijk gecode), is de parsetime van een puzzel van 80x45 van 62 uur naar 3 minuten teruggebracht. Ik ben blij.

Ik heb nog wel een ideetje voor een verdere optimalisatie.

Je maakt nu expliciet alle mogelijkheden voor een rij/kolom aan. Dat doe je om al die mogelijkheden af te kunnen lopen. Is het niet veel sneller om voordat je dat doet eerst voor elk nog onbekend vakje in een rij/kolom beide waarden vol & leeg in te vullen, en dan te kijken of de rij/kolom uberhaubt nog gevuld kan worden? Dit herhaal je voor elke rij/kolom tot er niets meer verandert, en pas daarna ga je verder met het één voor één proberen van de overgebleven mogelijkheden.

donderdag 3 februari 2005 11:26

Acties:

donderdag 3 februari 2005 12:25

tekno schreef op donderdag 03 februari 2005 @ 09:07:
[...]

Enige probleem is dan weer dat deze puzzel meerdere oplossingen heeft

Laat dat dan maar eens zien.

Acties:

tekno

code:

                  1 1 1 1   1 1 1 1   1 1 1 1   1 1 1 1   1 1 1 1   1 1 1 1 
                  1 1 1 1   1 1 1 1   1 1 1 1   1 1 1 1   1 1 1 1   1 1 1 1 
                  1 1 1 1   1 1 1 1   1 1 1 1   1 1 1 1   1 1 1 1   1 1 1 1 
                  1 1 1 1   1 1 1 1   1 1 1 1   1 1 1 1   1 1 1 1   1 1 1 1 
1 1 2 1 1 2 1 1 2 . . X . . X . X X . X . . X . . X X . . X . . X . . X X . 
2 1 1 2 1 1 2 1 1 X X . X . . X . . . . X X . . X . . X . . X X . . X . . X 
                  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
2 1 1 2 1 1 2 1 1 . X X . . X . . X . . X X . . X . . X . . X X . . X . . X 
1 1 2 1 1 2 1 1 2 X . . X . . X X . . X . . X . . X X . . X . . X . . X X . 
                  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
1 1 2 1 1 2 1 1 2 X . . X . . X X . . X . . X . . X X . . X . . X . . X X . 
2 1 1 2 1 1 2 1 1 . X X . . X . . X . . X X . . X . . X . . X X . . X . . X 
                  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
2 1 1 2 1 1 2 1 1 . X X . . X . . X . . X X . . X . . X . . X X . . X . . X 
1 1 2 1 1 2 1 1 2 X . . X . . X X . . X . . X . . X X . . X . . X . . X X .

En nog vele anderen

donderdag 3 februari 2005 17:23

Acties:

donderdag 3 februari 2005 21:02

Topicstarter

joepP schreef op donderdag 03 februari 2005 @ 10:40:
[...]

Ik heb nog wel een ideetje voor een verdere optimalisatie.

Je maakt nu expliciet alle mogelijkheden voor een rij/kolom aan. Dat doe je om al die mogelijkheden af te kunnen lopen. Is het niet veel sneller om voordat je dat doet eerst voor elk nog onbekend vakje in een rij/kolom beide waarden vol & leeg in te vullen, en dan te kijken of de rij/kolom uberhaubt nog gevuld kan worden? Dit herhaal je voor elke rij/kolom tot er niets meer verandert, en pas daarna ga je verder met het één voor één proberen van de overgebleven mogelijkheden.

Zou je het kunnen uitleggen met een voorbeeld? Zoals ik het nu begrijp moet ik eerst 2^{aantal_onbekende_vakjes} keer testen of een rij/kolom gevuld kan worden, en daarna pas kijken naar de mogelijkheden. Dat lijkt me niet de bedoeling, of ik begrijp het gewoon verkeerd

Acties: