Herzlich Willkommen, lieber Gast!
  Sie befinden sich hier:

  Forum » Rätselecke » @virtual: Geburtstagsrätsel

Forum | Hilfe | Team | Links | Impressum | > Suche < | Mitglieder | Registrieren | Einloggen
  Quicklinks: MSDN-Online || STL || clib Reference Grundlagen || Literatur || E-Books || Zubehör || > F.A.Q. < || Downloads   

Autor Thread - Seiten: [ 1 ] [ 2 ] > 3 <
020
09.01.2009, 21:02 Uhr
kronos
Quotenfisch
(Operator)


Hab' gegen deine alte Version getestet. Bin grad zu faul nochmal zu testen, kuck nebenher Terminator 3 und hab' von dem Film noch kaum was mitbekommen (ist allerdings auch kein großer Verlust).


Zitat:
Nachtrag: Die Liste werde ich mir übrigens wohl aufheben - das könnte irgendwann noch mal nützlich sein.

Jo, die ist hübsch, aber du bekommst evtl. Ärger wenn du ein Element X löschst, zwischen dessen prev und next was anderes einfügst und X wiederbelebst...
--
main($)??<-$<='?'>>2?main($-!!putchar(
(("$;99M?GD??(??/x0d??/a:???;a"+'?'/4)
??($??)+'?'/3-2-1+$%2)??''?')):'?';??>
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
021
09.01.2009, 21:08 Uhr
0xdeadbeef
Gott
(Operator)


Das ist, in der Tat, ein cleverer Ansatz. Beeindruckend, da wär ich so schnell nicht drauf gekommen. Es dürfte auch besser skalieren als meine Lösung.

Du gewinnst diese Runde.

Und jetzt werde ich deinen Ansatz in schamloser Weise stehlen und kucken, ob ich da noch mehr rausholen kann.
--
Einfachheit ist Voraussetzung für Zuverlässigkeit.
-- Edsger Wybe Dijkstra

Dieser Post wurde am 09.01.2009 um 21:08 Uhr von 0xdeadbeef editiert.
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
022
09.01.2009, 21:15 Uhr
kronos
Quotenfisch
(Operator)


Danke und wo wir bei schamlos stehlen sind - schon mal in Posting 007 gekuckt? Bin allerdings auch gerade erst draufgestoßen, also wieder mal konvergente Evolution. Nemo war sicher auch nicht der erste.


Zitat:

Und jetzt werde ich deinen Ansatz in schamloser Weise stehlen und kucken, ob ich da noch mehr rausholen kann.

Bin ich mal gespannt, werde ähnliches versuchen. Machen wir eigentlich mit globals oder ohne?
--
main($)??<-$<='?'>>2?main($-!!putchar(
(("$;99M?GD??(??/x0d??/a:???;a"+'?'/4)
??($??)+'?'/3-2-1+$%2)??''?')):'?';??>
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
023
09.01.2009, 21:28 Uhr
0xdeadbeef
Gott
(Operator)


Okay, in verkürzter Form (den Listenkram habe ich in ein eigenes Modul ausgelagert, ist aber unverändert:

C++:
#include "clist.h"

#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#ifndef DIMENSION
#define DIMENSION (8)
#endif

typedef struct {
  int y[DIMENSION];
  size_t size;
} damen;

static char delim_line[DIMENSION * 2 + 6] = "\n   +";

void init_delim_line(void) {
  size_t i;

  for(i = 0; i < DIMENSION; ++i) {
    strcpy(delim_line + i * 2 + 5, "-+");
  }
}

void print_loesung(damen const *d) {
  int i, j;

  printf("   ");
  for(i = 0; i < DIMENSION; ++i) {
    printf("%2d", i + 1);
  }
  puts(delim_line);

  for(i = 0; i < DIMENSION; ++i) {
    printf("%2d |", i + 1);
    for(j = 0; j < DIMENSION; ++j) {
      printf("%c|", d->y[i] == j ? 'D' : ' ');
    }
    puts(delim_line);
  }
  puts("");
}

void backtrack_damen(damen *d, clist *left_y, unsigned *count, int *diag_lu, int *diag_rd) {
  cnode *p;
  int depth = d->size;

  if(d->size == DIMENSION) {
    ++*count;
    print_loesung(d);
  }

  for(p = left_y->head->next; p != left_y->tail; p = p->next) {
    int dlu = depth - p->val + DIMENSION;
    int drd = depth + p->val;

    if(!diag_lu[dlu] &&
       !diag_rd[drd]) {
      d->y[d->size] = p->val;

      ++d->size;
      detach_node(p);
      diag_lu[dlu] = 1;
      diag_rd[drd] = 1;

      backtrack_damen(d, left_y, count, diag_lu, diag_rd);

      diag_lu[dlu] = 0;
      diag_rd[drd] = 0;
      attach_node(p);
      --d->size;
    }
  }
}

int main(void) {
  clist coords_y;
  int i;
  damen d = { { 0 }, 0 };
  unsigned counter = 0;
  int diag [DIMENSION * 2] = { 0 },
      diag2[DIMENSION * 2] = { 0 };

  init_delim_line();
  create_clist(&coords_y);

  for(i = 0; i < DIMENSION; ++i) {
    clist_push(&coords_y, i);
  }

  backtrack_damen(&d, &coords_y, &counter, diag, diag2);

  printf("%u\n", counter);

  destroy_clist(&coords_y);

  return 0;
}


Das schlägt deine Implementierung noch mal um ein paar Sekunden (24,358 gegenüber 33,422 bei DIMENSION=15, Varianz möglich). Falls du dich wunderst, warum mein verwursteter Listenkram Performance rausholt, er skaliert besser mit der Ebenentiefe - du hast mit dem Durchlaufen sämtlicher Koordinaten linearen Aufwand.

Nachtrag: Übrigens wird ein 16x16-Brett jetzt erschwinglich - 3:50 für dich, 2:34 für mich mit der von dir (bzw. Nemo) geklauten Idee.
--
Einfachheit ist Voraussetzung für Zuverlässigkeit.
-- Edsger Wybe Dijkstra

Dieser Post wurde am 09.01.2009 um 21:40 Uhr von 0xdeadbeef editiert.
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
024
09.01.2009, 21:45 Uhr
kronos
Quotenfisch
(Operator)


Hübsch. Das die paar Checks die du durch die Liste sparst schon bei so kleinen Brettern in's Gewicht fallen hätt ich gar nicht gedacht.
--
main($)??<-$<='?'>>2?main($-!!putchar(
(("$;99M?GD??(??/x0d??/a:???;a"+'?'/4)
??($??)+'?'/3-2-1+$%2)??''?')):'?';??>
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
025
09.01.2009, 21:50 Uhr
0xdeadbeef
Gott
(Operator)


Naja, die tieferen Ebenen werden tendenziell öfter durchlaufen als die höheren - die erste nur acht mal, die letzte bei einem 16x16-Brett mit 14.772.512 Lösungen 14.772.512 mal. Zwar werden die in der Mitte am häufigsten durchlaufen, die Glockenkurve ist allerdings schon etwas zu den tieferen Rekursionstiefen verschoben. Das läppert sich halt.

Mit Mikrooptimierungen (inline-Funktionen etc.) ließe sich der Overhead wohl noch reduzieren, und wenn das jetzt ein wichtiges Projekt wäre, würde ich den Aufwand wohl auch betreiben, aber es geht mir hier mehr um proof of concept.

...oder wir warten einfach auf WHOPR.
--
Einfachheit ist Voraussetzung für Zuverlässigkeit.
-- Edsger Wybe Dijkstra

Dieser Post wurde am 09.01.2009 um 21:54 Uhr von 0xdeadbeef editiert.
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
026
09.01.2009, 22:06 Uhr
kronos
Quotenfisch
(Operator)


Gut. Da mir das Problem nicht GPGPU-geeignet scheint, geb' ich bis auf weiteres auf.
--
main($)??<-$<='?'>>2?main($-!!putchar(
(("$;99M?GD??(??/x0d??/a:???;a"+'?'/4)
??($??)+'?'/3-2-1+$%2)??''?')):'?';??>
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
027
09.01.2009, 22:14 Uhr
0xdeadbeef
Gott
(Operator)


Als Backtracking-Algorithmus ließe sich das ganze noch parallelisieren; ich nehme auch stark an, dass NQueens@Home genau das getan hat. Und mit einem Quantencomputer wäre das ganze natürlich deutlich schneller zu bewältigen.

Allerdings habe ich weder einen Quantencomputer noch ein Multicore-System, und es ist nicht ganz trivial, die Parallelisierung ohne massenhafte Datenkopiererei, die den Gewinn wieder zunichte machen sollte, umzusetzen. Von daher lasse ich das vorläufig erst mal sein.

Ist aber auch gut genug geworden, oder?
--
Einfachheit ist Voraussetzung für Zuverlässigkeit.
-- Edsger Wybe Dijkstra
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
028
13.09.2013, 13:53 Uhr
kronos
Quotenfisch
(Operator)


Hallo, hallo.
Ist ja schon ein paar Jährchen alt der Thread und vermutlich liest das hier eh keiner mehr, aber ich möchte der Vollständigkeit folgendes anmerken:


Zitat von 0xdeadbeef:
So, dass das Durchlaufen der noch vorhandenen Kandidaten da oben linear skaliert, bloß, weil ich meine Iteratoren verliere, kann ich nicht auf mir sitzen lassen. Dementsprechend habe ich, wie es wohl jeder in meiner Situation täte... Naja, also, wie ich es jedenfalls getan habe, eine Koordinatenliste in C geschrieben, die es mir erlaubt, Nodes aus- und wieder einzuhängen.


Diese Technik ist als Dancing Links bekannt, nach einem Paper von Donald E. Knuth, das ein Jahr nach beefys Posting publiziert wurde. Für mich gibt es nur drei plausible Erklärungen:

* deadbeef ist Knuth
* Knuth plagiiert aus diesem Forum



Na gut, des Pudels Kern ist natürlich, dass niemand sonst auf die Idee käme solche Lapalien zu publizieren. Jedenfalls hab' ich gerade das Paper gelesen und musste sofort an diesen Thread denken und an die gute alte Zeit, als in der Rätselecke noch gerätselt wurde...


--
main($)??<-$<='?'>>2?main($-!!putchar(
(("$;99M?GD??(??/x0d??/a:???;a"+'?'/4)
??($??)+'?'/3-2-1+$%2)??''?')):'?';??>

Dieser Post wurde am 13.09.2013 um 13:54 Uhr von kronos editiert.
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
Seiten: [ 1 ] [ 2 ] > 3 <     [ Rätselecke ]  


ThWBoard 2.73 FloSoft-Edition
© by Paul Baecher & Felix Gonschorek (www.thwboard.de)

Anpassungen des Forums
© by Flo-Soft (www.flo-soft.de)

Sie sind Besucher: