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)

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")