правила, соответствующие данному входной (алгоритм)

Question

Давайте предположим, что у меня есть следующие категории (с их возможными значениями):

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

или в более общем ...

category: <array of values> 

(1) Допустим, У меня есть набор настраиваемых правил:

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) И некоторые входные значения.

Q. Существует ли алгоритм, который решает проблему поиска правильности сопоставления (с приоритетом, заданным для определенного конкретного правила) в соответствии с введенным вводом?

Ex.1:

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

было бы назвать "у"

Ex.2:

input (color:gray, gender:female) 

было бы назвать "г"

ли более подходящим способ сделать это - построить дерево поиска на основе правил (каждый уровень дерева является категорией)?

нравится:

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

Есть ли лучший способ сделать это?

Спасибо!

Answer 1

Решение дерева со следующими изменениями будет работать:

1. Создание дерева принятия решений в обычном порядке с «любой», как края, используя все правила

2. Хотя обходе рекурсивно, траверс как «значение» и «любые» и следить за количество «любой в рамках каждого решения, вернуть один с минимальным» любое это

   защиту траверс (значения, уровнем, деревом, AnyCount): Если дерево является листом: возвращения (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

Я бы сделал правила на карте, а затем посмотрел на один и тот же хэш.

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

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

Это обеспечит более быстрое создание правил и разрешение правильной функции для вызова на основе ввода.

Если правило должно быть согласовано точно или иначе попадают в общий любом, любой, любой, то это просто делается:

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

В противном случае, если она начинается с вводом и последовательно выбирает любое правило на каждый параметр, вы могли бы это сделать.

Имейте хеш-функцию, принимающую массив значений. Когда вы пытаетесь соответствовать правилу, вы начинаете с ввода, а затем последовательно переключаете каждый на любой, пока не найдете совпадение.

def key hash(array[]) 

....

процесс разрешения ...

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

Правильный ответ зависит от того, как фантазии вы хотите получить. Есть такие вещи, как Rete algorithm. Google «экспертные системы». Я работал в крупных корпорациях, которые имеют системы оценки правил, но они не пишут их в доме - они покупают коммерческий пакет.

Если ваши потребности просты, тогда будет работать дерево поиска, в котором каждый уровень будет категорией. Если приложение имеет только определенные элементы и один общий «любой» элемент, это будет работать нормально. Если существует несколько уровней общности («млекопитающее», «позвоночный», «животное»), он становится более жестким.

Если скорость является проблемой, но использование памяти не является, вы можете также попробовать подход hashtables-of-hashtables. Каждая запись в хэш-таблице представляет собой пару ключевых значений. В хэш-таблице верхнего уровня ключевым является верхняя категория: «собака», «кошка», «любая». Значение - это еще одна хеш-таблица. На хэш-таблице второго уровня ключевым является цвет, а значение - другая хеш-таблица. И так далее. Значение самой глубокой хэш-таблицы содержит указатель на функцию, закрытие или любой другой способ динамического вызова, предлагаемый вашими языками программирования.

Answer 4

Я бы сразу дал всем переменным уникальное значение (положение массива)

Animal: any = 0; cat = 1; dog = 2
Пол: any = 0; male = 1; female = 2
Цвет: any = 0; белый = 1; черный = 2; серый = 3;

Тогда я даю каждому возможному сочетанию значение поиска.

   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 | 
        ============================================================= 

Каждое значение поиска может быть вычислено следующим образом:

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

или в случае: животного является любым, (0) цвета серый, (3) пола мужского пола , (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 означает вызов X.

Так что в вашей программе:

Calculate вы дорожите Сравните это значение от известных случаев

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 

Очевидно, такая величина может быть фактически хранится в конфигурационном файле, чтобы вы могли изменить логику без повторной компиляции.

Answer 5

Вы можете почти сразу перевести это на лестницу код.

идиоматически, вы будете использовать для животных, кошки, собаки - с прописными буквами в Скале, но, чтобы соответствовать вашему примеру, я оставляю дорогу условности здесь:

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)) 

Результат:

y called without freedom 
x called with animal: None 

Вы должны позаботиться о сортировке в методе ввода. Конкретные методы должны поступать до неспецифических.

И есть некоторые случаи, когда, из вашего описания это не является критерием, что делать, но вы должны решить, какой тест приходит первым:

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

сделать все есть 1 открытого случай. Если ничего больше, (a, c, g) может соответствовать любому из них, но будет соответствовать только одному.

Вы должны предоставить общий регистр (_, _, _), но можете выбросить ошибку, если это не имеет смысла.