"Beste Zuweisung" //EDIT: für ein Photomosaic

[lordnaikon]

@Trichter: Danke für den Vorschlag, an sowas ähnliches hab ich auch schon gedacht, nur auf das Zählen wie oft ein Bild vorgeschlagen wurde (also sich in einer Vorschlagsliste befindet) bin ich noch nicht gekommen, vielleicht klappt das ja wirklich.. muss ich nochmal drüber grübeln. Irgendwie klingt es intuitiv als wäre das ne brauchbare Lösung, kann jetzt aber noch nicht sagen warum; das mit dem zufällig verteilen muss ich erstmal außen vor stellen, ganz einfach deshalb: sollte ich nun auch mal die Zeit haben es zu implementieren, muss ich es visuell vergleichen können, also wie der "Sichtbare"fehler linear zunimmt. Vielleicht zählt man den Fehler ja mal.
Aber dazu muss ich mein kleines Script erstmal komplett neu machen ..(und immer die gute alte Zeit )
Ich denke ich werde höchstwahrscheinlich auf "solche" Ansätze zurück kommen müssen. Die Laufzeitkomplexität macht mir bei meiner Zielgröße von 50k -200k schon sehr zu schaffen. Welchen Wert hatte ich hier mal in den Raum gestellt für die Anzahl der lokalen Fehler ich glaube 2.500.000.000. Das macht bei einer Laufzeit von O(n²) schon beachtliche 6,25 Trillionen! ... grr ...

@BlackJack: Ich glaube ich versteh jetzt deinen Gedankengang. Ich hab wohl einfach den Fehler gemacht den Worten von Cormen bild zu vertrauen und den Sinn Deiner Erweiterung nicht verstanden habe. Ich fasse das nochmal zusammen um hier keine Missverständnisse meiner seits aufkommen zu lassen. Cormen "missbraucht" Ford-Fulkerson um einfach zu zählen. Den Bipa. Graph wandelt er in ein Netzwerk dessen Kanten alle auf eins gesetzt werden. Dies tut er aus dem einzigen Grunde um die Vorraussetzungen für die "Paarung" zu erfüllen (e1,e2 elem. M disjunkt). So ist es nämlich nicht möglich zwei Kanten an einem Knoten aufzubauen, denn der Fluss ist schon auf eins beschränkt. Ford-Fulkerson versucht nun den Maximalen-Fluss zu finden und der entspricht dann auch der Anzahl an "Paarungs"kanten. Diejenigen Kanten mit dem "meisten" Fluss ... oder besser die nicht Teil des Residualgraphen sind und den Fluss "eins" haben (also überhaupt fluss) sind nun Teil der Paarung.


Jetzt kommst Du und "missbrauchst" Cormen in dem du den Zu- und Abfluss der Quelle und Senke bei "eins" lässt(das stellt die Bedingung der Paarung sicher) und suchst nun mit Ford-Fulkerson nach dem maximalem Fluss in dem Bipat. Graphen.


Und jetzt kommt Der Clou: Ich habe jetzt die Paarungen(wegen des auf eins begrenzten Flusses der Quelle und Senke) mit dem Maximalen Fluss .. dem globalen Fehler!!

Code: Alles auswählen

k1 {'b1': 0, 'b2': 0, 'b3': 1}          k1,b3 = 13
k3 {'b1': 1, 'b2': 0, 'b3': 0}  ==>     k3,b1 = 13   ==>  maximal möglicher gesammt Fehler von 31
k2 {'b1': 0, 'b2': 1, 'b3': 0}          k2,b2 = 5

jetzt sollte ich (wie du schon sagtest) den Fehler anders interpretieren (negieren .. oder invers ich denk mir da was aus) und dann sollte das gehen!!

Jetzt kommt noch das dicke Ende, die Laufzeitkomplexität so richtig hab ich da nix gefunden nur bei Wiki. O(E*f) wobei f der maximale Fluss sein soll oder aber O(V + E²) wobei ich wieder bei meinen 6,25 Trillionen wäre. Lässt sich auch Push-Relabel hier anwenden der O(V² + E) hat wären dann nur 2,5 Milliarden (und das mein 50K Bildern)

[lordnaikon]

Ich muss meine Euphorie leider wieder zurück nehmen :K

Wie es der Zufall so will, hat der olle Murphy mal wieder zugeschlagen. Eben beim Nudeln kochen lassen gemerkt, als ich es mal drauf ankommen lassen wollte den "min"fehler zu bekommen, das ich immer das gleiche Ergebnis bekomme . Damit will ich sagen: egal welche Gewichte die Kanten haben, es kommt immer die gleiche Reihenfolge oder Paarung bei raus also immer k1,b3; k2,b2; k3,b1. ZUFÄLLIG war das aber bei meiner Konstallation das richtige Ergebnis ... verdammich noch mal

Anschienend benutzt der Ford-Fulkerson algo von networkx eine nicht ganz so zufällige Auswahl der Pfade.

Mach ich vielleicht etwas falsch?

hier mal der code:

Code: Alles auswählen

import networkx as nx
import matplotlib.pyplot as plt

G=nx.DiGraph()
#die Bipat. Knoten
G.add_nodes_from(["k1","k2","k3","b1","b2","b3"])
G.add_nodes_from(["s","t"])
#hier kann man gerne die kapazitaeten tauschen, immer drei geben eine zeile ... 
capacities = [{'capacity':x} for x in [2,1,13,8,5,7,13,10,2]]
#capacities = [{'capacity':x} for x in [9,8,7,6,5,4,3,2,1]]
ks = [ "k%s" % str(x) for x in [1,1,1,2,2,2,3,3,3]]
bs = [ "b%s" % str(x) for x in [1,2,3,1,2,3,1,2,3]]
G.add_edges_from(zip(ks,bs,capacities))

capacities2 = [{'capacity':x} for x in [1,1,1,1,1,1]]
st = [ "s" if x<3 else "b%s" % str(x-2) for x in range(6)]
kb = [ "k%s" % str(x+1) if x<3 else "t"  for x in range(6)]
G.add_edges_from(zip(st,kb,capacities2))

#setze position der Knoten
pos=nx.spring_layout(G)
ik = 0
ib = 0
for edge, e_pos in pos.iteritems():
    if "k" in edge: 
        e_pos[0] = 0.1
        e_pos[1] = ik * 0.1
        ik = ik+1
    if "b" in edge: 
        e_pos[0] = 0.3
        e_pos[1] = ib * 0.1
        ib = ib+1
    if "s" in edge:
        e_pos[0] = -0.03
        e_pos[1] = 0.1
    if "t" in edge:
        e_pos[0] = 0.43
        e_pos[1] = 0.1

flow,F=nx.ford_fulkerson(G, 's', 't')

print "max_flow:",flow
print "F","xxx","\n\n\n"

for el, val in F.iteritems():
    print el, val,
    if "k" in el:
        for pic, flow in val.iteritems():
            if flow > 0:
                print pic,
                print "= ",G[el][pic]["capacity"]
                pass				
nx.draw(G,pos)

nx.draw_networkx_edge_labels(G,pos) 

plt.show()
#plt.savefig("path2.png")