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