Kuerzester Rundweg in Schachbrettgitter

27/02/2009 - 14:37 von Thomas Nordhaus | Report spam
Hallo!
Ich habe mal den sog. Metropolis-Algorithmus (siehe z.B. "Numerical
Recipies") für das Handlungsreisendenproblem in gnu-Octave
nachprogrammiert. Als Testfàlle suchte ich die kürzesten Rundwege in
einem 7x7 und 8x8 Schachbrettgitter.

Im Fall 8x8 kann man sich leicht einen Rundweg zusammenstellen, der aus
genau 64 Einheitsschritten besteht (allgemein für 2nx2n Gitter mit 4n^2
Einheitsschritten). "Mein" Algorithmus fand auch einen solchen Rundweg.
Siehe:

http://www.bilder-hochladen.net/files/2dly-d.png

Für ein 7x7 Gitter fand er allerdings "nur" einen Pfad bestehend aus 48
Einheitsschritten und 1 "Diagonalschritt". Siehe:

http://www.bilder-hochladen.net/files/2dly-e.jpg

Gibt's auch noch einen kürzeren Rundweg? Also mit 49 Einheitsschritten?
Ich vermute mal nein, allgemein für ungeradzahlige Gitter.. Gibts da
einen einfachen Beweis bzw. plausibles Argument?

Thomas Nordhaus
 

Lesen sie die antworten

#1 gwoegi
27/02/2009 - 14:42 | Warnen spam
Thomas Nordhaus wrote:
# Hallo!
# Ich habe mal den sog. Metropolis-Algorithmus (siehe z.B. "Numerical
# Recipies") f??r das Handlungsreisendenproblem in gnu-Octave
# nachprogrammiert. Als Testf??lle suchte ich die k??rzesten Rundwege in
# einem 7x7 und 8x8 Schachbrettgitter.
#
# Im Fall 8x8 kann man sich leicht einen Rundweg zusammenstellen, der aus
# genau 64 Einheitsschritten besteht (allgemein f??r 2nx2n Gitter mit 4n^2
# Einheitsschritten). "Mein" Algorithmus fand auch einen solchen Rundweg.
# Siehe:
#
# http://www.bilder-hochladen.net/files/2dly-d.png
#
# F??r ein 7x7 Gitter fand er allerdings "nur" einen Pfad bestehend aus 48
# Einheitsschritten und 1 "Diagonalschritt". Siehe:
#
# http://www.bilder-hochladen.net/files/2dly-e.jpg
#
# Gibt's auch noch einen k??rzeren Rundweg? Also mit 49 Einheitsschritten?
# Ich vermute mal nein, allgemein f??r ungeradzahlige Gitter.. Gibts da
# einen einfachen Beweis bzw. plausibles Argument?

Ja, ein Paritaetsargument.
Ein Einheitsschritt bringt Dich immer von einem Punkt mit
gerader (ungerader) Koordinatensumme zu einem Punkt mit
ungerader (gerader) Koordinatensumme. Etc.


___________________________________________________________
Gerhard J. Woeginger http://www.win.tue.nl/~gwoegi/

Ähnliche fragen