Алгоритм: есть ли хороший способ решения сравнения?

Question

У меня есть набор чисел для сравнения. Допустим, я должен получить это сравнение от пользователя. У меня есть выбор: задать ему вопрос, состоящий из 2 цифр или 3 цифр из 4 цифр. Например, я могу задать любой из следующих вопросов:

• Какое из чисел больше? 2 ИЛИ 4
• Какое из чисел больше? 2 ИЛИ 3 ИЛИ 4
• Какое из чисел больше? 2 ИЛИ 3 ИЛИ 4 ИЛИ 5

Моя цель - минимизировать количество вопросов, которые я задаю пользователю, в некоторой комбинации, которая в конечном итоге даст мне порядок всех чисел в наборе ... Например, если было только 4 числа {2,3, 4,5}, я мог бы задать ему третий тип вопросов, где я даю ему 4 цифры для сравнения. Но в экосистеме, для которой я проектирую это, пользователя раздражают длинные вопросы, поэтому я хотел бы свести к минимуму количество вопросов такого типа, которые я бы задавал. Поэтому, если каждый из вопросов имеет определенный вес, я пытаюсь найти способ в конечном итоге получить порядок всех чисел, но в то же время поставить пользователя с минимальными трудностями.

Есть ли хороший способ решения этой проблемы? Кто-нибудь видит это как принадлежащий к общему классу проблем, или я просто делаю это слишком сложным? Есть предложения?

Answer 1

Давайте поэкспериментируем, не так ли?

1. Пример

Давайте посмотрим на {A,B,C,D} и отсортируем его.

Решение 1: По сетам

• Больше {A,B,C,D} -> B (при этом B>A, B>C и B>D)
• Большой {A,C,D} -> D (при этом D>A и D>C)
• Большой {A,C} -> A (при этом A>C)

Общая сумма заказа [B,D,A,C]

Решение 2: парами

• Больше от A до C -> A (при этом A>C)
• Больше от B до D -> B (таким образом B>D)
• Больше от D до A -> D

Общий заказ [B,D,A,C]

В чем подвох? Очевидно, что это сложнее по парам, здесь я выбрал их так, чтобы слияние было легко (нет).

2. Примечания

a) Общая сумма заказа

> хорошо работает только с полным порядком: т.е. для двух заданных элементов A и B из набора A>B или B>A. Если ни одно из этих двух отношений не выполняется, то A и B эквивалентны.

Проблема с подходом Solution 1 заключается в том, что если вы предоставляете пользователю {A,B,C,D} и A и B, эквивалентны и больше, чем C и D ... какой ответ должен быть?

б) Транзитивность

Отношение > является транзитивным, что означает, что если A>B и B>C, то A>C. Важно использовать этот факт, поскольку вы можете выводить отношения между двумя элементами, даже не спрашивая пользователя.

в) Какова цель?

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

3. Моделирование

Можно смоделировать проблему как проблему «графика».

Вы начинаете с набора узлов {A,B,C,D}, которые представляют значения, которые вы хотите проверить.

Сортировка набора эквивалентна вычислению минимального набора ориентированных ребер, которые связывают эти узлы, так что при любых двух узлах путь ведет от одного к другому. Я настаиваю на минимуме.

Например, если у меня есть 2 ребра: B>A и B>C, тогда, если я обнаружу, что A>C, я удалю B>C, потому что могу вывести его транзитивностью. Важным свойством является то, что если нет двух узлов, эквивалентных, то кардинал результирующего набора ребер является кардиналом множества узлов минус 1. В моем примере (с учетом 4 узлов) это будет 3.

Оракул (или чрезвычайно удачливый парень), таким образом, сможет задать только 3 вопроса, и все же построить этот график ... это то, к чему мы должны стремиться.

4. Как решить эту проблему?

Хорошо, давайте предположим, что у нас нет 2 эквивалентных элементов. Это означает, что если A>B ложно, то я могу сделать вывод, что B>A ...

Для представления нашего маленького графа возьмем массив:

  A B C D  
D . > .      # . represent the unknown
C . >        
B >          # < and > have their usual meaning...
A 

Из-за симметрии нам нужен только треугольник.

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

Следовательно, хороший вопрос - это удалить как можно больше . одним махом.

5. Мой вопрос

И, таким образом, у меня есть другой тип вопроса:

Select the elements lower than "D" in the following {A,B,C}: _

Этот вопрос чувствует себя лучше, чем Что больше ... , потому что я явно нацеливаюсь на те отношения, которые я хочу знать (D?A, D?B и D?C), тогда как БОЛЬШЕ гарантирует, что я получу столько же отношений, но заранее не знаю, какие именно.

Я пытаюсь максимально использовать вопрос

Конечно, для лени нет смысла: все же важно учитывать транзитивность при использовании результатов вопросов.

6. Изучение больших наборов

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

Учитывая 2 упорядоченных (непересекающихся) набора: [A,B,C,D,...] и [R,S,T,U,...], давайте посмотрим на 3 вопроса панели инструментов:

1. Что больше: A или R? _
2. Какой самый большой элемент {A,B,R,S}? _

3. Какие элементы больше A в {R,S,T}? _

4. Дает 1 отношение

5. Дает 2 отношения: 3 из которых 1 уже известна
6. Дает 3 отношения

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

7. Заключение

Теперь у вас в коробке 4 вопроса:

• Сортировка : сортировать следующие элементы по возрастанию {A, B, C, D}? _
• Pivot : Какие элементы больше, чем A в этом наборе {B, C, D}? _
• Greater : Какой элемент больше в этом наборе {A, B, C, D}? _
• Пара : Какой элемент больше среди А и В? _

( Пара может рассматриваться как вырожденный случай: Большой или Сводный )

Учитывая, что каждый вопрос дает n-1 отношения для n узлов, вы можете попытаться измерить, сколько времени требуется пользователю, чтобы ответить на вопрос T(n), а затем найти n, который максимизирует T(n)/n ;)

Answer 2

Если вы сортируете массив, тогда вы обычно сортируете за O (n log (n)) время. Это означает, что вы иногда сравниваете пары чисел более одного раза. Если вы постоянно задаете 4 вопроса, вы получаете дополнительную информацию, которую можете хранить.

Когда вы попадаете в точку, в которой вы спрашиваете a> b, тогда вы можете также задать самый большой из {b, c, d, e, ...}. Таким образом, вам никогда не придется спрашивать a> c, a> d и т. Д. Если вы сохраняете эти известные сравнения в таблице, вам никогда не придется делать их снова. Что касается выбора именно того, что задает caparison, чтобы спросить пользователя, я не уверен, и это, безусловно, хороший вопрос.

Моя интуиция о том, какие наборы задать вопрос пользователю, состоит в том, чтобы посмотреть, как работает быстрая сортировка. Он разбивает данные на две части, и числа, которые не входят в одну и ту же группу, никогда не сравниваются, так что вы знаете, что НЕ положить в набор, чтобы спросить пользователя. Используйте 4 числа как можно дольше, пока быстрая сортировка не разбилась на группы, в которых менее 4 чисел.

Answer 3

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

Тогда возникает вопрос: уменьшает ли способность задавать вопрос, который является наибольшим из 3 или 4, количество вопросов, которые вам нужно задать? Моя интуиция говорит «нет», но мне будет трудно доказать это.

Answer 4

Вы можете представить вопросы с помощью алгоритмов быстрой сортировки или mergesort . Минимизируйте количество сравнений и гарантируйте правильный результат.