[PYTHON] Solution optimale en combinant les copeaux les plus longs
Résolvez la plus longue compression
Optimisation de combinaison peut être utilisé pour résoudre facilement la plus longue compression.
Formulation
Ceci est une variante du problème de correspondance maximum pour le graphe en deux parties dans Problème typique. Soit $ kw $ le mot utilisé pour shiritori. Disposez $ kw $ à gauche et à droite, avec la gauche en tête et la droite en piste. Et pensez à dessiner une ligne lors de la connexion. Dans la figure ci-dessous, «alignas» est suivi de «taille de».
Nous utiliserons $ x_ {ij} \ in \ {0, 1 } $ pour indiquer s'il faut tracer cette ligne ou non.
| $ \ mbox {objective} $ | $ \ sum_i {\ sum_j {x_ {ij}}} $ | Connectez-vous autant que possible (0) |
| $ \ mbox {variables} $ | $ x_ {ij} \ in \ {0, 1 \} ~ \ forall i, j $ Si | $ kw_i $ est à côté de $ kw_j $ (1) |
| $ y_i \ ge 0 ~ \ forall i $ | Indique si $ kw_i $ démarre (2) | |
| $ z_i \ ge 0 ~ \ forall i $ | $ kw_i $ commande (3) | |
| $ \ mbox {soumis à} $ | $ \ sum_j {x_ {ij}} = 1 ~ \ forall i $ | $ Le nombre de kw_i $ est 1 ou moins (4) |
| $ \ sum_j {x_ {ji}} = 1 ~ \ forall i $ | $ kw_i $ peut être entré en 1 ou moins (5) | |
| $ \ sum_j {x_ {ij}} \ le \ sum_j {x_ {ji}} + y_i ~ \ forall i $ | $ y $ contraintes (6) | |
| $ z_i \ le z_j + 1- (n + 1) \ times (1-x_ {ij}) ~ \ forall i, j $ | $ z $ contraintes (7) ) | |
| $ \ sum_i {y_i} = 1 $ | Un seul début (8) |
Résoudre avec Python
Utilisons 84 mots-clés C ++. Supposons que les mots-clés se trouvent dans un tableau de chaînes (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(',')
[pulpe](http://qiita.com/Tsutomu-KKE@github/items/bfbf4c185ed7004b5721#%E3%82%BD%E3%83%95%E3%83%88%E3%81%AE%E3%82 Formulons et résolvons en utilisant% 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) #Modèle mathématique
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_i à kw_Se connecter à j(1)
y = [LpVariable('y%d'%i, lowBound=0) for i in r] # kw_Si je suis le premier(2)
z = [LpVariable('z%d'%i, lowBound=0) for i in r] # kw_à mon tour(3)
m += lpSum(x[i][j] for i in r for j in r) #Connectez-vous autant que possible(0)
for i in r:
cou = lpSum(x[i][j] for j in r) # kw_Nombre sortant de i
cin = lpSum(x[j][i] for j in r) # kw_Numéro à saisir i
m += cou <= 1 # kw_Le nombre de i est 1 ou moins(4)
m += cin <= 1 # kw_Le nombre qui peut entrer i est 1 ou moins(5)
m += cou <= cin + y[i] #Contraintes sur y(6)
for j in r:
m += z[i] <= z[j]-1+(n+1)*(1-x[i][j]) #Contraintes sur z(7)
m += lpSum(y) == 1 #Un seul au début(8)
%time m.solve() #Solution
print(int(value(m.objective)) + 1) #Nombre maximum de copeaux
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
Si l'échelle est grande, reportez-vous à Résolution du problème de compression le plus long.
Post-scriptum 2017/1/16 Ajout de la variable z pour éviter les solutions contenant des boucles. S'il y a une boucle, l'équation (7) ne tiendra pas.
référence: J'ai recherché le nom de station le plus long en Python CodeIQ "Optimisation de combinaison: faisons le plus long shiritori à partir de mots réservés C ++!" Combinez et résolvez les Allemands de manière optimale Réflexion sur les menus par optimisation combinée J'ai essayé d'optimiser le séchage du linge
Recommended Posts