Lösungsbeschreibung des Preisrätsels vom Mai 2018

Reisende, von Flughafen zu Flughafen

1.) das Problem

Bei $n=25$ willkürlich verteilten Punkten, die auf dem kürzesten Rundweg miteinander verbunden werden sollen, gibt es $$\sand{\begin{align} u&=\sum_{i=1}^{n-1}i=\frac{n^2-n}{2}=300\; \text{meist unterschiedlich lange Streckenabschnitte}\quad\quad\quad\tag{1} \\ v&=\frac12\cdot\prod_{i=1}^{n-1}i=310224200866619719680000\; \text{verschiedene Punktreihenfolgen}\quad\quad\quad\tag{2} \end{align}}$$ Es ist also mit heutigen Mitteln fast unmöglich, alle Reihenfolgen durchzurechnen. Deshalb ist das mathematisch Problem seit 1930 als "Traveling Salesman Problem" (Problem des Handlungsreisenden) bekannt und es gibt unterschiedliche Vorgehensweisen, um näherungsweise oder genau zu einem Ergebnis zu gelangen, ohne alle Möglichkeiten zu durchlaufen.

2.) die einzelnen Strecken

Da die geographischen Koordinaten angegeben sind ist die Berechnung einer Strecke von $P_A$ nach $P_B$ die Orthodrome, welche hier zunächst als Winkel im Bogenmaß angegeben wird. Für die gesuchten Strecken muss noch mit dem Erdradius $r=6370\;km$ multipliziert werden. $$ \text{Orthodrome}\;\zeta_{A,B} =\arccos \left(\sin(\phi _{A})\cdot \sin(\phi _{B})+\cos(\phi _{A})\cdot \cos(\phi _{B})\cdot \cos(\lambda _{B}-\lambda _{A})\right) $$ Hier die Liste aller Strecken auf ganze Kilometer gerundet:

in km	FRA	TXL	HAM	MUC	STR	SXF	BRE	DRS	DUS	ERF	HAJ	CGN	LEJ	FMO	NUE	SCN	NRN	FMM	DTM	HHN	FKB	PAD	FDH	RLG	BWE
FRA	0	432	412	300	157	431	335	387	188	199	281	136	301	241	190	139	243	258	178	94	144	175	272	501	289
TXL	432	0	250	481	517	26	307	162	469	238	245	463	144	383	374	571	499	552	405	510	558	336	606	165	187
HAM	412	250	0	601	552	274	103	378	340	302	131	363	288	227	466	530	344	628	285	451	556	243	664	153	151
MUC	300	481	601	0	192	465	564	342	486	299	482	436	345	512	138	355	542	121	462	374	276	428	184	621	451
STR	157	517	552	192	0	509	485	424	338	283	421	284	373	398	162	165	391	108	335	199	85	328	115	619	414
SXF	431	26	274	465	509	0	326	139	478	234	260	470	136	397	362	570	511	540	415	512	553	345	595	190	200
BRE	335	307	103	564	485	326	0	401	239	273	88	267	296	126	425	442	241	572	188	361	477	160	600	250	144
DRS	387	162	378	342	424	139	401	0	487	197	318	464	111	434	264	519	532	432	429	478	483	361	493	326	257
DUS	188	469	340	486	338	478	239	487	0	294	239	54	380	113	364	232	56	444	64	153	294	133	448	473	285
ERF	199	238	302	299	283	234	273	197	294	0	187	267	103	260	165	337	342	337	240	286	320	177	382	339	151
HAJ	281	245	131	482	421	260	88	318	239	187	0	249	210	140	344	404	260	500	176	327	425	119	533	237	62
CGN	136	463	363	436	284	470	267	464	54	267	249	0	361	146	318	184	108	390	79	103	242	132	394	486	286
LEJ	301	144	288	345	373	136	296	111	380	103	210	361	0	323	230	440	422	409	320	388	418	252	462	276	152
FMO	241	383	227	512	398	397	126	434	113	260	140	146	323	0	378	327	121	496	69	245	374	86	513	366	197
NUE	190	374	466	138	162	362	425	264	364	165	344	318	230	378	0	289	420	179	332	279	232	292	233	498	316
SCN	139	571	530	355	165	570	442	519	232	337	404	184	440	327	289	0	274	267	259	82	86	287	247	633	422
NRN	243	499	344	542	391	511	241	532	56	342	260	108	422	121	420	274	0	498	102	200	343	171	500	486	313
FMM	258	552	628	121	108	540	572	432	444	337	500	390	409	496	179	267	498	0	435	307	182	420	65	675	482
DTM	178	405	285	462	335	415	188	429	64	240	176	79	320	69	332	259	102	435	0	177	306	70	449	412	221
HHN	94	510	451	374	199	512	361	478	153	286	327	103	388	245	279	82	200	307	177	0	143	208	302	560	350
FKB	144	558	556	276	85	553	477	483	294	320	425	242	418	374	232	86	343	182	306	143	0	318	162	641	431
PAD	175	336	243	428	328	345	160	361	133	177	119	132	252	86	292	287	171	420	70	208	318	0	443	355	154
FDH	272	606	664	184	115	595	600	493	448	382	533	394	462	513	233	247	500	65	449	302	162	443	0	721	522
RLG	501	165	153	621	619	190	250	326	473	339	237	486	276	366	498	633	486	675	412	560	641	355	721	0	212
BWE	289	187	151	451	414	200	144	257	285	151	62	286	152	197	316	422	313	482	221	350	431	154	522	212	0

3.) die 25 kürzesten und längsten Strecken

Um eine Vorstellung von der Länge des kürzesten und längsten Rundwegs zu bekommen, kann man die 25 kürzesten und längsten Strecken auflisten und jeweils deren Summe bilden. Diese Strecken bilden aber leider nicht die gesuchten Rundwege.
Links unten sind diese kürzesten Strecken gelistet und in die obere Karte eingetragen. Darunter ist das Bild für die längsten Strecken und rechts daneben die Auflistung.

die kürzesten Strecken Nr. von nach Strecke 1 TXL SXF 25,52 2 DUS CGN 53,72 3 DUS NRN 55,82 4 HAJ BWE 62,13 5 DUS DTM 63,95 6 FMM FDH 64,60 7 FMO DTM 68,57 8 DTM PAD 70,03 9 CGN DTM 79,46 10 SCN HHN 82,06 11 STR FKB 84,55 12 SCN FKB 85,68 13 FMO PAD 86,22 14 BRE HAJ 87,78 15 FRA HHN 93,87 16 NRN DTM 102,16 17 ERF LEJ 102,54 18 CGN HHN 102,72 19 HAM BRE 103,11 20 CGN NRN 107,63 21 STR FMM 108,11 22 DRS LEJ 111,16 23 DUS FMO 113,25 24 STR FDH 115,19 25 HAJ PAD 119,32 Summe: 2149,14		die längsten Strecken Nr. von nach Strecke 1 FDH RLG 721,04 2 FMM RLG 674,53 3 HAM FDH 663,62 4 FKB RLG 641,20 5 SCN RLG 632,94 6 HAM FMM 627,80 7 MUC RLG 620,94 8 STR RLG 618,66 9 TXL FDH 606,23 10 HAM MUC 601,32 11 BRE FDH 599,76 12 SXF FDH 595,19 13 BRE FMM 571,58 14 TXL SCN 570,63 15 SXF SCN 569,97 16 MUC BRE 563,70 17 HHN RLG 559,50 18 TXL FKB 557,68 19 HAM FKB 555,81 20 SXF FKB 553,21 21 TXL FMM 552,38 22 HAM STR 552,14 23 MUC NRN 541,81 24 SXF FMM 539,97 25 HAJ FDH 533,24 Summe: 14824,85

Auch wenn das noch nicht die Lösung des Rätsels ist, kann es doch helfen, Bedingungen zu bilden, die zum Abbruch unnötiger Versuche beim Durchtesten aller Möglichkeiten benutzt werden können und damit die Rechenzeit zu verkürzen.
Erkennbar wird auch die Struktur der Rundwege. Beim kürzesten Weg ist ein ringförmiges Bild zu erwarten, beim längsten Weg ist es eher sternförmig.
Das schematische Bild links mit 7 Punkten und das Bild rechts mit 25 Punkten zeigt diesen Effekt bei dem kürzesten (rot) und längsten (blau) echten Rundweg.

4.) Suche nach den kürzesten und längsten Rundwegen

Das menschliche Auge ist in der Lage, den kürzesten Rundweg gut abzuschätzen. Das gelingt beim längsten Rundweg weitaus schlechter. Trotzdem gilt für beide Lösungsansätze die gleiche Vorgehensweise: Es sind mehrere Variable einzustellen:

• die Startsequenz der Kette, von der es oft abhängt, ob das absolute Minimum/Maximum erreicht wird oder nur ein lokales
• die Länge des vom Rechner zu optimierenden Anteils, der darüber entscheidet, wie schnell das Programm arbeitet
• die Anzahl der Elemente, die von hinten nach vorne verschoben werden

Die Startsequenz ist für den kürzesten Rundweg leicht abzuschätzen. Aber auch eine zufällige Abfolge kommt oft zum gleich guten Ergebnis. Es sollten aber in jedem Fall mehrere Möglichkeiten erprobt werden.
Die Erfahrung zeigte, dass mit 18 vorgegebenen Strecken der Rechner die letzten 7 Strecken = 5040 Kombinationen in ein paar Millisekunden berechnen kann. Dabei wird im Einzelnen auch deutlich weniger Rechenaufwand nötig sein, weil sich abzeichnet, dass eine bessere Lösung nicht möglich ist, also schon beispielsweise nach der Festlegung der ersten von sieben Strecken das bisherige Minimum/Maximum verpasst wird. Bei solch kurzen Rechenzeiten macht es gar nichts, dass dieser geringe Aufwand sehr oft wiederholt werden muss, um den Ring mehrfach zu durchlaufen.
Die Anzahl der zu verschiebenden Elemente ist kein kritische Punkt, weder in Rechenzeit noch in Zielsicherheit. Der Wert sollte aber die Hälfte der vom Rechner ermittelten Streckenabschnitte nicht überschreiten.

Hier folgt das Ergebnis der Berechnung des kürzesten Rundwegs: Eine offensichtliche Abfolge beginnend bei Hamburg (Nr.2) führt rechts herum über Rostock/Lage (Nr.23) weiter nach Berlin. Die folgenden offensichtlich richtigen Zahlen der Startabfolge entsprechen den Punkt-Nummern der Flughäfen, die auf der Karte abzulesen sind, wenn der Mauszeiger über einem Punkt steht. $$ 2, 23, 1, 5, 7, 12, 9, 14, 3, 17, 22, 4, 20, 15, 19, 0, 11, 8 $$ Diese wird vorgegeben und vom Rechner mit dem besten Ergebnis aller möglichen Folgekombinationen ergänzt. Dann schiebt man noch den Ring weiter, bis als Start die Nr. 0, also Frankfurt am Anfang steht. Das Ergebnis ist $$\rand{\begin{align} 0,11,8,16,18,13,21,24,10,6,2,23,1,5,7,12,9,14,3,17,22,4,20,15,19 \\ \text{kürzester Rundweg}=s_{min}=2557,337112\;km \end{align}}$$ Die Rechenzeit dafür einschließlich Test bei allen verschobenen Stellungen des Rings lag bei etwa 0,3 Sekunden.

5.) Suche nach dem längsten Rundweg

Wie man aus den beiden obigen schematischen Bildern lernen kann, ist es mit guter Näherung möglich, aus dem kürzesten Rundweg den längsten zu konstruieren. Dazu fügt man zwischen die Punkte des kürzesten Rundwegs jeweils einen Punkt aus der zweiten Hälfte ein.
Beginnend mit $$00, xx, 11, xx, 08, xx, 16, xx, 18, xx, 13, xx, 21, xx, 24, xx, 10, xx$$ wird eingefügt $$xx, 05, xx, 07, xx, 12, xx, 09, xx, 14, xx, 03, xx, 17, xx, 22, xx, 04$$ ergibt als Startabfolge $$00, 05, 11, 07, 08, 12, 16, 09, 18, 14, 13, 03, 21, 17, 24, 22, 10, 04$$ die der Rechner wieder mit den verbleibenden 7 Punkte in allen Variationen durchtestet und ergänzt. Auch hier wird der Ring der Punkte verschoben und weiter optimiert. dabei wird z.B. 7 mit 12 getauscht und zwischen 0 und 5 noch die vom Rechner ergänzte Folge 23,15,1,19 eingefügt. Im Ergebnis bildet sich die Folge mit dem längsten Rundweg: $$\rand{\begin{align} 0, 23, 15, 1, 19, 5, 11, 12, 8, 7, 16, 9, 18, 14, 13, 3, 21, 17, 6, 22, 10, 4, 2, 20, 24 \\ \text{längster Rundweg}=s_{max}=11561,009483\;km \end{align}}$$ Auch hierfür betrug die Rechenzeit einschließlich Tests bei allen verschobenen Stellungen des Rings etwa 0,3 Sekunden.

6.) verschiedene Strecken fast gleicher Länge

Zwischen dem kürzesten und längsten Rundweg liegen all die anderen Rundwege und das sind nach (2): $$ v=310224200866619719680000 $$ Wenn man annimmt, dass die Abstände der Längen von allen diesen Rundwegen maximal werden, also eine Gleichverteilung auf einer Strecke von $$ s=s_{max}-s_{min}=9003,67\;km $$ dann wird dieser Abstand $$\rand{ (s_{max}-s_{min})/v=0.000000000000000000029\;km=29\;am }\tag{3}$$ Ist diese angenommene Gleichverteilung nicht der Fall, wovon man sicher ausgehen kann, dann würden sich noch kleinere Abstände zwischen einzelnen Rundwegen ergeben, weil an anderer Stelle sich Abstände vergrößert hätten. Daher ist das Ergebnis von Gleichung (3) nur eine obere Grenze und damit die Lösung der dritten Rätselfrage.

Diese Informationen wurden zusammengestellt von