Извращенная проблема палача

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

Жадный алгоритм построения дерева решений выглядит следующим образом: - для каждого предположения выберите предположение, ответ на которое является «истинным», а ответ - «ложным», как можно ближе к 50-50, поскольку теоретически это дает больше всего информации.

Пусть N - размер набора, A - размер алфавита, а L - количество букв в слове.

Итак, поместите все свои слова в набор. Для каждой позиции буквы и для каждой буквы в вашем алфавите посчитайте, сколько слов имеет эту букву в этой позиции (это можно оптимизировать с помощью дополнительной хеш-таблицы). Выберите счетчик, который по размеру ближе всего к половине набора. Это O (L * A).

Разделите набор пополам, взяв подмножество, которое имеет эту букву в этой позиции, и сделайте эти две ветви к дереву. Повторите для каждого подмножества, пока не получите все дерево. В худшем случае это потребует O (N) шагов,