WikiDer > Geradlinige Kreuzungszahl
Geradlinige Kreuzungszahl ist ein verteiltes Rechnen Projekt unter dem BOINC Plattform läuft. Ziel dieses Projektes ist es, die Mindestanzahl von Kreuzungen in Grafiken mit geraden Linien.
Anzahl der Kreuzungen ermitteln
In einem Geradengraphen mit n Knoten ist es äußerst schwierig, die minimale Anzahl von Schnittpunkten zu bestimmen. Für kleine Graphen (zB n = 4 oder 5) ist es immer noch einfach, aber mit zunehmender Anzahl von Knoten wird es schnell schwierig. Eine vollständige Zählung mit 20 Knoten ist bereits unbekannt. Sie wurde bereits für Graphen mit weniger als 19 und 21 Knoten bestimmt. Die Schwierigkeit der Berechnung liegt in der Vielzahl unterschiedlicher Konfigurationen. für n = 11 gibt es bereits 2.334.512.907 verschiedene Konfigurationen.
Die Anwendung
Die Anwendung ist ein Programm namens CAPE (CKomplett einabstrakt pSalbe EVerlängerung). Diese Anwendung nimmt eine Ausgangssituation von 11 Punkten und erweitert diese dann auf 12,13...,20 Punkte. Nach jeder Erweiterung werden die Situationen entfernt, in denen die Anzahl der Kreuzungen selbst bei einer weiteren Erweiterung sicherlich nicht minimal sein wird. Nicht einmal alle 11-Punkte-Ausgangssituationen müssen überprüft werden. Als Ergebnis ist die Länge der "Arbeitseinheiten" (durchzuführende Berechnungssätze) sehr variabel und eine Arbeitseinheit kann einige Minuten oder mehrere Stunden dauern. Es gibt maximal 10 Stunden. Eine Arbeitseinheit besteht aus einer Ausgangssituation von 11 Punkten und einigen Zahlen, die den Ausbau angeben. Stellt sich heraus, dass dies zu lange dauert, wird die Arbeitseinheit in mehrere Einheiten aufgeteilt.