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».

image

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