Генерация дерева решений с учетом набора правил - PullRequest
Новая
       6

Генерация дерева решений с учетом набора правил

3 голосов
/ 13 июля 2011

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

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

variables V_1,V_2,V_3
V_1 > 5 -> "Turn left"
V_2 < 6 -> "Turn right"
1 < V_1 < 4 -> "Continue straight"
V_1 = 0 AND V_2 > 6 AND V3 > 5 -> "Go backwards"
default -> "Stay"

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

То, что я хочу сделать, - это построить дерево решений, которое позволило бы мне быстро обработать ввод (0,7,9) и вернуть правильное действие. На данный момент моя единственная идея состоит в том, чтобы разделить пространство переменных и посмотреть, куда подходит состояние ввода, но это кажется медленным решением: кто-нибудь знает что-то, что может быть быстрее?

1 Ответ

0 голосов
/ 13 июля 2011

Что замедляет?Много правил?Длинные правила?Много переменных?Медленная обработка правил?

Если у вас не так много переменных правил , я бы явно выбрал хеш-таблицу.

Это примердерева (не обязательно оптимального) для поставленной вами задачи. 

variables V_1,V_2,V_3
V_1 > 5 -> "Turn left"
V_2 < 6 -> "Turn right"
1 < V_1 < 4 -> "Continue straight"
V_1 = 0 AND V_2 > 6 AND V3 > 5 -> "Go backwards"
default -> "Stay"

   V1         V2      V3
   <0 ------- <6 --------------- Right
              >=6 -------------- Stay

   0 -------- <6 --------------- Right
               6 --------------- Stay
              >6 ---- <=5 ------ Stay
                      >5 ------- Backwards

   ]0-1] ---- <6 --------------- Right
              >=6 -------------- Stay

   ]1-4[ ----------------------- Straight

   [4-5] ---- <6 --------------- Right
              >=6 -------------- Stay

   >5 ------- <6 --------------- Right
              >=6 -------------- Stay
...