Python :: Aufgabe #354

2 Lösungen Lösungen öffentlich

Suche nach kreuzenden Linien beim Rundreiseproblem

Fortgeschrittener - Python von hollst - 29.04.2021 um 19:12 Uhr
Beim Rundreiseproblem (auch Traveling Salesman Problem (TSP) genannt) muss ein Rundreisender nacheinander N Orte besuchen ohne einen einzigen zweimal anzufahren. Die letzte Reiselinie soll ihn genau an seinen Start(Heimat)ort zurückführen. Gesucht ist der insgesamt kürzeste Reiseweg für die Runde.

In Bild 1 sind die zu besuchenden Orte schematisch durch blauer Kreise gekennzeichnet und die Reisestrecke durch einen roten Geradenzug. Es wird angenommen, dass es unabhängig von der Lage (den Koordinaten) der (hier 12) blauen Kreise keine Wegekreuzungen beim kürzesten Reiseweg geben kann. Ob das auch bereits mathematisch bewiesen oder nur eine Vermutung ist, entzieht sich meiner Kenntnis [ich wäre für einen entsprechenden Hinweis von einem mathematischen Fachmann sehr dankbar].

Wir wollen diese Annahme durch ein Simulationsprogramm zu widerlegen versuchen, d. h. Ortslagekonstellationen suchen, bei denen der kürzeste Reiseweg mindstens zwei Teilstrecken einhält, die sich kreuzen.

Da es bei N unterschiedlichen Orten insgesamt 0.5 * (N - 1)! verschiedene Rundreisewege der besagten Art gibt, ist man mit N >> 10 sehr schnell am Ende seiner Rechenkunst (selbst mit Hochleistungsrechnern). Es soll für die Simulation daher N maximal 12 sein, aber mindestens 4. Bei N = 4 kann man einfach zeigen, dass eine Rundreise mit Wegekreuzung immer länger ist als der einzige Weg ohne Kreuzung. Aber, gilt das auch für N > 4?

Die Kreuzungsfreiheit kann unter Nutzung der Lösung von Aufgabe Nr. 390 (bei c#) (Schnittpunkt zweier Geraden endlicher Länge) nachgewiesen werden. Insgesamt sollen etwa 1.000 zufällige Ortslagekonstellationen der N Orte erzeugt und hinsichtlich ev. vorhandener Kreuzungen untersucht werden.

Viel Spaß!

Lösungen:

vote_ok
von eisheiliger (3750 Punkte) - 26.05.2021 um 14:17 Uhr
Quellcode ausblenden Python-Code

"""
#354: Suche nach kreuzenden Linien beim Rundreiseproblem
Beim Rundreiseproblem (auch Traveling Salesman Problem (TSP) genannt) muss ein Rundreisender nacheinander N Orte
besuchen ohne einen einzigen zweimal anzufahren. Die letzte Reiselinie soll ihn genau an seinen Start(Heimat)ort
zurückführen. Gesucht ist der insgesamt kürzeste Reiseweg für die Runde. Wir wollen diese Annahme durch ein
Simulationsprogramm zu widerlegen versuchen, d. h. Ortslagekonstellationen suchen, bei denen der kürzeste Reiseweg
mindstens zwei Teilstrecken einhält, die sich kreuzen. Insgesamt sollen etwa 1.000 zufällige Ortslagekonstellationen
der N Orte erzeugt und hinsichtlich ev. vorhandener Kreuzungen untersucht werden. Es soll für die Simulation daher N
maximal 12 sein, aber mindestens 4.
"""
from sympy.utilities.iterables import multiset_permutations
import numpy as np
import random
from scipy.spatial import distance
from operator import itemgetter


def prf_schnittp(px1, py1, px2, py2, qx1, qy1, qx2, qy2):
    zwi1 = (qy2 - qy1) * (px2 - px1) - (qx2 - qx1) * (py2 - py1)
    if zwi1:
        zwia = ((qx2 - qx1) * (py1 - qy1) - (qy2 - qy1) * (px1 - qx1)) / zwi1
        zwib = ((px2 - px1) * (py1 - qy1) - (py2 - py1) * (px1 - qx1)) / zwi1
    else:
        return 0
    if not (0 <= zwia <= 1 and 0 <= zwib <= 1):
        return 0
    x = px1 + zwia * (px2 - px1)
    y = py1 + zwia * (py2 - py1)
    print("Schnittpunkt          :", x, y)
    return 1


def cross(tour, wp):
    t1, t2, t3 = [], [], []
    h1 = 2
    zae = 0
    for i in range(0, len(tour) - 2):
        t1.append([tour[i], tour[i + 1]])
    for i in range(0, len(t1) - 2):
        for j in range(h1, len(t1)):
            t2.append([t1[i], t1[j]])
        h1 += 1
    for i in range(0, len(t2)):
        t3.append([wp[t2[i][0][0]], wp[t2[i][0][1]], wp[t2[i][1][0]], wp[t2[i][1][1]]])

    for i in range(0, len(t3)):
        [[a, b], [c, d], [e, f], [g, h]] = t3[i]
        sp = prf_schnittp(a, b, c, d, e, f, g, h)
        if sp != 0:
            zae += sp
    return zae


def dist(ort, fol):
    erg = []
    for i in range(len(fol)):
        zwi = fol[i]
        dst = 0
        for j in range(0, len(zwi) - 1):
            dst += distance.euclidean(ort[zwi[j]], ort[zwi[j + 1]])
        erg.append([dst] + fol[i])
    return sorted(erg, key=itemgetter(0))


def reisefolge(n):
    o = np.arange(1, n + 1, 1)
    p = list(multiset_permutations(o))
    q = []
    for i in p:
        q.append([0] + i + [0])
    return q


def reiseorte(n):
    orte = []
    while n >= 0:
        neu = [random.randint(0, 50, )] + [random.randint(0, 50, )]
        if neu not in orte:
            orte.append(neu)
            n -= 1
    return orte


def reisestart(wdhlg, anz):
    folg = reisefolge(anz)
    print("Simulation von", anz, "Orten bei", len(folg), "Reisevarianten mit", wdhlg, "Durchläufen:",  "\n")
    while wdhlg > 0:
        orte = reiseorte(anz)
        erg1 = dist(orte, folg)
        mini = erg1[0]
        wdhlg -= 1
        print("Wegpunkte, p0 - pn:", orte)
        print("Kürzeste Strecke,", "Folge:", mini[1:], "Distanz:", erg1[0][0],
              cross(mini[1:], orte), "Schnittpunkte", "\n")


wdh = 1000
poi = 7
reisestart(wdh, poi)


vote_ok
von satn1241 (3090 Punkte) - 13.07.2021 um 00:04 Uhr
Quellcode ausblenden Python-Code
import numpy as np


# Zufällig werden verschiedene Punkte erzeugt
# Die Grenzen können auch verändert werden
# Der erste Punkt ist der Startpunkt
def punkte_kreieren(n):
    import random
    punkte = []
    for i in range(0, n):
        punkte.append([random.randint(-10, 10), random.randint(-10, 10)])
    return punkte


# Test, ob ob Punkt doppelt erzeugt wurde
def test_auf_doppelte_punkte(liste):
    bereinige_liste = []
    for element in liste:
        if element not in bereinige_liste:
            bereinige_liste.append(element)
        elif element in bereinige_liste:
            # print("min. 1 doppelter Punkt")
            return False
    return bereinige_liste


# Matrix über die Abstände zwischen allen Punkten erstellen
def alle_abstaende(punkte):
    from math import dist
    import numpy as np
    alle_distanzen = []
    for i in punkte:
        distanzen = []
        for a in range(0, len(punkte)):
            distanzen.append(dist(i, punkte[a]))
        alle_distanzen.append(distanzen)
    return np.array(alle_distanzen)


# Permutationen zwischen dem Start- und Endpunkt
def permutationen_erzeugen(n):
    import itertools
    liste = list(range(1, n))
    permutationen = list(itertools.permutations(liste))
    return permutationen


# Bereinigt die Permutationen um Dopplungen --> Hin- und Rückweg ist gleich
def permutationen_bereinigen(perm):
    bereinige_liste = []
    for element in perm:
        reversed_element = element[::-1]
        if reversed_element not in bereinige_liste:
            bereinige_liste.append(element)
    return bereinige_liste


# Berechne die Länge aller möglichen Pfade
def pfadlaengen():
    pfadlaengen_liste = []
    for element in strecken:
        distanz = 0
        for i in range(0, n - 2):
            distanz += (distanzen_matrix[element[i], element[i + 1]])
        distanz += distanzen_matrix[0, element[0]] + distanzen_matrix[element[n - 2], 0]
        pfadlaengen_liste.append(distanz)
    return pfadlaengen_liste


# Wählt den kürzesten Pfad aus
def kuerzester_pfad():
    position = np.where(np.array(pfadlaengen()) == min(pfadlaengen()))[0]
    for element in position:
        kuerzeste_pfade = []
        kuerzeste_pfade.append([0] + list(strecken[element]) + [0])
    return kuerzeste_pfade


def plotten():
    import matplotlib.pyplot as plt
    x = []
    y = []
    for element in plot_punkte:
        x.append(element[0])
        y.append(element[1])
    plt.scatter(x, y)
    plt.plot(x, y)
    plt.xlabel("X")
    plt.ylabel("Y")
    plt.title("Route")
    plt.annotate("Start / Ende", (x[0], y[0]))
    plt.show()
    return None


def check_seiten(seite1, seite2):
    import numpy as np
    P0 = seite1[0]
    P1 = seite1[1]
    P2 = seite2[0]
    P3 = seite2[1]
    A = np.array([[P1[0] - P0[0], P2[0] - P3[0]], [P1[1] - P0[1], P2[1] - P3[1]]])
    b = np.array([P2[0] - P0[0], P2[1] - P0[1]])
    try:
        z = np.linalg.solve(A, b)
    except np.linalg.LinAlgError:
        return True
    if 0 < round(z[0], 6) < 1 and 0 < round(z[1], 6) < 1:
        return False
    else:
        return True


# Prüfung, ob es zwischen den einzelnen Seite Schnittpunkt neben dem Anfang und Endpunkt gibt
def gibt_es_schnttpunkte():
    seiten = []
    for i in range(0, len(plot_punkte) - 1):
        seiten.append([plot_punkte[i], plot_punkte[i + 1]])
    schnittpunkt_check = []
    for j in range(0, len(seiten)):
        for k in range(j + 1, len(seiten)):
            schnittpunkt_check.append(check_seiten(seiten[j], seiten[k]))
    for i in schnittpunkt_check:
        if not i:
            return False
    else:
        return True


# Ausführung des Algoritmus
# Anzahl der Punkte
n = 6
ausfuehrungen = 1000
for i in range(0, ausfuehrungen):
    liste = (permutationen_erzeugen(n))
    punkte = test_auf_doppelte_punkte(liste)
    distanzen_matrix = alle_abstaende(punkte)
    strecken = (permutationen_bereinigen(permutationen_erzeugen(n)))

    plot_punkte = []
    for elm in kuerzester_pfad():
        for e in elm:
            plot_punkte.append(punkte[e])

    # Die folgenden Rauten können ggf. entfernt werden
    # print("kürzeste Route")
    # print(plot_punkte) #kürzeste Route
    # print("Die Länge der Strecke ist:",min(pfadlaengen())) # Länge der Strecke
    # plotten() # Plotten des Weges
    if gibt_es_schnttpunkte() == False:
        print("Fehler")
        plotten()
        break
else:
    print("Keine Schnittpunke --> immer ein Kreis")
1800908

Du scheinst einen AdBlocker zu nutzen. Ich würde mich freuen, wenn du ihn auf dieser Seite deaktivierst und dich davon überzeugst, dass die Werbung hier nicht störend ist.