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

Question

вопрос о 20 вопросах игра была задана here:

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

1. Является ли это животным? Да.
2. Это млекопитающее? Да.
3. Это кошка? Да.

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

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

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

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

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

Answer 1

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

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

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

Answer 2

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

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

Answer 3

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

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

Answer 4

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