001 /*
002 * Created on 22.11.2004
003 */
004 package de.hska.info1.uebung.backtracking;
005
006 /**
007 * HausVomNikolaus ist verantwortlich eine Lösung zu finden, das Haus vom
008 * Nikolaus ab einem Knoten ohne Unterbruch zu zeichnen. Die Kanten des Hauses
009 * werden als Adjazentmatrix gespeichert {@link #haus}. Die Lösung wird mit
010 * einen Backtrackingalgorithmus gesucht {@link #sucheLoesung}.
011 *
012 * @author Christian Pape
013 */
014 public class HausVomNikolaus {
015
016 private static final int KANTE = 1;
017
018 private static final int KANTE_GEZEICHNET = 2;
019
020 /**
021 * Definiert, welche Kanten es überhaupt gibt. Man stelle sich dazu vor,
022 * dass die Anfangs- und Endpunkte der Kanten einfach als Zahlen codiert
023 * sind:
024 *
025 * <pre>
026 * 4
027 * / \
028 * / \
029 * / \
030 * 2 ----- 3
031 * |\ /|
032 * | \ / |
033 * | \ / |
034 * | / \ |
035 * | / \ |
036 * |/ \|
037 * 0-------1
038 * </pre>
039 * Gültige Kanten sind dann Kanten von Knoten 0 nach 1, von 0 nach 3
040 * und von 0 nach 2; ungültig ist aber die Kante 0 nach 4.
041 * Wenn haus[i][k] == KANTE gilt, dann ist die Kante von i nach k eine
042 * für das Haus des Nikolaus gültige Kante.
043 * Da die Kante in beiden Richtungen abgelaufen werden können, ist
044 * haus[i][j] == haus[j][i].
045 * Wenn in {@link #sucheLoesung} eine Kante "gezeichnet" wurde, dann
046 * werden sowohl haus[i][j] als auch haus[j][i] auf KANTE_GEZEICHNET gesetzt.
047 *
048 */
049 private int haus[][] = { { 0, KANTE, KANTE, KANTE, 0 },
050 { KANTE, 0, KANTE, KANTE, 0 }, { KANTE, KANTE, 0, KANTE, KANTE },
051 { KANTE, KANTE, KANTE, 0, KANTE }, { 0, 0, KANTE, KANTE, 0 } };
052
053 /**
054 * Das Haus vom Nikolaus hat gerade so viel Knoten, wie die Dimension der
055 * Adjazenzmatrix.
056 */
057 private int anzahlKnoten = haus.length;
058
059 /**
060 * Beim obigen haus ist die Anzahl Kanten 8. Damit das Suchverfahren aber
061 * möglichst allgemein ist, wird der Wert aus der gegebenen Adjazenzmatrix
062 * im Konstruktor bestimmt.
063 */
064 private int anzahlKanten;
065
066 /**
067 * Beinhaltet die Lösung als Folge der einzelnen Knoten. Der erste Knoten
068 * ist nicht hier enthalten. Zusammen mit dem Anfangsknoten, beinhaltet
069 * loesung die Folge der Knoten die zum Zeichnen des Hauses benötigt wird.
070 * <p>
071 * Eine Lösung von Knoten 0 ist zum Beispiel: 1 2 0 3 2 4 3 1. Das heisst
072 * von 0 nach Knoten 1, dann nach Knoten 2, usw, und zum Schluss von Knoten
073 * 3 nach 1.
074 * </p>
075 */
076 private int loesung[];
077
078 public HausVomNikolaus() {
079 anzahlKanten = 0;
080 for (int i = 0; i < anzahlKnoten; i++) {
081 for (int j = i; j < anzahlKnoten; j++) {
082 if (haus[i][j] == KANTE) {
083 anzahlKanten++;
084 }
085 }
086 }
087 loesung = new int[anzahlKanten];
088 }
089
090 /**
091 * Setzte alle Werte von loesung auf -1. Dies ist nötig, um später zu
092 * identifzieren, ob überhaupt eine Lösung gefunden wurde bzw. zum debuggen
093 * sinvoll
094 */
095 void initLoesung() {
096 for (int i = 0; i < loesung.length; i++) {
097 loesung[i] = -1;
098 }
099 }
100
101 /**
102 * Sucht mit Backtracking eine Zeichenreihenfolge, um das Haus vom Nikolaus
103 * ohne den Stift abzusetzten zu zeichnen.
104 *
105 * @param knoten
106 * die derzeitige Position des Zeichenstifts
107 * @param i
108 * die Anzahl bereits gezeichneter Kanten
109 *
110 * @return true, wenn eine Lösung gefunden wurde
111 */
112 boolean sucheLoesung(int knoten, int i) {
113 for (int k = 0; k < anzahlKnoten; k++) {
114 if (kanteIstUnbesucht(knoten, k)) {
115 loesung[i] = k;
116 kanteZeichnen(knoten, k);
117 if (i < loesung.length - 1) {
118 if (sucheLoesung(k, i + 1)) {
119 return true;
120 } else {
121 kanteZuruecksetzen(knoten, k);
122 loesung[i] = -1;
123 }
124 } else {
125 return true;
126 }
127 }
128 }
129
130 return false;
131 }
132
133 /**
134 * Markiert die Kante von knoten bis j in beiden Richtungen
135 * als ablaufbare Kante.
136 */
137 private void kanteZuruecksetzen(int knoten, int i) {
138 haus[knoten][i] = KANTE;
139 haus[i][knoten] = KANTE;
140 }
141
142 /**
143 * Markiert die Kante von i bis j in beiden Richtungen
144 * als bereits abgelaufen.
145 */
146 private void kanteZeichnen(int i, int j) {
147 haus[j][i] = KANTE_GEZEICHNET;
148 haus[i][j] = KANTE_GEZEICHNET;
149 }
150
151 /**
152 * Gibt true zurück, wenn die Kante von knoten bis i
153 * ablaufbar ist.
154 */
155 private boolean kanteIstUnbesucht(int knoten, int i) {
156 return haus[knoten][i] == KANTE && haus[i][knoten] == KANTE;
157 }
158
159 /**
160 * Gibt die Lösung als Folge der abgelaufenen Knoten aus.
161 */
162 private void print() {
163 for (int i = 0; i < loesung.length; i++) {
164 System.out.print(loesung[i] + "\t");
165 }
166 System.out.println();
167 }
168
169 /**
170 * Sucht jeweils für jeden Knoten 0 bis 4 eine Lösung und gibt sie aus
171 * (falls eine existiert).
172 */
173 public static void main(String argv[]) {
174 HausVomNikolaus hausVomNikolaus = new HausVomNikolaus();
175
176 for (int i = 0; i < hausVomNikolaus.anzahlKnoten; i++) {
177 hausVomNikolaus = new HausVomNikolaus();
178 System.out.println("Suche Lösung ab Knoten " + i);
179 if (hausVomNikolaus.sucheLoesung(i, 0)) {
180 System.out.print(" Lösung: ");
181 hausVomNikolaus.print();
182 } else {
183 System.out.println(" Keine Lösung gefunden");
184 }
185 }
186 }
187 }