Деревья решений – мощный инструмент интеллектуального анализа данных, оказывающийся полезным при решении многих задач, в том числе, задач диагностики. Задача минимизации средней стоимости диагностики NP-трудна, поэтому для ее решения в литературе предлагаются эвристические алгоритмы. Мы сравнивали предложенный в [2] алгоритм как с предложенными нами его модификациями, так и с классическими алгоритмами. Численные эксперименты на стандартных наборах данных показали, что алгоритм [2] строит лучшие деревья, чем известные эвристики (в частности, EG2), но предложенные нами модификации, сочетающие комбинаторную нижнюю оценку с классическими эвристиками, превосходят его как по скорости работы, так и по качеству деревьев.