Questo è un problema di ottimizzazione che riguarda la corrispondenza delle stringhe con i caratteri jolly. Abbiamo un set di caratteri jolly, ognuno contrassegnato con un "punteggio" numerico, come di seguito.
Pattern Score
*AA* 20
*ABB* 10
*BA* 5
*C* -5
*B*A* -10
*AAAA* -100
In questo esempio il vocabolario, V , è {A, B, C} .
Una stringa normale (una stringa senza caratteri jolly) può essere assegnata a un punteggio prendendo la somma dei punteggi dei modelli di caratteri jolly corrispondenti.
La regola per il conteggio del numero di corrispondenze di un modello jolly in una stringa normale è che, per ogni corrispondenza univoca, il carattere non jolly più a sinistra del modello jolly deve corrispondere a un carattere diverso della stringa normale. Ad esempio, il carattere non jolly più a sinistra di *B*A* è B . *B*A* corrisponde quindi alla stringa normale BABAAA due volte, non sette.
Esempio di punteggi a stringa normale:
String Score
ABB 10
ABBABB 5
CAAA 35
CAAAA -45
BAACBAC 0
L'obiettivo è generare stringhe su V che abbiano il punteggio più alto possibile (o, in mancanza, un punteggio "ragionevolmente alto") per una determinata lunghezza massima della stringa.
L'efficienza è importante: la lunghezza massima della stringa, la dimensione del vocabolario e il numero di caratteri jolly potrebbero essere entrambi > 100, quindi lo spazio della soluzione può essere abbastanza grande.