Generate a decision tree given a set of rules

in the last few days I've been thinking about this problem without finding an optimal solution, hence this question.

Let's say we have a set of N variables, which a user can compose to create a list of rules and the following action, such as:

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"

Variables won't necessarly be integers, and suppose that the rules are all composed by a list of AND clauses followed b开发者_如何学编程y an action.

What i want to do is to build a decision tree that would allow me to fast process an input like (0,7,9) and return the proper action. As of now, my only idea is to partition the variable space and the see where the input state fits, but it seems a slow soluition : anybody knows something that may be faster?

---

What makes it slow? Lot of rules? Long rules? Lot of variables? Slow rules processing?

If you have not to many variables rules, I would clearly go for a hash table.

This is an example of tree (not necessarily optimal) for the problem you stated.

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