regole di corrispondenza dato un input (algoritmo)

Question

Supponiamo Ho le seguenti categorie (con i loro valori possibili):

animal: any, cat, dog 
color: any, white, black, gray 
gender: any, male, female 
[...] 

o più in generale ...

category: <array of values> 

(1) Diciamo Ho una serie di regole configurabili come:

when animal is any, color is gray, gender is male, call x 
when animal is dog, color is gray, gender is male, call y 
when animal is any, color is any, gender is any, call z 
[...] 

(2) E alcuni valori di input.

D. Esiste un algoritmo che risolva il problema di trovare una regola di corrispondenza (con una priorità data alla regola più specifica trovata) in base all'input fornito?

Es.1:

input (animal:dog, color:gray, gender:male) 

sarebbe chiamare "y"

Es.2:

input (color:gray, gender:female) 

sarebbe chiamare "z"

è la più idonea modo per farlo è costruire un albero di ricerca in base alle regole (ogni livello dell'albero è una categoria)?

piace:

- any animal 
    - any color 
    - any gender => z 
    - gray 
    - male => x 
- dog 
    - gray 
    - male => y 

C'è un modo migliore di farlo?

Grazie!

Answer 1

Un albero di decisione con i seguenti modifiche avrebbe funzionato:

1. Creare l'albero decisionale in modo normale con 'qualsiasi' quanto i bordi usando tutte le regole

2. Mentre attraversa in modo ricorsivo, traversata per raggiungere 'valore' e 'qualsiasi' e tenere traccia del numero 'di ogni in ogni soluzione, tornare quello con minima' qualsiasi

   def traverse (valori, livello, albero, AnyCount): Se albero è è una foglia: ritorno (appr_func , anyCount)

   v1 = None 
   if values[level] in tree: 
       v1 = traverse(values, level+1, tree[values[level]]], anyCount) 
   
   v2 = None 
   if 'any' in tree: 
       v2 = traverse(values, level+1, tree['any'], anyCount+1) 
   
   if v1!=None: 
       if v2!=None: 
        if v1[1]<v2[1]: 
         return v1 
        else: 
         return v2 
       else: 
        return v1 
   elif v2!=None: 
       return v2 
   else: 
       return None 
   

Answer 2

Vorrei inserire le regole in una mappa e quindi cercare con lo stesso hash.

map[hash(animal, color, gender)] = function to call 

call map[hash(inputanimal, inputcolor, inputgender)] 

Ciò garantirebbe una più rapida creazione di regole e la risoluzione della funzione corretta da chiamare in base all'input.

Se la regola deve essere abbinato esattamente oppure cadere al generico qualsiasi, qualsiasi, qualsiasi, allora è semplicemente fatto da:

if map.contains(hash(inAnimal, inColour, inGender)) 
    x = map[hash(inAnimal, inColour, inGender)] 
else 
    x = map[hash(any, any, any)] 

caso contrario, se si inizia con l'ingresso e seleziona il ogni regola sulla successione ogni parametro quindi potresti farlo.

La funzione hash accetta una matrice di valori. Quando si tenta di associare una regola, si inizia con l'input e successivamente si passa a qualsiasi, finché non si trova una corrispondenza.

def key hash(array[]) 

....

processo di risoluzione ...

input[] = {inAnimal, inColour, inGender} 
function x 
for(i = 0 to input.size) { 
    if(map.contains(hash(input)) { 
     x = map[hash(input)] 
     break 
    } 
    input[i] = any 
} 
call x 

Answer 3

La risposta giusta dipende da come fantasia si desidera ottenere. Ci sono cose come lo Rete algorithm. Google "sistemi esperti". Ho lavorato in grandi aziende che hanno sistemi di valutazione delle regole, ma non li scrivono internamente: acquistano un pacchetto commerciale.

Se le vostre esigenze sono semplici, un albero di ricerca in cui ogni livello è una categoria funzionerebbe. Se l'applicazione ha solo elementi specifici e un elemento "qualsiasi" generale, ciò funzionerebbe correttamente. Se ci sono più livelli di generalità ("mammifero", "vertebrato", "animale") diventa più difficile.

Se la velocità è un problema, ma l'utilizzo della memoria non lo è, si potrebbe anche provare l'approccio di hashtables-of-hashtables. Ogni voce in una tabella hash è una coppia valore-chiave. Nella hashtable di livello superiore, la chiave è la categoria superiore: "dog", "cat", "any". Il valore è un altro hashtable. Nel hashtable di secondo livello, la chiave è il colore e il valore è un altro hashtable. E così via. Il valore della tabella hash più profonda contiene un puntatore, una chiusura o qualsiasi altro metodo di chiamata dinamica offerto dai linguaggi di programmazione.

Answer 4

Vorrei innanzitutto assegnare a tutte le variabili un valore univoco (posizione dell'array)

Animale: qualsiasi = 0; cat = 1; dog = 2
Genere: any = 0; maschio = 1; femmina = 2
Colore: qualsiasi = 0; bianco = 1; nero = 2; grigio = 3;

Quindi vorrei assegnare a ciascuna combinazione possibile un valore di ricerca.

   Animal-|  ANY  |  cat   |  dog   |  
        ------------------------------------------------------------- 
      Gender-| any | male |female| any | male |female| any | male |female| 
        ============================================================= 
     Color-any  | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 
        ------------------------------------------------------------- 
      white | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 
        ------------------------------------------------------------- 
      black | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 
        ------------------------------------------------------------- 
      gray | 27 | 28 | 29 | 30 | 32 | 33 | 34 | 35 | 36 | 
        ============================================================= 

Ciascun valore di ricerca può essere calcolata con la seguente:

(Animal * number of animals) + Gender + (Color * number of animals * number of sexes) 

o in caso di: animale è qualsiasi, (0) colore grigio, (3) genere è maschio , (1)

(Animal * number of animals) + Sex + (Color * number of animals * number of sexes) 
( 0 *  3  ) + 1 + ( 3 *  3   *  3  ) 

(0 * 3) + 1 + (3 * 3 * 3) 
    0 + 1 +  27  = 28 (the lookup value from the grid above) 

28 significa chiamata X.

Quindi nel tuo programma:

Calcolare apprezzi Confrontare tale valore contro casi noti

if Value in (1,2,8,13,14,15,21,28) then X 
if value in (3,4,5,23,24,26,34,35,36) then Y 
if value in (0,9,12,16,17,22,25)  then Z 

Ovviamente quelli valore potrebbe effettivamente essere memorizzato in un file di configurazione in modo da potreste cambiare la logica, senza un re-compilazione.

Answer 5

Si può quasi tradurre direttamente questo in codice Scala.

idiomaticamente, si userebbe animale, gatto, cane - con lettere maiuscole in scala, ma per abbinare il vostro esempio, lascio la strada della convenzione qui:

abstract sealed class animal() {} 
object cat extends animal() {} 
object dog extends animal {} 

abstract sealed class color() {} 
object white extends color {} 
object black extends color {} 
object gray extends color {} 

abstract sealed case class gender() {} 
object male extends gender {} 
object female extends gender {} 

def input (a: Option[animal], c: Option[color], g: Option[gender]) = (a, c, g) match { 
    case (Some (dog), Some (gray), Some (male)) => println ("y called without freedom") 
    case (_,   Some (gray), Some (male)) => println ("x called with animal" + a) 
    case (_,   _,   _   ) => println ("z called with anmimal: " + a + "\tcolor: " + c + "\tgender: " + g) 
} 

input (Some (dog), Some (gray), Some (male)) 
input (None,  Some (gray), Some (female)) 

Risultato:

y called without freedom 
x called with animal: None 

Devi fare attenzione allo smistamento nel metodo "input". I metodi specifici devono venire prima di quelli non specifici.

e ci sono alcuni casi in cui, dalla tua descrizione ricevute non è cosa fare, ma si deve decidere, quale test viene prima:

(a, c, _) 
(_, c, g) 
(a, _, g) 

hanno tutti 1 caso aperto. Se non c'è nient'altro, (a, c, g) potrebbe corrispondere a nessuno di essi, ma corrisponderà solo al primo.

È necessario fornire un caso generale (_, _, _), ma può generare un errore, se non ha senso.