[PYTHON] Optimale Lösung durch Kombination der längsten Späne

Löse den längsten Druck

Mit Kombinationsoptimierung können Sie den längsten Druck leicht lösen.

Formulierung

Dies ist eine Variante des Problems der maximalen Übereinstimmung für das zweiteilige Diagramm in Typisches Problem. Sei $ kw $ das Wort für Shiritori. Ordnen Sie $ kw $ links und rechts an, mit der linken als Führung und der rechten als Spur. Und denken Sie daran, beim Verbinden eine Linie zu ziehen. In der folgenden Abbildung folgt auf "alignas" "size of".

image

Wir werden $ x_ {ij} \ in \ {0, 1 } $ verwenden, um anzugeben, ob diese Linie gezogen werden soll oder nicht.

$ \ mbox {Ziel} $ $ \ sum_i {\ sum_j {x_ {ij}}} $ Verbinde so viel wie möglich (0)
$ \ mbox {variables} $ $ x_ {ij} \ in \ {0, 1 \} ~ \ forall i, j $ Ob $ kw_i $ neben $ kw_j $ (1) steht
$ y_i \ ge 0 ~ \ forall i $ Gibt an, ob $ kw_i $ startet (2)
$ z_i \ ge 0 ~ \ forall i $ $ kw_i $ order (3)
$ \ mbox {vorbehaltlich} $ $ \ sum_j {x_ {ij}} = 1 ~ \ forall i $ $ Die Zahl von kw_i $ ist 1 oder weniger (4)
$ \ sum_j {x_ {ji}} = 1 ~ \ forall i $ $ kw_i $ kann in 1 oder weniger (5) eingegeben werden
$ \ sum_j {x_ {ij}} \ le \ sum_j {x_ {ji}} + y_i ~ \ für alle i $ $ y $ Einschränkungen (6)
$ z_i \ le z_j + 1- (n + 1) \ times (1-x_ {ij}) ~ \ forall i, j $ $ z $ Einschränkungen (7) )
$ \ sum_i {y_i} = 1 $ Nur ein Anfang (8)

Löse mit Python

Verwenden wir 84 C ++ - Schlüsselwörter. Angenommen, die Schlüsselwörter befinden sich in einem Array von Zeichenfolgen (kw).

python


kw = "alignas,alignof,and,and_eq,asm,auto,bitand,bitor,bool,break,case," \
     "catch,char,char16_t,char32_t,class,compl,const,constexpr,const_cast," \
     "continue,decltype,default,delete,do,double,dynamic_cast,else,enum," \
     "explicit,export,extern,false,float,for,friend,goto,if,inline,int,long," \
     "mutable,namespace,new,noexcept,not,not_eq,nullptr,operator,or,or_eq," \
     "private,protected,public,register,reinterpret_cast,return,short," \
     "signed,sizeof,static,static_assert,static_cast,struct,switch,template," \
     "this,thread_local,throw,true,try,typedef,typeid,typename,union," \
     "unsigned,using,virtual,void,volatile,wchar_t,while,xor,xor_eq".split(',')

[Zellstoff](http://qiita.com/Tsutomu-KKE@github/items/bfbf4c185ed7004b5721#%E3%82%BD%E3%83%95%E3%83%88%E3%81%AE%E3%82 Formulieren und lösen wir mit% A4% E3% 83% B3% E3% 82% B9% E3% 83% 88% E3% 83% BC% E3% 83% AB).

python


from pulp import * # pip install pulp
n, r = len(kw), range(len(kw))
m = LpProblem(sense=LpMaximize) #Mathematisches Modell
x = [[0 if kw[i][-1] != kw[j][0] else LpVariable('x%d_%d'%(i,j), cat=LpBinary)
      for j in r] for i in r] # kw_ich zu kw_Gibt an, ob eine Verbindung zu j hergestellt werden soll(1)
y = [LpVariable('y%d'%i, lowBound=0) for i in r] # kw_Ob ich der erste bin(2)
z = [LpVariable('z%d'%i, lowBound=0) for i in r] # kw_Ich bin dran(3)
m += lpSum(x[i][j] for i in r for j in r) #Verbinde so viel wie möglich(0)
for i in r:
    cou = lpSum(x[i][j] for j in r) # kw_Nummer kommt aus i
    cin = lpSum(x[j][i] for j in r) # kw_Nummer zur Eingabe i
    m += cou <= 1 # kw_Die Zahl von i ist 1 oder weniger(4)
    m += cin <= 1 # kw_Die Zahl, die i eingeben kann, ist 1 oder weniger(5)
    m += cou <= cin + y[i] #Einschränkungen für y(6)
    for j in r:
        m += z[i] <= z[j]-1+(n+1)*(1-x[i][j]) #Einschränkungen für z(7)
m += lpSum(y) == 1 #Nur eine am Anfang(8)
%time m.solve() #Lösung
print(int(value(m.objective)) + 1) #Maximale Anzahl Späne
rr = range(1,n+1)
vx = np.vectorize(value)(x).astype(int)
i, s = 0, int(np.vectorize(value)(y)@rr)
while s:
    if i:
        print(' -> ', end='')
    i += 1
    print('[%d]%s'%(i,kw[s-1]), end=' ')
    s = vx[s-1]@rr
>>>
35
[1]alignas  -> [2]signed  -> [3]default  -> [4]typedef  -> 
[5]friend  -> [6]do  -> [7]operator  -> [8]reinterpret_cast  -> 
[9]thread_local  -> [10]long  -> [11]goto  -> [12]or  -> 
[13]register  -> [14]return  -> [15]new  -> [16]wchar_t  -> 
[17]true  -> [18]export  -> [19]throw  -> [20]while  -> 
[21]else  -> [22]enum  -> [23]mutable  -> [24]explicit  -> 
[25]this  -> [26]static  -> [27]class  -> [28]sizeof  -> 
[29]float  -> [30]template  -> [31]extern  -> [32]noexcept  -> 
[33]typeid  -> [34]dynamic_cast  -> [35]try

Wenn der Maßstab groß ist, lesen Sie Lösen des längsten Squeeze-Problems.

2017/1/16 Nachtrag Variable z hinzugefügt, um Lösungen mit Schleifen zu vermeiden. Wenn es eine Schleife gibt, gilt Gleichung (7) nicht.

Referenz: Ich habe nach dem längsten Stationsnamen in Python gesucht CodeIQ "Kombinationsoptimierung: Machen wir die längsten Shiritori aus reservierten C ++ - Wörtern!" Kombiniere und löse die Deutschen optimal Über Menüs durch Kombinationsoptimierung nachdenken Ich habe versucht, beim Trocknen der Wäsche zu optimieren