Rectilinear Crossing Number

Rectilinear Crossing Number Projekt (RCN)
Ziel:	Suche nach der kleinsten Anzahl von Kreuzungen eines Graphen von n-Punkten mit geraden Linien als Kanten
Kategorie:	Mathematik
Homepage:	http://dist.ist.tugraz.at/cape5/
Betreiber:	University of Technology, Graz
Status:	inaktiv/beendet
SETI.Germany
Forenthread:	SETI.Germany Forum

Bei diesem Mathematik-Projekt aus dem Bereich der kombinatorischen Geometrie beschäftigt man sich mit der Suche nach der kleinsten Anzahl von Kreuzungen eines Graphen von n-Punkten mit geraden Linien als Kanten. Dabei sollen keine drei Punkte auf einer gemeinsamen Linie liegen.

Für eine kleine Anzahl von Punkten ist dieses Problem, was u.a. in der Optimierung von Transportproblemen und z.B. auch im Print-Layout eine Rolle spielt, relativ leicht auflösbar. Nachfolgende Grafik verdeutlicht das z.B. für 5 Punkte

Für größere Punktmengen ist es aber sehr schwer, die beste Konfiguration zu ermitteln, da die Anzahl der kombinatorisch verschiedenen Arten, diese Punkte anzuordnen, exponentiell wächst. Zum Beispiel gibt es für n=11 Punkte bereits 2.334.512.907 verschiedene Möglichkeiten.

Hier die Ergebnisse der Kreuzungszahlen:

K(12) = 153, K(13) = 229, K(14) = 324, K(15) = 447, K(16) = 603 und K(17) = 798

K(19) = 1318 und K(21) = 2055

Im Dezember des Jahres 2006 ist es schließlich gelungen, mit einer weltweiten Computerkapazität von 10.000 CPU-Stunden pro Tag auch die Kreuzungszahl für Graphen mit 18 Knoten zu berechnen. Sie beträgt, wie im Januar 2007 rechnerisch bestätigt worden ist, 1029.

Das Projekt RCN berechnet daher zurzeit den Graph für n=20.

Dabei ist (Anfang Juli 2009) die W7er-Serie beendet worden und auch die W8er-Serie (Mitte Oktober 2010) – aktuell ist eine neue Serie (st***) am Start ...

Seit 14.01.2011 ist das Projekt offline – die letzten noch offenen Wus werden lokal auf den Servern des Projektbetreibers gerechnet.

Sobald „finale“ Informationen bekannt sind, werden diese hier ergänzt.

verfügbare Anwendungen

Aktuell sind die TCAPE Crossing Number-Apps tcape-crossing 5.63 für Win, 5.59 für Linux und 5.61 für Mac. Eine 64-Bit-Version wird seit 3. März 2008 nun neben Linux (5.53) auch für Windows angeboten (5.54)! Die maximale Laufzeit beträgt im Moment (projektseitig voreingestellt) für die Serie st*** 24h.

Ein Bildschirmschoner (Grafik) ist seit 24.01.2008 integriert! (wurde projektseitig aber wieder temporär akti- bzw. deaktiviert)

manuelles Verändern der maximalen Laufzeit einer WU

1. BOINC beenden!
2. Die Datei client_state.xml mit einem Texteditor öffnen. (Die Datei befindet sich in den „älteren“ Versionen standardmäßig im Verzeichnis .../Programme/BOINC/. Ein ausreichender Texteditor wäre der integrierte von Windows, welcher über Start -> Alle Programme -> Zubehör -> Editor gestartet wird.
3. Für jede WU findet man dort (in abgewandelter Form) eine solche Zeile:

   data11cr102 17 TIME=86400 NMAX=20 OUTPUTSIZE=18 OUTPUTFILE=W4_0302_0925_1551_0001 FROM=302 TO=302 RECSTART=925,1551,1 RECFINAL=925,1551,501

4. Diese Zeile befindet sich im letzten Drittel der Datei. Diese kann man mittels einer Suche über das Menü des Editors auch direkt „anspringen“, indem man einfach als Suchbegriff TIME=86400 verwendet.
5. Der Wert hinter TIME gibt die max. Laufzeit an, die der WU eingeräumt wird – hier also 86400 s = 24 h. Wenn man dies nun z.B. mit 100000 ersetzt, verändert sich die Laufzeit dementsprechend.
6. Datei speichern und BOINC neu starten.

Info: Die Validierung und das Granten der WUs erfolgt ohne Probleme
      und seitens RCN wurden gegen dieses Editieren keine Einsprüche erhoben!

Projektende

14. Januar 2011

Weblinks

• Anwendungen
• RSS-Feed