Существует ли алгоритм поиска предмета, который соответствует определенным свойствам, например, игра с 20 вопросами?

Question

Был задан вопрос о 20 играх с вопросами здесь :

Однако, если я правильно понимаю, ответы, похоже, предполагают, что каждый вопрос будет идти вниз по иерархическому ветвящемуся дереву. Бинарное дерево должно работать, если игра шла так:

1. Это животное? Да.
2. Это млекопитающее? Да.
3. Это кошачий? Да.

Потому что кошачий является примером млекопитающего, а млекопитающее - примером животного. Но что, если вопросы пойдут так?

1. Это млекопитающее? Да.
2. Это хищник? Да.
3. У него длинный нос? Нет.

Вы не можете разветвляться на дерево с такими вопросами, потому что есть много хищников, которые не являются млекопитающими. Таким образом, ваша программа не может быть сужена до млекопитающих, а хищники могут быть подмножеством млекопитающих.

Так есть ли способ использовать двоичное дерево поиска, которое я не понимаю, или есть другой алгоритм для этой проблемы?

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

Answer 1

Это похоже на бинарный поиск в том смысле, что каждый вопрос да / нет, и поэтому каждый ответ разбивает ваш оставшийся набор на две части. Однако набор данных, скорее всего, , а не будет храниться в реальном двоичном дереве, потому что, как вы понимаете, это будет работать, только если вопросы всегда задавались в том же порядке, что и измерение с разделением дерева.

Кроме того, вы могли бы легко иметь более чем точно 20 измерений («свойств»), по которым можно разделить вещи, и некоторый набор из этих двадцати мог бы использоваться более чем одним объектом (так что конечный узел двоичного файла с 20 уровнями) дерево не обязательно будет содержать только один элемент).

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

Answer 2

Я считаю, что то, что вы ищете, чаще всего называют Дерево решений , специально для классификации. Затем вы можете использовать алгоритмы, такие как C4.5 , чтобы узнать, как упорядочить ваши вопросы для эффективной классификации.

Answer 3

Если вы ищете точное соответствие - просто хешируйте все свойства и ищите.

Если вы хотите выполнить распознавание образов, чтобы найти похожие элементы, вы можете использовать метод с довольно «линейным» отображением, например k-ближайший сосед. Например, вы можете использовать kd-дерево для представления пространства поиска.

Answer 4

Если вам нужно придерживаться бинарного дерева для решения проблемы, ничто не говорит о том, что вы не можете дублировать ветку или узел. Поместите узел ответа кошачьих в конце более чем одного набора решений. Или задайте вопрос хищнику дважды - один раз, если пользователь сказал «да» млекопитающему, и один раз, если пользователь сказал «нет».

Конечно, есть проблемы оптимизации и эффективности, если вы пойдете по этому пути, но есть и способы решения конкретных проблем. (Например, если вас беспокоит объем памяти для дерева решений, сделайте ветви или узлы или оба указателя на неизменяемые объекты / объявления).