Ich hätte mal eine Frage. Ich habe einen Algorithmus geschrieben der sehr viel Zeit benötigt.
Code: Alles auswählen
from itertools import izip
import numpy as np
import math
def erfrage_koordinate():
return np.array(
[float(raw_input('{0}. Koordinate: '.format(i + 1))) for i in xrange(2)]
)
def lex_opt_standort(index1,index2, gewichte, standorte):
W = sum(gewichte[i][index1] for i in xrange(len(gewichte)))
sortiert=[[standorte[i][index2], gewichte[i][index1]] for i in xrange(len(standorte))]
sortiert.sort()
i = 0
p = sortiert[i][1]
while p < (W/2) and i <=len(gewichte):
i = i+1
p = p + sortiert[i][1]
if p <= (W/2):
opt ={sortiert[i][0],sortiert[i+1][0]}
elif p > (W/2):
opt = {sortiert[i][0]}
return opt
def kanidaten(index, gewichte, standorte):
return [[x1,x2] for x1 in lex_opt_standort(index,0, gewichte, standorte)
for x2 in lex_opt_standort(index,1, gewichte, standorte)]
def lex_opt_Zielwert(index, gewichte, standorte):
return [min(
f(x, gewichte, standorte)[i] for x in kanidaten(index, gewichte,standorte)
) for i in xrange(2)]
def f(x, gewichte, standorte):
return [sum(
(g[i] * abs(s - x)).sum() for g, s in izip(gewichte, standorte)
) for i in xrange(2)]
def flaecheninhalt(Y1, Y2):
return (Y2[0] - Y1[0]) * (Y1[1] - Y2[1])
def stoppkriterium(Y1, Y2, genauigkeit, Liste, F):
flaeche = flaecheninhalt(Y1, Y2)
if genauigkeit < flaeche:
Liste.append([Y1, Y2])
F.append(flaeche)
return Liste
def epsilon_bedingung(Y1,Y2):
return Y1[0] + (Y2[0] - Y1[0])/2
def steigung(gewichte, index, p):
return sum(
gewichte[i][index] for i in range(0,p+1)
) - sum(
gewichte[i][index] for i in range(p+1, len(gewichte))
)
def gewSum(index1, index2 , p, gewichte, standorte):
return sum(
gewichte[i][index1] * standorte[i][index2] for i in range(0, p+1)
) - sum(
gewichte[i][index1] * standorte[i][index2] for i in range(p+1, len(gewichte))
)
def zwischenwert(x, index, gewichte, standorte):
return sum(
gewichte[i][0] * abs(standorte[i][index] - x) for i in xrange(len(gewichte))
)
def res_kanidaten(epsilon, gewichte, standorte):
kanidaten = []
for j in xrange(len(gewichte)):
x = standorte[j][0]
t = epsilon - zwischenwert(x,0, gewichte, standorte)
v = standorte[j][1]
s = epsilon - zwischenwert(x,1, gewichte, standorte)
for l in xrange(len(gewichte)):
y = (t + gewSum(0, 1, l, gewichte, standorte)) / steigung(gewichte, 0, l)
u = (s + gewSum(0, 0, l, gewichte, standorte)) / steigung(gewichte, 0, l)
if f([x,y], gewichte, standorte)[0] == epsilon:
kanidaten.append([x,y])
if f([v,u], gewichte, standorte)[0] == epsilon:
kanidaten.append([v,u])
return kanidaten
def res_Zielwert(epsilon, gewichte, standorte):
return [epsilon, min(
f(x, gewichte, standorte)[1] for x in res_kanidaten(epsilon, gewichte,standorte)
) ]
def iteration(Liste, F, gewichte, standorte, repraesentatives_system, genauigkeit):
while len(Liste) > 0:
u = F.index(max(F))
Y1 = Liste[u][0]
Y2 = Liste[u][1]
F.remove(F[u])
Liste.remove(Liste[u])
epsilon = epsilon_bedingung(Y1,Y2)
Y3 = res_Zielwert(epsilon, gewichte, standorte)
repraesentatives_system.append(Y3)
stoppkriterium(Y1, Y3, genauigkeit, Liste, F)
stoppkriterium(Y3, Y2, genauigkeit, Liste, F)
return repraesentatives_system
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: '))
repraesentatives_system = [lex_opt_Zielwert(i, gewichte, standorte) for i in xrange(2)]
Y1 = repraesentatives_system[0]
Y2 = repraesentatives_system[1]
Liste = []
F = []
stoppkriterium(Y1, Y2, genauigkeit, Liste, F)
iteration(Liste, F, gewichte, standorte, repraesentatives_system, genauigkeit)
print 'Das repräsentative System ist gegeben durch: Rep= ', repraesentatives_system
if __name__ == '__main__':
main()
Code: Alles auswählen
def res_kanidaten(epsilon, gewichte, standorte):
kanidaten = []
for j in xrange(len(gewichte)):
x = standorte[j][0]
t = epsilon - zwischenwert(x,0, gewichte, standorte)
v = standorte[j][1]
s = epsilon - zwischenwert(x,1, gewichte, standorte)
for l in xrange(len(gewichte)):
y = (t + gewSum(0, 1, l, gewichte, standorte)) / steigung(gewichte, 0, l)
u = (s + gewSum(0, 0, l, gewichte, standorte)) / steigung(gewichte, 0, l)
if f([x,y], gewichte, standorte)[0] == epsilon:
kanidaten.append([x,y])
if f([v,u], gewichte, standorte)[0] == epsilon:
kanidaten.append([v,u])
return kanidatenverbessern könnte?
