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)