[HaBo]

**CDW** · 08.02.09, 17:50

Backtracking mit einfacher Heuristik

kann sich zwar nicht mit Lescos Implementierung messen (entweder nutzt er noch ein paar Regeln oder ich sollte weniger Speicher "fressen"

), braucht aber für 8x8 ~31ms, 20x20 ~ 1.7 Sek, 50x50 ~ 70 Sek.

Ausgabe für 5x5:

spoiler

Lesco · 08.02.09, 18:09

Zitat:

Original von CDW
(entweder nutzt er noch ein paar Regeln oder ich sollte weniger Speicher "fressen"

)

Die einzige (algorithmische) Optimierung, die ich verwendet habe ist die Sortierung der Nachfolgefelder anhand der Anzahl ihrer jeweiligen gültigen Nachfolger. Meine Prolog-Unkenntnis hindert mich jedoch daran, zu erkennen, ob das bei deiner Lösung auch schon so gemacht wird.

**CDW** · 09.02.09, 12:30

Zitat:

Original von Lesco Meine Prolog-Unkenntnis hindert mich jedoch daran, zu erkennen, ob das bei deiner Lösung auch schon so gemacht wird.

spoiler

EDIT:
Ich hab das ein wenig "optimiert" - statt einer vorgefertigten Koordinatenliste wird nun erst bei Bedarf ein Zug generiert. Auch wird für die Prüfung/Speicherung getätigter Züge statt einfacher Liste nun eine Associations (Bintree) benutzt. Entsprechend sind auch die Zeiten:
1.7Sek werden nun für 80x80 Feld gebraucht, 160x160 ist immerhin in 6Sek gemacht, 200x200 in ~10 Sek.

nicht mehr so elegant

MontyPerl · 10.02.09, 15:27

Na dann will ich doch auch nochmal

springerproblemReloaded

Mit der stumpfen (aber effektiven) Optimierung + es ist jetzt reines ANSI C (also viel portabler geht nimma). Außerdem nimmts jetzt die Startx- und Starty-Koordinaten als optionales 3. und 4. Argument. (Default ist 0 0)

Code:

#include <stdio.h>
#include <stdlib.h>
#include "stackChar.h"

#define VISITED 1

typedef struct {
    int xdim, ydim;
    int **f;
    int **moves;
} field;

typedef struct stepStruct {
    int dx, dy;     /* delta x and delta y */
    int succ;       /* number of valid successors */ 
} step;

field *getField(int x, int y);
int isValidPos(field *f, int x, int y);
step *getSteps(field *f, int x, int y);
void *xmalloc(int size);
void printField(field *f, int currx, int curry);
void clearField(field *f);
int solve(field *f, stack s, int x, int y, int visited);
int stepsort(const void *a, const void *b);

int main(int argc, char *argv[]) {
    int x, y, startx, starty, success;
    field *f;
    stack solution;
    if (argc == 3) {
        startx = 0;
        starty = 0;
    }
    else if (argc == 5) {
        startx = atoi(argv[3]);
        starty = atoi(argv[4]);
    }
    else {
        fprintf(stderr, "usage: %s <x> <y> [<startx> <starty>]\n", argv[0]);
        exit(EXIT_FAILURE);
    }
    x = atoi(argv[1]);
    y = atoi(argv[2]);
    solution = newStack(x * y * 2);
    f = getField(x, y);
    success = solve(f, solution, startx, starty, 1);
    if (success) {
        printf("success\n");
        if (x <= 50 && y <= 40) {
            clearField(f);
            while (!isEmptyStack(solution)) {
                x = shiftStack(solution);
                y = shiftStack(solution);
                f->f[y][x] |= VISITED;
                printField(f, x, y);
            }
        }
    }
    else {
        printf("couldn't find a solution\n");
    }
    return success ? EXIT_SUCCESS : EXIT_FAILURE;
}

int solve(field *f, stack s, int x, int y, int visited) {
    int i;
    step *steps;
    f->f[y][x] ^= VISITED;
    pushStack(s, x);
    pushStack(s, y);
    if (visited == (f->xdim * f->ydim)) {
        return 1;
    }

    if ((steps = getSteps(f, x, y)) == NULL) {
        f->f[y][x] ^= VISITED;
        return 0;
    }
    for (i = 0; i < 8 && steps[i].succ != -1; i++) {
        if (solve(f, s, x + steps[i].dx, y + steps[i].dy, visited + 1)) {
            return 1;
        }
    }
    popStack(s);    /* y */
    popStack(s);    /* x */
    free(steps);
    f->f[y][x] ^= VISITED;
    return 0;
}

void clearField(field *f) {
    int x, y;
    for (y = 0; y < f->ydim; y++) {
        for (x = 0; x < f->xdim; x++) {
            f->f[y][x] = 0;
        }
    }
}

void printField(field *f, int currx, int curry) {
    int x, y;
    printf("\n");
    for (x = 0; x < f->xdim; x++) {
        printf("--");
    }
    printf("\n");
    for (y = 0; y < f->ydim; y++) {
        for (x = 0; x < f->xdim; x++) {
            if (x == currx && y == curry) {
                printf("@ ");
            }
            else {
                printf("%s", f->f[y][x] & VISITED ? "o " : ". ");
            }
        }
        printf("\n");
    }
}

field *getField(int x, int y) {
    int *rows = xmalloc(x * y * sizeof(int));
    int **arr = xmalloc(y * sizeof(int *));
    int *move, **moves, xd, yd;
    int i, j;
    field *f;
    for (i = 0; i < y; i++) {
        arr[i] = &rows[i * x];
        for (j = 0; j < x; j++) {
            arr[i][j] = 0;
        }
    }
    f = xmalloc(sizeof(field));
    f->f = arr;
    f->xdim = x;
    f->ydim = y;
    /* these are the 8 movement possibilities
     * written in the form (xoffset, yoffset):
     * 2, 1; 2, -1; -2, 1; -2, -1;
     * 1, 2; -1, 2; 1, -2; -1, -2;
     */
    move = malloc(2 * 8 * sizeof(int));
    moves = malloc(8 * sizeof(int *));
    i = 0;
    for (xd = -2; xd <= 2; xd++) {
        for (yd = -2; yd <= 2; yd++) {
            if (xd && yd && (abs(xd) != abs(yd))) {
                move[i*2] = xd;
                move[(i*2)+1] = yd;
                moves[i] = &move[i*2];
                i++;
            }
        }
    }
    f->moves = moves;
    return f;
}

int isValidPos(field *f, int x, int y) {
    if (x < 0 || y < 0 || x >= f->xdim || y >= f->ydim) {
        return 0;
    }
    else if (f->f[y][x] & VISITED) {
        return 0;   /* this one was already visited! */
    }
    return 1;
}

step *getSteps(field *f, int x, int y) {
    int i, j, k, succ;
    step *steps = xmalloc(8 * sizeof(step));
    j = 0;
    for (i = 0; i < 8; i++) {
        if (isValidPos(f, x + f->moves[i][0], y + f->moves[i][1])) {
            steps[j].dx = f->moves[i][0];
            steps[j].dy = f->moves[i][1];
            succ = 0;
            for (k = 0; k < 8; k++) {
                if (
                  isValidPos(f, x + steps[j].dx + f->moves[k][0], y + steps[j].dy + f->moves[k][1])
                ) {
                    succ++;
                }
            }
            steps[j].succ = succ;
            j++;
        }
    }
    if (j == 0) {
        free(steps);
        return NULL;
    }
    else if (j < 8) {
        steps[j].succ = -1;
    }
    qsort(steps, j, sizeof(step), &stepsort);
    return steps;
}

int stepsort(const void *a, const void *b) {
    if (( (step *) a)->succ == ( (step *) b)->succ) {
        return 0;
    }
    if (( (step *) a)->succ > ( (step *) b)->succ) {
        return 1;
    }
    else {
        return -1;
    }
}

void *xmalloc(int size) {
    void *ptr = malloc(size);
    if (ptr == NULL) {
        fprintf(stderr, "not enough memory\n");
        exit(EXIT_FAILURE);
    }
    return ptr;
}

Außerdem ein patch für den char Stack: (hat jetzt eine shift Methode, damit man den "replay" in der richtigen Reihenfolge anschauen kann)

Code:

23a24
> char shiftStack(stack s);
61a63,77
> char shiftStack(stack s) {
>     int i;
>     char c;
>     if (s->pos == -1) {
>         return POP_EMPTY;
>     }
>     c = s->arr[0];
>     for (i = 1; i <= s->pos; i++) {
>         s->arr[i-1] = s->arr[i];
>     }
>     s->arr[s->pos] = '\0';
>     s->pos--;
>     return c;
> }
> 
62a79
>     char c;
66c83
<     char c = s->arr[s->pos];
---
>     c = s->arr[s->pos];

Das Feld wird jetzt auch nur noch ausgegeben, wenn n <= 50 und m <= 40 ist. (Größeres ist für die meisten Terminals einfach nicht sinnvoll darstellbar.)

Code:

$ time ./springerproblem 360 360
success

real    0m0.309s
user    0m0.219s
sys     0m0.069s
$ # Vergleich mit Lesco's Lösung:
$ time ./haskellLoesung '(50,50)' '(1,1)' >/dev/null

real    0m0.324s
user    0m0.242s
sys     0m0.010s

$ time ./springerproblem 50 50
success

real    0m0.008s
user    0m0.005s
sys     0m0.003s

CWD's Lösung (zumindest die SWIPL Lösung, denn die konnte ich ausprobieren..) ist nochmal ein paar Dimensionen langsamer. Und bei mir bricht sie bereits bei 100x100 Feldern ab mit "Out of global stack", trotz 500mb stack..
Mein Rechner:

Code:

$ grep 'name' /proc/cpuinfo 
model name      : Intel(R) Pentium(R) 4 CPU 1.70GHz
$ grep MemTotal /proc/meminfo 
MemTotal:       512684 kB

Genug Sch****vergleich?

**CDW** · 11.02.09, 18:41

Pff, richtige Männer messen in cm

(oder: traue keiner Statistik, die du nicht selbst gefälscht hast

)
Erweiterte Heuristik rein: (aus gleichwertigen Zügen werden nun zuerst die zum Rand nächsten abgearbeitet)

SICStus

Nun cheaten wir:

cheat 1, SICStus

cheat2, SICSTus

Speicherverbrauch ist natürlich ein Problem - aber eher Interpreterbezogen.
Bsp:

100*100 Feld, SICStus

das ist die Statisitk nach der Ausgabe der ersten Lösung (d.h die Choicepoints für andere sind noch im Speicher). Wie man sieht sind nur 5 MB global stack belegt.
dasselbe mit SWI-Prolog, 32 bits, Version 5.6.55, Windows:

100*100 Feld

Sind zwar etwas mehr - aber auch noch deutlich unter 10 MB.

Anzeige

- Anzeige -

Themen-Optionen
Druckbare Version zeigen Jemanden per E-Mail auf dieses Thema hinweisen
Ansicht
Linear-Darstellung Zur Hybrid-Darstellung wechseln Zur Baum-Darstellung wechseln

Ähnliche Themen
Thema	Autor	Forum	Antworten	Letzter Beitrag
Springerproblem	Nornagest	Programmieraufgaben	16	19.04.04 16:20

[HaBo]

Springerproblem