Das k-Center-Applet

• Beschreibung
• Spiel starten
• Aufgabenstellung
• Dokumentation

Beschreibung

Beim sogenannten k-Center Problem geht es darum, zu einer gegebenen Menge von Punkten und einer Anzahl k von Zentren, diese so zu platzieren, dass der weiteste Abstand eines der Punkte zu seinem nächstgelegenen Zentrum minimiert wird. Die folgende Abbildung zeigt beispielsweise eine 10-Center Lösung für 150 Punkte einer Deutschlandkarte.

Dieses Applet gibt dem Benutzer die Möglichkeit, in einer Menge von Punkten selbst k Zentren zu platzieren und diese solange zu verschieben, bis seiner Meinung nach eine gute Lösung erreicht wurde. Anschließend bietet das Applet die Möglichkeit, die gefundene Lösung mit einer tatsächlichen (approximativen) Optimallösung zu vergleichen.

Bedienung des Applets

Um das Applet zu starten, klicken Sie oben auf Spiel starten. Es wird anschließend ein Startbildschirm angezeigt, der folgende Möglichkeiten bietet.

• Geben Sie die gewünschte Karte, die gewünschte Anzahl von Orten, die auf dieser Karte verwendet werden sollen, sowie die gewünschte Anzahl an Zentren, die Sie platzieren möchten, an. Klicken Sie dann auf Start oder drücken Sie die Eingabetaste, um ein neues Spiel mit dieser Konfiguration zu starten.
• Alternativ können Sie auch eine Spielnummer eingeben, und anschließend auf Start klicken oder die Eingabetaste drücken, um ein neues Spiel zu starten. Die Spielnummer eines laufenden Spiels können Sie im Dialogfeld Spielinformationen erfahren (siehe unten).

Wenn das Spiel gestartet ist, stehen Ihnen folgende Möglichkeiten zur Verfügung.

• Verschieben Sie die Zentren mit gedrückter linker Maustaste.
• Verändern Sie den Radius, der durch die Zentren abgedeckt werden soll, mit gedrückter rechter Maustaste. Um eine gültige Lösung zu erhalten, müssen alle Orte überdeckt sein. Überdeckte bzw. nicht überdeckte Orte werden in grün bzw. rot dargestellt.
• Klicken Sie auf Neues Spiel, um das laufende Spiel zu beenden und zum Startbildschirm zurückzukehren.
• Klicken Sie auf Mehr..., um eine der folgenden Aktionen vorzunehmen.
  • Spiel neu beginnen - Dasselbe Spiel wird neu begonnen.
  • Radius automatisch anpassen - Der Radius der von Ihnen platzieren Zentren wird automatisch angepasst. Die rechte Maustaste hat bei dieser Einstellung keine Wirkung.
  • Radius nicht automatisch anpassen - Dies hebt die eben genannte Einstellung wieder auf.
  • Spielinformationen - Öffnet ein Dialogfenster, das folgende Informationen über das laufende Spiel anzeigt. Der Name der Karte, die Anzahl der Orte, die Anzahl der Zentren, die Approximationsgüte (siehe unten), die erzielte Genauigkeit (siehe unten), die bisher verstrichene Rechenzeit, und die Spielnummer.
  • Einstellungen - Öffnet ein Dialogfenster, das die Approximationsgüte anzeigt oder festlegt und die erzielte Genauigkeit anzeigt.
• In der Dropdown-Liste Lösung können Sie festlegen, ob die gefundene Optimallösung nicht, auch, oder nur angezeigt werden soll, um Sie mit Ihrer Lösung zu vergleichen. Falls die Optimallösung noch nicht vollständig berechnet wurde, wird ein Dialogfenster geöffnet, das den aktuellen Fortschritt der Berechnung anzeigt.

Die Approximationsgüte spezifiziert die zulässige Toleranz, innerhalb der die approximative Optimallösung ermittelt werden soll. Die approximative Lösung ist also höchstens um diesen Faktor schlechter als die tatsächliche Optimallösung. Je kleiner dieser Wert ist, desto genauer ist die Lösung und desto mehr Zeit wird für die Berechnung in Anspruch genommen. Dieser Wert muss immer größer als 1 sein. Hinweis: Sie können die Approximationsgüte jederzeit im Einstellungen Dialogfenster (siehe oben) anpassen.

Die erzielte Genauigkeit spezifiziert die zur Zeit bereits erreichte Genauigkeit. Sobald dieser Wert kleiner oder gleich der Approximationsgüte ist, wird die Berechnung abgebrochen und die Lösung kann angezeigt werden.

Wird im Spiel die Optimallösung angezeigt, wird zusätzlich ein Hinweis mit einer Bewertung Ihrer Lösung angezeigt. Je kleiner dieser Wert ist, desto näher ist Ihre Lösung an der Optimallösung. Die Optimallösung entspricht dabei einem Wert von 1. Hinweis: Dieser Wert kann nur angezeigt werden, wenn Sie eine gültige Lösung angegeben haben, d.h. wenn alle Orte überdeckt sind.

Durch einen Klick auf die Schaltfläche Eigene Karte hinzufügen bzw. Eine weitere Karte hinzufügen können Sie eigene Datensätze zum Spiel hinzufügen. Beachten Sie hierzu bitte die Kartenspezifikationen.

---