Hausdorffdistanz

[zwiety]

Hallo

ich hab eine Frage, da ich versuche die Hausdorffdistanz einer oberen und einer unteren Approximation, die zusammen ein Dreieick ergeben zu berechnen. Mein Problem ist, dass ich nicht weis ob das was ich mache richtig ist. Hier ist der Code wie ich es versucht habe

Code: Alles auswählen

def drange(start, stop, step):
     r = start
     while r < stop:
         yield r
         r += step

def U(x12,y12,x21,y21):
    N1=drange(0,1,0.001)
    U={(f1(x12,y12)+lambd*(f1(x21,y21)-f1(x12,y12)),f2(x12,y12)+lambd*(f2(x21,y21)-f2(x12,y12)))  for lambd in N1}
    return U

def L(x12,y12,x21,y21):
    N1=drange(0,1,0.001)
    L1={(f1(x12,y12),f2(x12,y12)+lambd*(f2(x21,y21)-f2(x12,y12)))  for lambd in N1}
    L2={(f1(x12,y12)+lambd*(f1(x21,y21)-f1(x12,y12)),f2(x21,y21))  for lambd in N1}
    L=L1|L2
    return L

U1=U(x12,y12,x21,y21)
L1=L(x12,y12,x21,y21)

def l1min(L,U):
    N1=drange(0,1,0.001)
    l1min=min(f1(x12,y12)+lambd*(f1(x21,y21)-f1(x12,y12)) for lambd in N1)
    return l1min

def l2max(L,U):
    N1=drange(0,1,0.001)
    l2max=max(f2(x12,y12)+lambd*(f2(x21,y21)-f2(x12,y12)) for lambd in N1)
    return l2max


def l2min(L,U):
    N1=drange(0,1,0.001)
    l2min=min(f2(x12,y12)+lambd*(f2(x21,y21)-f2(x12,y12)) for lambd in N1)
    return l2min


def l1max(L,U):
    N1=drange(0,1,0.001)
    l1max=max(f1(x12,y12)+lambd*(f1(x21,y21)-f1(x12,y12)) for lambd in N1)
    return l1max

l1min=l1min(L,U)
l2min=l2min(L,U)
l1max=l1max(L,U)
l2max=l2max(L,U)



def dist(x1,y1,x2,y2):
    dist=math.sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2))
    return dist
    

def Dist1(l1min,l2min,U1):
    Dist=max(min(dist(l1min,l2min,u1,u2) for (u1,u2) in U1))
    return Dist

def dH(L,U):
     D1=Dist1(l1min,l2max,U1)
     D2=Dist1(l1min.l2min,U1)
     D3=Dist1(l1max,l2min,U1)
     D4=Dist1(l1min.l2max,L1)
     D5=Dist1(l1max,l2min,L1)
     dH=max(D1,D2,D3,D4,D5)
     return dH

leider hab ich zum einen das Problem, dass ich z.B. U als konvexkomination zweier Punkte darstellen soll und ich durch die Definition von U nur eine ungefähre Menge definiert habe und zum anderen weis ich nicht ob ich die Hausdorffdistanz so richtig angefangen habe zu programmieren. Wäre nett wenn mir jemand helfen könnte.

LG

[BlackJack]

@zwiety: Ganz grundsätzlich zum Vorgehen: Schreib nicht so eine Masse an Quelltext runter ohne den getestet zu haben. Implementiere eine Funktion nach der anderen und probiere die aus, ob die tun was sie sollen. Und erst wenn der Code bis dahin lauffähig ist, implementiere die nächste Funktion. Dabei ergibt sich dann relativ natürlich, dass Du zuerst die Funktionen implementierst, die von anderen verwendet werden. Der Quelltext ist so wie er da steht voller Fehler die verhindern, dass man das ablaufen lassen kann.

Zur Form: Es sind manche Zeilen um 5 oder 9 Leerzeichen eingerückt. Wie bekommt man das denn hin‽ Du machst die Einrückung hoffentlich nicht in dem Du mehrmals die Leertaste drückst‽ Falls doch, solltest Du Dich mit den Einstellungen Deines Editors vertraut machen, und wie man den dazu bringt mittels Tabulator-Taste um vier Spalten mittels Leerzeichen einzurücken. Das kann jeder Editor der zum Programmieren taugt.

Es gibt einige Zeilen, die länger als 80 Zeichen sind, und Du verwendest zu wenig Leerzeichen, damit das nicht alles so unlesbar aneinander klebt. Mit mehr Leerzeichen würden noch mehr Zeilen länger als 80 Zeichen werden und sollten umgebrochen werden. Dabei sollte man möglichst ausnutzen, dass für den Python-Compiler eine ”logische” Zeile nicht zu Ende ist, solange noch offene Klammern jedweder Art auf ein schliessendes Gegenstück warten.

Allgemein zur Form gibt es den PEP 8 -- Style Guide for Python Code.

`drange()` ist problematisch implementiert, da Operationen mit Gleitkommazahlen ungenau sein können. Und wenn Du immer wieder eine ungenaue Operation auf ein bereits ungenaues Zwischenergebnis anwendest, akkumulieren sich diese Abweichungen und die Ergebnisse werden immer ungenauer. Ausserdem variiert je nach konkreten Werten die Anzahl der Ergebnisse. Während (0, 1, 0.1) zum Beispiel 11 Ergebnisse liefert, bekommst Du bei (0, 1, 0.001) genau 1000 Ergebnisse:

Code: Alles auswählen

In [105]: list(drange(0, 1, 0.1))
Out[105]: 
[0,
 0.10000000000000001,
 0.20000000000000001,
 0.30000000000000004,
 0.40000000000000002,
 0.5,
 0.59999999999999998,
 0.69999999999999996,
 0.79999999999999993,
 0.89999999999999991,
 0.99999999999999989]

In [106]: len(_105)
Out[106]: 11

In [107]: len(list(drange(0, 1, 0.001)))
Out[107]: 1000

In [108]: list(drange(0, 1, 0.001))[-1]
Out[108]: 0.99900000000000078

In `U` fangen dann die Probleme an, die mich vermuten lassen, dass Du davon bisher nichts ausprobiert hast. Denn die dort verwendeten Funktionen `f1` und `f2` werden nirgends definiert. Das gleiche bei `L`. Und bei den Aufrufen von `U` und `L` bestehen die Argumente aus lauter nicht definierten Namen. In `l1min` und `l2max` & Co werden plötzlich neben den undefinierten Funktionen `f1` und `f2` auch andere Werte (`x12`, `x21`, `y12`, `y21`) einfach so verwendet, die nicht als Argumente übergeben werden und auch sonst nirgends definiert sind‽ Dafür werden die Argumente `L` und `U` in den Funktionen gar nicht verwendet‽

Ein ``import math`` fehlt.

Übliche Konvention mit Namen umzugehen, die in Python Schlüsselwörter sind, ist übrigens einen Unterstrich anzuhängen. Also `lambda_` statt `lambd`.

Man sollte auch nicht den Namen der Funktion innerhalb der Funktion an einen anderen Wert binden. Das ist verwirrend. Und so wie Du das regelmässig machst muss ich wohl mal sagen Python ist nicht Pascal. Es ist sowieso unnötig den Rückgabewert an einen Namen zu binden, wenn das einzig direkt vor dem ``return`` geschieht, wo allein dieser Name als Ausdruck steht. Die Zeile kann man sich dann auch sparen — das ist kein Mehrgewinn für den Leser.

Bei den ganzen `*min`- und `*max`-Funktionen fällt auf, dass der Funktionskörper fast identisch ist. Da könnte man eine etwas allgemeinere Funktion schreiben, welche die Unterschiede als Argumente entgegen nimmt, und die konkreten Varianten dann mit `functools.partial()` erstellen.

Bei `dist()` — was ich `distance()` nennen würde — könnte man den Potenzoperator verwenden, statt die Terme wirklich zweimal hin zu schreiben.

`Dist1` ist ein schlechter Name. Was soll die 1 aussagen? Man sollte Namen vergeben, die dem Leser eine Idee vermitteln wofür der Wert im Programm semantisch steht. *Welche* Distanz wird von der Funktion berechnet? Die Kritik gilt auch für viele der anderen, insbesondere einbuchstabigen Namen. Bei mathematischen Berechnungen sind die an vielen Stellen üblich, so dass die Faustregel längere, aussagekräftigere Namen zu verwenden bei diesem Themengebiet etwas lockerer gesehen werden kann, aber die meisten können sich unter Funktionen die `U` oder `L` heissen, nicht wirklich vorstellen, was die machen sollen.

In `dH()` hast Du offenbar Punkt und Komma verwechselt. Die Argumente `L` und `U` werden auch hier nicht verwendet, dafür aber die globalen Werte `L1` und `U2`, deren zustande kommen weiter oben schon indirekt angesprochen wurde.

[zwiety]

Code: Alles auswählen

import math

m=int(raw_input("Anzahl der existierenden Standorte: "))
W=0
A1=0
B1=0
A2=0
B2=0
V=0


a1=[]
a2=[]
A=[]

for i in range(0,m):
    [ai,bi]=[input("1.Koordinate des Standortes: "), input("2.Koordinate des Standortes: ")]
    a1.insert(i,ai)
    a2.insert(i,bi)
    A.insert(i,(ai,bi))


print "Die Menge der existierenden Standorte ist gegeben durch A= ", A

GEW=[]
w1=[]
w2=[]

for i in range(0,m):
    [wi,vi]=[input("1.Koordinate des Gewichtes: "),input("2.Koordinate des Gewichtes: ")] 
    w1.insert(i,wi)
    w2.insert(i,vi)
    GEW.insert(i,(wi,vi))


tau=input("Wert der Genaugigkeit: ")
print "Die Menge der Gewichtsvektoren ist gegeben durch GEW=", GEW 

W=sum(w1)
V=sum(w2)

      
for i in range(0,m):
    A1=float(A1+a1[i]*w1[i])
    B1=float(B1+a2[i]*w1[i])
    A2=float(A2+a1[i]*w2[i])
    B2=float(B2+a2[i]*w2[i])
    x12=float(A1/W)
    y12=float(B1/W)
    x21=float(A2/V)
    y21=float(B2/V)


print "Die lex. optimalen Standorte sind: " ,(x12,y12), (x21,y21)


def f2(x,y):
        f2=0
        for i in range(m):
            f2=f2+w2[i] * (a1[i]-x)**2 + w2[i] * (a2[i] - y)**2
        return f2
def f1(x,y):
    f1=0
    for i in range(m):
        f1=f1+w1[i] * (a1[i]-x)**2 + w1[i] * (a2[i] - y)**2
    return f1

def f(x,y):
    f1(x,y)
    f2(x,y)
    f=(f1(x,y),f2(x,y))
    return f1(x,y),f2(x,y)


f(x12,y12)
f1(x12,y12)
f2(x12,y12)

Rep=[]
Rep.append(f(x12,y12))



f(x21,y21)
f1(x21,y21)
f2(x21,y21)

Rep.append(f(x21,y21))


yI=(f1(x12,y12),f2(x21,y21))


def drange(start, stop, step):
     r = start
     while r < stop:
         yield r
         r += step

def U(x12,y12,x21,y21):
    N1=drange(0,1,0.001)
    U={(f1(x12,y12)+lambd*(f1(x21,y21)-f1(x12,y12)),f2(x12,y12)+lambd*(f2(x21,y21)-f2(x12,y12)))  for lambd in N1}
    return U

def L(x12,y12,x21,y21):
    N1=drange(0,1,0.001)
    L1={(f1(x12,y12),f2(x12,y12)+lambd*(f2(x21,y21)-f2(x12,y12)))  for lambd in N1}
    L2={(f1(x12,y12)+lambd*(f1(x21,y21)-f1(x12,y12)),f2(x21,y21))  for lambd in N1}
    L=L1|L2
    return L

U1=U(x12,y12,x21,y21)
L1=L(x12,y12,x21,y21)

def l1min(L,U):
    N1=drange(0,1,0.001)
    l1min=min(f1(x12,y12)+lambd*(f1(x21,y21)-f1(x12,y12)) for lambd in N1)
    return l1min

def l2max(L,U):
    N1=drange(0,1,0.001)
    l2max=max(f2(x12,y12)+lambd*(f2(x21,y21)-f2(x12,y12)) for lambd in N1)
    return l2max


def l2min(L,U):
    N1=drange(0,1,0.001)
    l2min=min(f2(x12,y12)+lambd*(f2(x21,y21)-f2(x12,y12)) for lambd in N1)
    return l2min


def l1max(L,U):
    N1=drange(0,1,0.001)
    l1max=max(f1(x12,y12)+lambd*(f1(x21,y21)-f1(x12,y12)) for lambd in N1)
    return l1max

l1min=l1min(L,U)
l2min=l2min(L,U)
l1max=l1max(L,U)
l2max=l2max(L,U)



def dist(x1,y1,x2,y2):
    dist=math.sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2))
    return dist
    

def Dist1(l1min,l2min,U1):
    Dist=max(min(dist(l1min,l2min,u1,u2) for (u1,u2) in U1))
    return Dist

hier hab ich mal den ganzen code wo auch die definition von den funktionen mit drinnen ist.

[zwiety]

Also ich hab hier mal den kompletten Code geschrieben. Sorry das ich das nicht gleich gemacht habe. ich habe also keine Probleme bis zu dem Teil von L und U. Kann mir vielleicht jemand sagen, wie ich L und U anders Darstellen kann? L soll eine untere Approximation darstellen und U die zugehörige obere Approximation und davon möchte ich dann gerne die Hausdorffdistanz berechnen. Dies hab ich dann versuch indem ich die dist usw definiert habe aber das klappt so nicht, da es dann das falsche Ergebniss liefert.

[BlackJack]

@zwiety: Ui, da lässt sich an der Form noch mehr kritisieren. Der Code auf Modulebene sollte sich auf Definitionen von konstanten Werten, Funktionen, Klassen, und so weiter beschränken. Alles andere gehört in Funktionen.

Das über Namen gesagte möchte ich noch einmal unterstreichen: Namen sollten dem Leser vermitteln welche Bedeutung der daran gebundene Wert im Programm hat und nicht aus irgendwelchen kryptischen Abkürzungen oder gar nur willkürlichen Buchstaben oder Buchstaben/Ziffern-Kombinationen bestehen. Wenn `m` für die Anzahl der Standorte und `A` für deren Menge stehen, dann sollten die nicht `m` oder `A` heissen, sondern zum Beispiel `coordinates_count` und `coordinates`.

Wenn ich mir Deine Schleifen anschaue, solltest Du mal dringend das Tutorial in der Python-Dokumentation durcharbeiten. So geht man in Python nicht mit Listen um. Das `insert()` ist umständlich und wenn Du über die Elemente einer Liste iterieren möchtest, dann kannst Du das *direkt* tun. Eine Schleife der Form ``for i in range(len(obj)):``, wobei `m` in Deinem Fall ja immer der Länge entspricht, wo im Schleifenkörper `i` nur für den Indexzugriff verwendet wird, ist in Python ein „Anti-Pattern”.

Falls man zusätzlich zu den Elementen einen Index benötigt, gibt es die `enumerate()`-Funktion. Und wenn man über die Elemente von mehreren Listen ”parallel” iterieren möchte, verwendet man `itertools.izip()`.

`input()` sollte man in Python 2.x nicht verwenden, da dort beliebige vom Benutzer eingegebene Python-Ausdrücke ausgewertet werden. Damit kann der Benutzer das Programm absichtlich oder unabsichtlich sehr tief greifend beeinflussen. Ausserdem ist es fast aussichtslos vernünftige Fehlerbehandlung dafür zu implementieren, das bei beliebigen Ausdrücken auch nahezu beliebige Fehler und Ausnahmen auftreten können.

Auf der linken Seite einer Zuweisung eine Liste mit Namen zu schreiben ist sehr ungewöhnlich. Üblicherweise verwendet man dort ein Tupel von Namen und lässt, falls möglich die Klammern weg.

Es werden in den Listen für die Eingaben offensichtlich zusammengehörige Werte in verschiedenen Listen gespeichert, und das anscheinend auch noch redundant. Beides sollte man vermeiden. Man muss dann immer aufpassen, dass die Listen ”synchron” bleiben und beim Lesen im Kopf eine Verbindung zwischen den Strukturen behalten, die auch im Quelltext explizit hätte ausgedrückt werden können.

Namen die man irgendwann später einmal an „richtige” Werte bindet, sollte man nicht am Anfang an Werte binden, die nie verwendet werden.

Bei der ersten Schleife nach Eingabe der Genauigkeit werden die `x*` und `y*`-Namen unnötigerweise in der Schleife ständig neu berechnet, wo doch eigentlich nur die letzte Berechnung von Interesse ist. Die ständigen `float()`-Aufrufe sind unnötig, wenn man schon im Vorfeld dafür sorgt, dass die Datenstrukturen Gleitkommazahlen enthalten, oder man sorgt mit einem ``from __future__ import division`` dafür, dass der ``/``-Operator Gleitkommazahl-Ergebnisse liefert. Bei der Berechnung von `A1`, `A1`, `B1`, und `B2` sind die `float()`-Aufrufe auch unnötig, da der jeweilige Audruck auch bei ganzen Zahlen die gleichen Werte ergibt.

Die Schleife könnte man ausserdem durch zwei `sum()`-Aufrufe mit Generator-Ausdrücken ersetzen wenn man nicht die zusammengehörenden Werte in einzelnen Listen halten würde.

Von der Definition von `f()` bis zur Definition von `drange()` (exklusive) steht fast ausschliesslich sinnfreier Code‽

Nach den Definitionen der `*min()`- und `*max()`-Funktionen bindest Du deren Namen an neue Werte die aus dem Ergebnis von Aufrufen davon bestehen. Lass so einen Unsinn bitte. Da verliert man ganz schnell den Überblick welcher Wert an welcher Stelle im Programmablauf an welchen Wert/Typ gebunden ist.

Ein Beispiel wie man den Quelltext lesbarer formatieren kann:

Code: Alles auswählen

def U(x12, y12, x21, y21):
    return set(
        (
            f1(x12, y12) + lambda_ * (f1(x21, y21) - f1(x12, y12)),
            f2(x12, y12) + lambda_ * (f2(x21, y21) - f2(x12, y12))
        )
        for lambda_ in drange(0, 1, 0.001)
    )

Und eines wie man sich wiederholenden, nahezu identischen Quelltext vermeiden kann:

Code: Alles auswählen

def _extreme(extreme_f, f, x12, y12, x21, y21):
    return extreme_f(
        f(x12, y12) + lambda_ * (f(x21, y21) - f(x12, y12))
        for lambda_ in drange(0, 1, 0.001)
    )


l1min = partial(_extreme, min, f1)
l2max = partial(_extreme, max, f2)
l2min = partial(_extreme, min, f2)
l1max = partial(_extreme, max, f1)

Zu den falschen Ergebnissen: Teste die Funktionen einzeln und vergleiche das Ergebnis mit dem was Du erwartest. Dann ein paar ``print``-Anweisungen strategisch einstreuen um Zwischenergebnisse mit dem erwarteten Zwischenergebnissen zu vergleichen. Dann solltest Du dem Problem auf die Spur kommen. Vielleicht solltest Du auch mal das angesprochene `drange()`-Problem angehen.

[zwiety]

Ja das mit dem drange() Problem habe ich schon versucht. Ich würde gerne ein Intervall definieren bei dem ich lambda aus [0,1] wähle, aber ich finde keinen befehl oder keinen Weg wir ich dieses Intervall durchlaufen kann. Ich versuche nun nochmal die Tipps von oben abzuarbeiten und werde Stück für Stück das verbesserte Ergebniss posten, um zu sehen, ob ich die Tipps verstanden habe.

LG

[zwiety]

So ich hab mich nun mal damit beschäftigt das ganze ein wenig umzuschreiben und hab gerade den ersten Teil mal so geschrieben, dass es für außenstehende eventuell zu erkennen ist was in den einzelnen Schritten gemacht wird. Mein code sieht dann folgendermaßen aus

Code: Alles auswählen

# -*- coding: cp1252 -*-
import math
import numpy
from numpy import *
from numpy import linalg

Anzahl_Standorte=int(raw_input("Anzahl der existierenden Standorte: "))

Menge_Standorte=[]



def existierender_Standort(i):
    Koordinate1=int(raw_input("1.Koordinate: "))
    Koordinate2=int(raw_input("2.Koordinate: "))
    Standort=zeros([2,1],float)
    Standort[0][0]=Koordinate1
    Standort[1][0]=Koordinate2
    return Standort


def Menge_ex_Standorte(Anzahl_Standorte):
    for i in range(Anzahl_Standorte):
        Menge_Standorte.append(existierender_Standort(i))
    return Menge_Standorte

Menge_ex_Standorte(Anzahl_Standorte)
print "Die Menge der existierenden Standorte ist: ", Menge_Standorte

Menge_Gewichte=[]

def Gewicht(i):
    Koordinate1=int(raw_input("1.Koordinate: "))
    Koordinate2=int(raw_input("2.Koordinate: "))
    Gewicht=zeros([2,1],float)
    Gewicht[0][0]=Koordinate1
    Gewicht[1][0]=Koordinate2
    return Gewicht

def Menge_der_Gewichte(Anzahl_Standorte):
    for i in range(Anzahl_Standorte):
        Menge_Gewichte.append(Gewicht(i))
    return Menge_Gewichte


Menge_der_Gewichte(Anzahl_Standorte)
print Menge_Gewichte

tau=raw_input("Wert der Genauigkeit: ")


def Summe_Koordinate1_Gewicht(Menge_Gewichte):
    W=0
    for i in range(len(Menge_Gewichte)):
        W=W+Menge_Gewichte[i][0][0]
    return W

def Summe_Koordinate2_Gewicht(Menge_Gewichte):
    V=0
    for i in range(len(Menge_Gewichte)):
        V=V+Menge_Gewichte[i][1][0]
    return V

def lex_opt_Standort1(Menge_Gewichte,Menge_Standorte):
    A1=0
    for i in range(0,Anzahl_Standorte):
        A1=A1+Menge_Gewichte[i][0][0]*Menge_Standorte[i]
    x12=A1/Summe_Koordinate1_Gewicht(Menge_Gewichte)
    return x12

def lex_opt_Standort2(Menge_Gewichte,Menge_Standorte):
    A1=0
    for i in range(0,Anzahl_Standorte):
        A1=A1+Menge_Gewichte[i][1][0]*Menge_Standorte[i]
    x21=A1/Summe_Koordinate1_Gewicht(Menge_Gewichte)
    return x21

x12=lex_opt_Standort1(Menge_Gewichte,Menge_Standorte)
x21=lex_opt_Standort2(Menge_Gewichte,Menge_Standorte)



        

def f1(x12):
    f1=0
    for i in range(0,Anzahl_Standorte):
        f1=f1+ Menge_Gewichte[i][0][0]*((Menge_Standorte[i][0][0]-x12[0][0])**2)+Menge_Gewichte[i][0][0]*((Menge_Standorte[i][1][0]-x12[1][0])**2)
    return f1

def f2(x12):
    f2=0
    for i in range(0,Anzahl_Standorte):
        f2=f2+ Menge_Gewichte[i][1][0]*((Menge_Standorte[i][0][0]-x12[0][0])**2)+Menge_Gewichte[i][1][0]*((Menge_Standorte[i][1][0]-x12[1][0])**2)
    return f2

def f(x12):
    f=zeros([2,1],float)
    f[0][0]=f1(x12)
    f[1][0]=f2(x12)
    return f

Repraesentatives_System=[]
Repraesentatives_System.append(f(x12))
Repraesentatives_System.append(f(x21))
print Repraesentatives_System

Jetzt hab ich allerdings die Frage wie ich die Arrays wegbekomme, weil ich hätte gerne Vektoren darin stehen. Die Berechnungen die das Programm macht, stimmen mit meinen überein und ich finde dass das Programm schon vereinfacht wurde. Leider hab ich wie ihr das ja schon gemerkt hab nicht so viel Ahnung weil es eigentlich das erste mal ist das ich programmiere und das natürlich gleich für meine Diplomarbeit . Wäre nett wenn mir jemand sagen könnte, ob ich die Tipps bis dahin richtig verstanden habe und was eventuell so noch nicht richtig ist bzw. wie man es besser machen kann.
Weiterhin versuche ich jetzt das Problem mit dem drange() in den Griff zu bekommen aber ich weis nicht so recht wie ich das angehen soll weil ich nicht weis und auch nichts im internet finde, wie man sonst die Konvexkombination genauer definieren kann.

LG

[BlackJack]

@zwiety: Das sieht schon etwas besser aus. Und wenn es das richtige Ergebnis liefert ist das ja auch schon mal toll.

Du hast aber immer noch Code auf Modulebene der nicht in die Kategorie „definiert eine Konstante im weitesten Sinne” fällt und noch Funktionen die solche modulglobalen Objekte verändern und darauf zugreifen.

Ausserdem müllst Du Dir den Namensraum des Moduls mit dem Sternchenimport mit über 500 Namen voll:

Code: Alles auswählen

In [122]: len(dir(numpy))
Out[122]: 532

Da besteht schon eine reale Chance, dass man sich mal irgendwo bei einem Namen vertippt und zufällig einen dieser 500 erwischt. Sternchen-Importe machen Sinn wenn man in einer Python-Shell arbeitet um sich Tipparbeit zu sparen, aber in Quelltexten die dauerhafter bestehen als Shell-Eingaben, sollte man die Namen, die man benötigt explizit importieren, oder nur das Modul und dann über den Modulnamen auf dessen Inhalt zugreifen. Bei Numpy ist es nicht unüblich den Modulnamen beim Importieren an den Namen `np` zu binden.

Den reinen `numpy`-Import verwendest Du gar nicht und auch `linalg` nicht. (`math` übrigens auch nicht (mehr).) Und wenn ich beim drüber schauen nichts übersehen habe, verwendest Du auch `numpy` nicht wirklich. Ein Array-Objekt anzulegen, dass anscheinend unnötigerweise eine Dimension zu komplex ist, und damit dann nur Sachen zu machen, die man auch mit einer verschachtelten, beziehungsweise sogar einer einfachen Liste machen kann, ist nicht besonders sinnvoll. Das macht das Programm nur unnötig komplexer und langsamer. Numpy-Arrays bringen nur Vorteile wenn man Operationen darauf anwendet, die intern auf alle Elemente angewendet werden, oder zumindest auf Viele. Also wenn man Schleifen aus dem Python-Code durch Operationen ersetzt, die durch Schleifen innerhalb der Numpy-Objekte umgesetzt werden, welche in C oder Fortran implementiert sind und damit einen Geschwindigkeitsvorteil bieten.

Du hast auch immer noch viele unnötige Code-Wiederholungen. `existierender_Standort()` und `Gewicht()`, `Menge_ex_Standorte()` und `Menge_der_Gewichte()`, `Summe_Koordinate1_Gewicht()` und `Summe_Koordinate2_Gewicht()`, `lex_opt_Standort1()` und `lex_opt_Standort2()`, `f1()` und `f2()` unterscheiden sich jeweils nur ganz geringfügig. Da würde jeweils eine Funktion mit entsprechend mehr Argumenten genügen.

`existierender_Standort()` und `Gewicht()` sind von der Struktur her sogar identisch! Warum also zweimal den selben Code hinschreiben‽ Etwas abstrakter betrachtet erfragen beide eine Koordinate vom Benutzer. Beide verwenden das Argument `i` überhaupt nicht.

Warum erzeugst Du erst ein Array mit Nullen um dann die Elemente einzeln zu setzen, statt gleich ein Array mit den Werten zu erstellen? Und warum hat das die Form 2×1 statt ein einfacheres, eindimensionales Array? Bei jedem Zugriff ist der zweite Index 0 – das könnte man sich auch sparen. Letztendlich könnte man sich aber die Numpy-Arrays auch ganz sparen, wenn man den Datentyp gar nicht wirklich verwendet und stattdessen ein Tupel oder eine Liste mit den beiden Koordinaten-Werten erstellen. Da würde dann diese Funktion übrig bleiben:

Code: Alles auswählen

def erfrage_koordinate():
    return [
        float(raw_input('{0}. Koordinate: '.format(i + 1)) for i in xrange(2))
    ]

Du solltest Dir mal „list comprehensions” (LCs) anschauen. Die Funktionen `Menge_ex_Standorte()` und `Menge_der_Gewichte()` lassen sich damit ersetzen:

Code: Alles auswählen

Menge_Standorte = [erfrage_koordinate() for _ in xrange(Anzahl_Standorte)]

Da lohnt sich keine extra Funktion für.

`tau` wird zwar an einen Wert gebunden, aber nirgends verwendet.

In `Summe_Koordinate1_Gewicht()` verwendest Du 1:1 das „Anti-Pattern” mit der Zählschleife und dem Indexzugriff. Man kann *direkt* über die Elemente von Listen (und allen anderen iterierbaren Objekten) iterieren. Ohne den unnötigen Umweg über einen Index:

Code: Alles auswählen

# Statt:
for i in xrange(len(sequence)):
    print sequence[i]
# idiomatisches Python:
for item in sequence:
    print item

Zum Aufsummieren solltest Du Dir auch mal die `sum()`-Funktion und Generatorausdrücke anschauen. Damit werden die `Summe_*`-Funktionen jeweils zu Einzeilern.

`Summe_Koordinate2_Gewicht()` wird nirgends verwendet‽ Absicht?

Ah, in `lex_opt_Standort*()` wird dann doch ausgenutzt, dass es sich um Numpy-Arrays handelt. Allerdings hätte es hier auch ein eindimensionales getan. Und man sollte `A1` vielleicht nicht mit 0 initialisieren sondern mit einem Array mit 0en, damit sofort deutlich wird, dass es sich nicht um einen Skalarwert handelt. Hier ist auch wieder das „Anti-Pattern” mit der Zählschleife zu finden. Den Index kann man sich mittels `itertools.izip()` sparen. Wenn man ein eindimensionales Array für die Koordinaten verwendet, könnte eine allgemeinere `lex_opt_standort`-Funktion so aussehen:

Code: Alles auswählen

def lex_opt_standort(index, gewichte, standorte):
    a = sum(
        (g[index] * s for (g, s) in izip(gewichte, standorte)),
        np.zeros(2)
    )
    return a / Summe_Koordinate1_Gewicht(gewichte)

Wenn `gewichte` und `standorte` an dieser Stelle Numpy-Arrays wären, könnte man das wesentlich kompakter schreiben, weil man die Schleife dann ”in” diese Objekte verlegen kann.

`f1` und `f2` kann man ähnlich zusammenfassen und umschreiben:

Code: Alles auswählen

def f_i(x, index, gewichte, standorte):
    return sum(
        g[index] * ((s[0] - x[0])**2) + g[index] * ((s[1] - x[1])**2)
        for g, s in izip(gewichte, standorte)
    )

Auch hier könnte wahrscheinlich man mit zweidimensionalen Numpy-Arrays die Schleifen aus dem Python-Code entfernen.

[BlackJack]

@zwiety: Ich habe den Quelltext mal komplett überarbeitet (völlig ungetestet):

Code: Alles auswählen

from itertools import izip
import numpy as np


def erfrage_koordinate():
    return np.array(
        [float(raw_input('{0}. Koordinate: '.format(i + 1)) for i in xrange(2))]
    )


def lex_opt_standort(index, gewichte, standorte):
    a = sum(
        (g[index] * s for g, s in izip(gewichte, standorte)),
        np.zeros(2)
    )
    return a / sum(gewicht[0] for gewicht in gewichte)


def f_i(x, index, gewichte, standorte):
    return sum(
        # g[index] * ((s[0] - x[0])**2) + g[index] * ((s[1] - x[1])**2)
        # ⇒     (factoring)
        # g[index] * ((s[0] - x[0])**2 + (s[1] - x[1])**2)
        # ⇒     (using `numpy`)
        (g[index] * (s - x)**2).sum() for g, s in izip(gewichte, standorte)
    )


def f(x, gewichte, standorte):
    return [f_i(i, x, gewichte, standorte) for i in xrange(2)]


def main():
    anzahl_standorte = int(raw_input('Anzahl der existierenden Standorte: '))
    
    standorte = [erfrage_koordinate() for _ in xrange(anzahl_standorte)]
    print 'Die Menge der existierenden Standorte ist: ', standorte
    
    gewichte = [erfrage_koordinate() for _ in xrange(anzahl_standorte)]
    print gewichte
    
    xs = [lex_opt_standort(i, gewichte, standorte) for i in xrange(2)]
    
    repraesentatives_system = [f(x, gewichte, standorte) for x in xs]
    print repraesentatives_system


if __name__ == '__main__':
    main()

Bist Du sicher das bei `lex_opt_standort()` unanbhängig vom `index`-Argument immer die erste Komponente der Gewichte in der letzten Zeile genommen werden soll? Also dass in `lex_opt_Standort2()` bei Deinem Quelltext tatsächlich `Summe_Koordinate1_Gewicht()` aufgerufen werden sollte und nicht vielleicht `Summe_Koordinate2_Gewicht()`, was ja ansonsten gar nicht verwendet werden würde!?

Bei `f_i()` habe ich in den Kommentaren in zwei Schritten gezeigt wie die Vereinfachung zustande kommt. Der erste Schritt ist eine einfache mathematische Umformung und im zweiten wird ausgenutzt, dass `s` und `x` Numpy-Arrays sind, und man deshalb nicht auf den Komponenten einzeln operieren muss, sondern Operationen auf die gesamten Arrays anwenden kann.

Wenn `gewichte` und `standorte` zweidimensionale Arrays statt Listen mit eindimensionalen Arrays wären, könnte man noch mehr Arbeit auf Numpy-Operationen verschieben. Und falls meine Vermutung mit dem Aufruf von `Summe_Koordinate2_Gewicht()` stimmt, würde es noch ein weniger einfacher, weil man `gewichte` dann in eine passendere/günstigere Form bringen kann.

[zwiety]

Erstmal muss ich mich bedanken das du die so viel Mühe machst um mir zu helfen.

Ich hab mir jetzt deine Kommentare angeschaut und hab glaube ich das Prinzip dahinter ein wenig verstanden. Den Code habe ich getestet und nachdem ich einen Fehler behoben habe erhalte ich auch die richtigen Ergebnisse und bin faziniert. ich versuche jetzt mal so weiter zu machen.


Manche Dinge hatte ich definiert, weil der Algorithmus an dieser Stelle noch nicht fertig ist. Ich hatte erst einen Teil davon gemacht und wollte wenn dieser stimmt dann weiter machen. Ich beschäftige mich heute weiter mit dem Algorithmus und poste es dann hier dass du mir oder jemand anders vielleicht weiter helfen kannst. Jetzt kommt allerdings die Sache mit dem drange() bei der ich noch nicht weiter gekommen bin. Ich versuche nun mich damit zu beschäftigen und zu schauen ob ich dazu was finde wie ich die Mengen besser definieren kann.


LG
Zwiety

[zwiety]

Code: Alles auswählen

from itertools import izip
import numpy as np


def erfrage_koordinate():
    return np.array(
        [float(raw_input('{0}. Koordinate: '.format(i + 1))) for i in xrange(2)]
    )



def lex_opt_standort(index, gewichte, standorte):
    a = sum(
        (g[index] * s for g, s in izip(gewichte, standorte)),
        np.zeros(2)
    )
    return a / sum(gewicht[0] for gewicht in gewichte)


def f_i(x, index, gewichte, standorte):
    return sum(
        # g[index] * ((s[0] - x[0])**2) + g[index] * ((s[1] - x[1])**2)
        # ⇒     (factoring)
        # g[index] * ((s[0] - x[0])**2 + (s[1] - x[1])**2)
        # ⇒     (using `numpy`)
        (g[index] * (s - x)**2).sum() for g, s in izip(gewichte, standorte)
    )


def f(x, gewichte, standorte):
    return [f_i(x, i, gewichte, standorte) for i in xrange(2)]

def idealpunkt(xs,gewichte,standorte):
    return [f_i(xs[i],i,gewichte,standorte) for i in xrange(2)]


def main():
    anzahl_standorte = int(raw_input('Anzahl der existierenden Standorte: '))
    
    standorte = [erfrage_koordinate() for _ in xrange(anzahl_standorte)]
    print 'Die Menge der existierenden Standorte ist: ', standorte
    
    gewichte = [erfrage_koordinate() for _ in xrange(anzahl_standorte)]
    print 'Die Menge der Gewichte ist: ', gewichte

    genauigkeit=float(raw_input('Gewuenschte Genauigkeit: '))
    
    
    xs = [lex_opt_standort(i, gewichte, standorte) for i in xrange(2)]

    repraesentatives_system = [f(x, gewichte, standorte) for x in xs]
    print repraesentatives_system

    idealpunkt(xs, gewichte, standorte)


if __name__ == '__main__':
    main()

ich habe jetzt das Programm erweitert um die Berechnung des Idealpunktes. Jetzt möchte ich gerne zwei Mengen definieren, sowie ich die am Anfang beschrieben habe

Code: Alles auswählen

def drange(start, stop, step):
     r = start
     while r < stop:
         yield r
         r += step

def U(x12,y12,x21,y21):
    N1=drange(0,1,0.001)
    U={(f1(x12,y12)+lambd*(f1(x21,y21)-f1(x12,y12)),f2(x12,y12)+lambd*(f2(x21,y21)-f2(x12,y12)))  for lambd in N1}
    return U

def L(x12,y12,x21,y21):
    N1=drange(0,1,0.001)
    L1={(f1(x12,y12),f2(x12,y12)+lambd*(f2(x21,y21)-f2(x12,y12)))  for lambd in N1}
    L2={(f1(x12,y12)+lambd*(f1(x21,y21)-f1(x12,y12)),f2(x21,y21))  for lambd in N1}
    L=L1|L2
    return L

allerdings sind die ja aufgrund des drange() sehr ungenau und ich finde aber leider nichts dazu wie ich die genauer geben kann. ich benötige die beiden Mengen da ich dann zwischen diesen die Hausdorffdistanz berechnen möchte. Kann mir da jemand einen Tip geben wie ich die beiden Mengen definieren könnte?

[BlackJack]

@zwiety: Noch einmal die Frage zu `lex_opt_standort()`: Ist es wirklich so vorgesehen, dass in der ersten Summe ``g[index]`` steht und in der zweiten, unter dem Bruchstrich unabhängig von `index` immer ``gewicht[0]``?

Zu `drange()` magst Du vielleicht mal `arange()` und `linspace()` aus `numpy` anschauen, je nach dem was besser passt.

Probleme bei Deinen `set()`-Operationen sehe ich mit der Ungenauigkeit von Gleitkommaoperationen.

[zwiety]

Nein das war natürlich ein Schreibfehler von mir. Es ist Zufall das es das richtige Ergebniss liefert da in meinem Beispiel die beiden Summen das gleiche liefern.

Ich habe es verbessert, da es ein Leichtsinnsfehler von mir war.

Code: Alles auswählen

def lex_opt_standort(index, gewichte, standorte):
    a = sum(
        (g[index] * s for g, s in izip(gewichte, standorte)),
        np.zeros(2)
    )
    return a / sum(gewicht[index] for gewicht in gewichte)

Aber nochmal danke der Nachfrage.

Also vielleicht zur Erklärung. Ich möchte gerne einmal die Gerade zwischen den beiden Punkten in repraesentative_system betrachten und zum Anderen jeweis die Gerade von einem der Punkte zu dem Idealpunkt und möchte dann

max{sup inf l_2(x,y), sup inf l_2(x,y)}
xinL yinU yinU xinL

und damit komm ich gar nicht zurecht. Den anderen Teil konnt ich ja wenigstens auf meine "komische" Art programmieren aber hier weis ich gar nicht wie ich das machen soll.


ich schau mir nun grad linspace() und arange() an und muss sagen, dass ich von linspace() mehr halte, da ich ja die Schrittgröße genau wählen kann, also wie viele Werte er berechnen soll. Jetzt hab ich auch das ganze mal eingebaut, aller dings nicht allgemein sondern um es zu versuchen für meine erste Approximation. Jetzt hab ich ja allerdings wieder eine Ungenauigkeit drinnen, da mein Laptop wenn ich zu viele Werte wähle die Berechnung aller Werte nicht packt. Muss ich die Anzahl der Werte dann kleiner wählen oder hängt das an meinem Laptop und an mir?

[zwiety]

Also ich hab mich den Tag über mal mit der Definition der Mengen beschäftig und hab jetzt folgendes

Code: Alles auswählen

import math
from itertools import izip
import numpy as np


def erfrage_koordinate():
    return np.array(
        [float(raw_input('{0}. Koordinate: '.format(i + 1))) for i in xrange(2)]
    )



def lex_opt_standort(index, gewichte, standorte):
    a = sum(
        (g[index] * s for g, s in izip(gewichte, standorte)),
        np.zeros(2)
    )
    return a / sum(gewicht[index] for gewicht in gewichte)


def f_i(x, index, gewichte, standorte):
    return sum(
        # g[index] * ((s[0] - x[0])**2) + g[index] * ((s[1] - x[1])**2)
        # ⇒     (factoring)
        # g[index] * ((s[0] - x[0])**2 + (s[1] - x[1])**2)
        # ⇒     (using `numpy`)
        (g[index] * (s - x)**2).sum() for g, s in izip(gewichte, standorte)
    )


def f(x, gewichte, standorte):
    return [f_i(x, i, gewichte, standorte) for i in xrange(2)]

def idealpunkt(xs,gewichte,standorte):
    return [f_i(xs[i],i,gewichte,standorte) for i in xrange(2)]

def obere_approximation(xs,index1, index2, gewichte,standorte):
    U1 = np.linspace(f_i(xs[index1],index1, gewichte, standorte), f_i(xs[index2],index1 ,gewichte, standorte), num=1000)
    U2 = np.linspace(f_i(xs[index2],index2, gewichte, standorte), f_i(xs[index1], index2, gewichte, standorte), num=1000)
    U = zip(U1, U2)
    return [np.array(U[i]) for i in xrange(1000)]
    
    
def untere_approximation1(xs, index1, index2, gewichte, standorte):
    L1 = np.linspace(f_i(xs[index1], index1, gewichte, standorte), idealpunkt(xs, gewichte, standorte)[index1], num=1000)
    L2 = np.linspace(idealpunkt(xs, gewichte, standorte)[index2], f_i(xs[index1], index2, gewichte, standorte), num=1000)
    L = zip(L1,L2)
    return [np.array(L[i]) for i in xrange(500)]

def untere_approximation2(xs, index1, index2, gewichte, standorte):
    L1 = np.linspace(idealpunkt(xs, gewichte, standorte)[index1], f_i(xs[index2], index1, gewichte, standorte), num=1000)
    L2 = np.linspace(f_i(xs[index2], index2, gewichte, standorte), idealpunkt(xs, gewichte, standorte)[index2], num=1000)
    L = zip(L1,L2)
    return [np.array(L[i]) for i in xrange(500)]

def untere_approximation(xs, index1, index2, gewichte, standorte):
    return untere_approximation1(xs, 0, 1, gewichte, standorte)+untere_approximation2(xs, 0, 1, gewichte, standorte)






def main():
    anzahl_standorte = int(raw_input('Anzahl der existierenden Standorte: '))
    
    standorte = [erfrage_koordinate() for _ in xrange(anzahl_standorte)]
    print 'Die Menge der existierenden Standorte ist: ', standorte
    
    gewichte = [erfrage_koordinate() for _ in xrange(anzahl_standorte)]
    print 'Die Menge der Gewichte ist: ', gewichte

    genauigkeit=float(raw_input('Gewuenschte Genauigkeit: '))
    
    
    xs = [lex_opt_standort(i, gewichte, standorte) for i in xrange(2)]

    repraesentatives_system = [f(x, gewichte, standorte) for x in xs]
    print repraesentatives_system

    idealpunkt(xs, gewichte, standorte)

    U = obere_approximation(xs, 0, 1, gewichte,standorte)

    L = untere_approximation(xs, 0, 1, gewichte, standorte)

hab ich das nun so richtig verstanden oder gibt es einen Weg dies besser zu machen?

[BlackJack]

@zwiety: Ups, ich hätte schwören können das ich den folgenden Text schon auf Deinen Beitrag von Freitag 11:33 veröffentlich hatte. Na gut, dann etwas verspätet:

Mit *der* `lex_opt_standort()` kann man den Quelltext noch weiter vereinfachen und wenn ich jetzt keinen Fehler gemacht habe, deutlich mehr Arbeit auf `numpy` abwälzen:

Code: Alles auswählen

from itertools import izip
import numpy as np


def erfrage_koordinate():
    return (
        [float(raw_input('{0}. Koordinate: '.format(i + 1))) for i in xrange(2)]
    )


def lex_opt_standort(gewichte, standorte):
    return (gewichte * standorte).sum(0) / gewichte.sum()


def f_i(x, gewichte, standorte):
    return (gewichte * (standorte - x)**2).sum()


def f(x, gewichte, standorte):
    return [f_i(x, gs, standorte) for gs in gewichte]


def idealpunkt(xs, gewichte, standorte):
    return [f_i(x, gs, standorte) for x, gs in izip(xs, gewichte)]


def main():
    anzahl_standorte = int(raw_input('Anzahl der existierenden Standorte: '))
    
    standorte = np.array(
        [erfrage_koordinate() for _ in xrange(anzahl_standorte)]
    )
    print 'Die Menge der existierenden Standorte ist: ', standorte
    
    gewichte = np.array(
        [erfrage_koordinate() for _ in xrange(anzahl_standorte)]
    ).T.reshape(2, -1, 1)
    print 'Die Menge der Gewichte ist: ', gewichte

    # TODO: Unbenutzt!
    genauigkeit = float(raw_input('Gewuenschte Genauigkeit: '))
    
    xs = [lex_opt_standort(gs, standorte) for gs in gewichte]

    repraesentatives_system = [f(x, gewichte, standorte) for x in xs]
    print repraesentatives_system

    print idealpunkt(xs, gewichte, standorte)


if __name__ == '__main__':
    main()

Ich habe das Ganze bisher nur auf Quelltextebene betrachtet, ohne Berücksichtigung des Problems was mit diesen Berechnungen gelöst werden soll. Ich weiss auch nicht ob ich in der Lage bin mal eben so aus den Rechnungen eine Idee von dem geometrischen Problem zu bekommen.

Aber mir scheint Deine Umsetzung von mathematischen Mengen auf den Mengentyp in Python hier nicht ideal. In der Mathematik sind die Rechnungen immer „perfekt” und es gibt unendliche Mengen. Das kann man nicht wirklich mit einer endlichen Anzahl von ungenauen Gleitpunktzahlen umsetzen.

Wie gesagt weiss ich nicht was Du genau machen möchtest, aber mal angenommen man hat einen Punkt `x` und eine Gerade `L` und möchte wissen welcher Punkt auf der Geraden am nächsten an `x` liegt, also `min({d(x,y)|y∈L})` (`d` ist die Abstandsfunktion), dann wird man nicht eine Liste mit ganz vielen Punkten erzeugen die auf der Geraden liegen (und schon gar keine Menge im Sinne vom `set()`-Datentyp), sondern schauen welches Gleichungssystem man aufstellen und lösen muss um aus `x` und zum Beispiel zwei Punkten auf `L` den gewünschten Punkt ausrechnen zu können. Das wäre eine Rechnung, die mit einer handvoll Operationen genau den Punkt berechnet, gegenüber einer Lösung die Abstände für ganz viele Punkte berechnen und vergleichen muss und wahrscheinlich *sehr* viele Punkte betrachten muss um an das Ergebnis der direkten Berechnung heran zu kommen.

[zwiety]

Ja du hast mein Problem richtig verstanden. ich hätte gerne eine Gerade U die die beiden repräsentativen Punkte verbindet und dann noch mal die Vereinigung L aus zwei Geraden, wobei jeweils eine Gerade einen repräsentativen Punkt mit dem Idealpunkt verbindet. Da wir drei Punkte haben, erhalten wir also Wenn wir U und L zusammen betrachten ein Dreieck.

Und wie du auch richtig erkannt hast möchte ich dann die Distanz entsprechend berechnen und zwar kannst du dir es besser vorstellen wir, wenn du hier schaust http://de.wikipedia.org/wiki/Hausdorff-Abstand. Ich verstehe allerdings nicht ganz, wie ich für die Geraden ein Gleichungssystem aufstellen soll. Oder kann ich eine Funktion definieren wie sie in Mathe beschrieben wir durch f(x)=m*x + b wobei m die Steigung ist und b der y-Achsenabschnitt? An so eine vorgehensweise habe ich noch nicht gedacht, aber wenn das gehen würde, würde ich es auf die Art versuchen.

Wenn du mir sagst wie ich Bilder hier hochladen kann, dann kann ich genau eine Zeichnung davon schicken. Ich habe die Algorithmen die ich programmieren möchte schon mit Beispielen per Hand gerechnet und in Latex geschrieben. Allerdings weis ich nicht, wie ich die zugehörigen Bilder, die einiges verdeutlichen würden hier hochladen kann.

[webspider]

Wenn du mir sagst wie ich Bilder hier hochladen kann, dann kann ich genau eine Zeichnung davon schicken.

Normalerweise lädt man Bilder auf Imagehoster (imagebanana, ...) hoch (oder andere Alternativen, die Direktlinks erlauben wie zum Beispiel Dropbox) und stellt hier besagte Direktlinks ein.

[BlackJack]

@zwiety: Wenn Du etwas ohne den Rechner ausrechnen kannst, dann kannst Du das natürlich genau so *mit* dem Rechner ausrechnen. Du musst Dir halt überlegen welche Eingabegrössen Du hast, und was Du daraus ausrechnen möchtest. Bei meinem Beispiel mit dem Punkt auf einer Geraden mit dem kleinsten Abstand zu einem anderen gegebenen Punkt, geht das zum Beispiel wie hier beschrieben: https://en.wikipedia.org/wiki/Distance_ ... _to_a_line

[zwiety]

Ich hab bis jetzt das folgendes programmiert

Code: Alles auswählen

import math
from itertools import izip
import numpy as np


def erfrage_koordinate():
    return np.array(
        [float(raw_input('{0}. Koordinate: '.format(i + 1))) for i in xrange(2)]
    )



def lex_opt_standort(index, gewichte, standorte):
    a = sum(
        (g[index] * s for g, s in izip(gewichte, standorte)),
        np.zeros(2)
    )
    return a / sum(gewicht[index] for gewicht in gewichte)


def f_i(x, index, gewichte, standorte):
    return sum(
        # g[index] * ((s[0] - x[0])**2) + g[index] * ((s[1] - x[1])**2)
        # ⇒     (factoring)
        # g[index] * ((s[0] - x[0])**2 + (s[1] - x[1])**2)
        # ⇒     (using `numpy`)
        (g[index] * (s - x)**2).sum() for g, s in izip(gewichte, standorte)
    )


def f(x, gewichte, standorte):
    return [f_i(x, i, gewichte, standorte) for i in xrange(2)]

def idealpunkt(xs,gewichte,standorte):
    return [f_i(xs[i],i,gewichte,standorte) for i in xrange(2)]

def U(xs, index1, index2, gewichte, standorte):
    r = np.array([f_i(xs[index1], i, gewichte, standorte) for i in xrange(2)])
    a = np.array([f_i(xs[index2], i, gewichte, standorte) - f_i(xs[index1], i, gewichte, standorte) for i in xrange(2)])
    return r, a


    
    
def L(xs, index1, index2, gewichte, standorte, t1, t2):
    r = np.array(idealpunkt(xs, gewichte, standorte))
    a = np.array([abs(f_i(xs[index1], i, gewichte, standorte) - idealpunkt(xs, gewichte, standorte)[i]) for i in xrange(2)])
    b = np.array([abs(f_i(xs[index2], i, gewichte, standorte) - idealpunkt(xs, gewichte, standorte)[i]) for i in xrange(2)])
    l = r + t1 * a + t2 * b
    return l
    

def H(L, U):
    return max(h(L, U), h(U, L))




def distanz(p, U, xs, gewichte, standorte):
    r = np.array([U(xs, 0, 1, gewichte, standorte)[0][i] - p[i] for i in xrange(2)])
    a = np.array([U(xs, 0, 1, gewichte, standorte)[1][i] for i in xrange(2)])
    kreuzprod = a[0] * r[1] - a[1] * r[0]
    norm_laenge = math.sqrt(a[0]**2 + a[1]**2)
    print kreuzprod / norm_laenge
    
    
    
    


def main():
    anzahl_standorte = int(raw_input('Anzahl der existierenden Standorte: '))
    
    standorte = [erfrage_koordinate() for _ in xrange(anzahl_standorte)]
    print 'Die Menge der existierenden Standorte ist: ', standorte
    
    gewichte = [erfrage_koordinate() for _ in xrange(anzahl_standorte)]
    print 'Die Menge der Gewichte ist: ', gewichte

    genauigkeit=float(raw_input('Gewuenschte Genauigkeit: '))
    
    
    xs = [lex_opt_standort(i, gewichte, standorte) for i in xrange(2)]

    repraesentatives_system = [f(x, gewichte, standorte) for x in xs]
    print repraesentatives_system

    idealpunkt(xs, gewichte, standorte)

    p = idealpunkt(xs, gewichte, standorte)

    print distanz(p, U, xs, gewichte, standorte)
    
    


    


    


if __name__ == '__main__':
    main()

Ist das der richtige Ansatz?

[zwiety]

Also ich hab jetzt mal angefangen die Distanz zu programmieren. kann mir vielleicht jemand sagen ob das so richtig ist oder wie ich das besser machen kann, weil ich die h(L, U,....) und h(U, L, ....) benötige aber das so leider nicht geht.

Code: Alles auswählen

import math
from itertools import izip
import numpy as np


def erfrage_koordinate():
    return np.array(
        [float(raw_input('{0}. Koordinate: '.format(i + 1))) for i in xrange(2)]
    )



def lex_opt_standort(index, gewichte, standorte):
    a = sum(
        (g[index] * s for g, s in izip(gewichte, standorte)),
        np.zeros(2)
    )
    return a / sum(gewicht[index] for gewicht in gewichte)


def f_i(x, index, gewichte, standorte):
    return sum(
        # g[index] * ((s[0] - x[0])**2) + g[index] * ((s[1] - x[1])**2)
        # ⇒     (factoring)
        # g[index] * ((s[0] - x[0])**2 + (s[1] - x[1])**2)
        # ⇒     (using `numpy`)
        (g[index] * (s - x)**2).sum() for g, s in izip(gewichte, standorte)
    )


def f(x, gewichte, standorte):
    return [f_i(x, i, gewichte, standorte) for i in xrange(2)]

def idealpunkt(xs,gewichte,standorte):
    return [f_i(xs[i],i,gewichte,standorte) for i in xrange(2)]

def U(xs, index1, index2, gewichte, standorte, t):
    a = np.array([f_i(xs[index1], i, gewichte, standorte) for i in xrange(2)])
    r = np.array([f_i(xs[index2], i, gewichte, standorte) - f_i(xs[index1], i, gewichte, standorte) for i in xrange(2)])
    return a + t * r

def U1(xs, index1, index2, gewichte, standorte):
    a = np.array([f_i(xs[index1], i, gewichte, standorte) for i in xrange(2)])
    r = np.array([f_i(xs[index2], i, gewichte, standorte) - f_i(xs[index1], i, gewichte, standorte) for i in xrange(2)])
    return a, r
    
    
def L(xs, index1,index2, gewichte, standorte, t):
    a = np.array(idealpunkt(xs, gewichte, standorte))
    r = np.array([abs(f_i(xs[index1], i, gewichte, standorte) - idealpunkt(xs, gewichte, standorte)[i]) for i in xrange(2)])
    return a + t * r

def L1(xs, index1, index2, gewichte, standorte):
    a = np.array(idealpunkt(xs, gewichte, standorte))
    r = np.array([abs(f_i(xs[index1], i, gewichte, standorte) - idealpunkt(xs, gewichte, standorte)[i]) for i in xrange(2)])
    return a, r  

def H(L, U1, xs, index1, index2, gewichte, standorte):
    return max(
            h(L, U1, xs, index1, index2, gewichte, standorte)
        )


def h1(L, U1, xs, index1, index2, gewichte, standorte):
    return max(
            distanz(L(xs, index,index2, gewichte, standorte, t), xs, index1, index2, gewichte, standorte, U1)  
            for t in np.linspace(0, 1, num=500) for index in xrange(2)
            )


def h2(U, L1, xs, index1, index2, gewichte, standorte):
    return max(
            distanz(U(xs, index1, index2, gewichte, standorte, t), xs, index1, index2, gewichte, standorte, L1)  
            for t in np.linspace(0, 1, num=500) for index in xrange(2)
            )

    

def distanz(p, xs, index1, index2, gewichte, standorte, U1):
    s1 = sum(
            U1(xs, index1, index2, gewichte, standorte)[1] * ( p - U1(xs, index1, index2, gewichte, standorte)[0])
        )
    s2 = sum(
            U1(xs, index1, index2, gewichte, standorte)[1]**2
        )
    t = s1 / s2
    q = U(xs, index1, index2, gewichte, standorte, t)
    return math.sqrt((p[0] - q[0])**2 + (p[1]- q[1])**2)
    
    
    


def main():
    anzahl_standorte = int(raw_input('Anzahl der existierenden Standorte: '))
    
    standorte = [erfrage_koordinate() for _ in xrange(anzahl_standorte)]
    print 'Die Menge der existierenden Standorte ist: ', standorte
    
    gewichte = [erfrage_koordinate() for _ in xrange(anzahl_standorte)]
    print 'Die Menge der Gewichte ist: ', gewichte

    genauigkeit=float(raw_input('Gewuenschte Genauigkeit: '))
    
    
    xs = [lex_opt_standort(i, gewichte, standorte) for i in xrange(2)]

    repraesentatives_system = [f(x, gewichte, standorte) for x in xs]
    print repraesentatives_system

    idealpunkt(xs, gewichte, standorte)

    print h1(L, U1, xs, 0, 1, gewichte, standorte)

    
    


if __name__ == '__main__':
    main()