Определение того, какой метод лучше всего подходит для сравнительного алгоритма сортировки. Проблема «Разделяй и властвуй» или «Найм» для небольшого сбора данных

Question

Вот вопрос, с которым я сталкиваюсь

У нас есть 25 уникальных материалов, принадлежащих к классу, и мы хотели бы определить топ-3 из этих 25 материалов с точки зрения их эффективности.

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

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

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

Можете ли вы разработать стратегию, которая позволит определить 3 наиболее эффективных материала среди 25 материалов, выполнив минимальное количество экспериментов? Какое минимальное количество экспериментов необходимо для окончательного определения 3 наиболее эффективных материалов?

Вам не нужно писать псевдокод; Достаточно словесного объяснения, возможно, подкрепленного графикой.

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

Меня интересует, как профессионал подойдет к этому типу проблемы.

Answer 1

Вот подход для 7 экспериментов.

Выполните 5 групп из 5. Для этого требуется 5 экспериментов.

Сравните верхнюю часть каждой группы. Теперь у нас есть такой порядок, где каждая строка и столбец убывают.

1a 2a 3a 4a 5a
1b 2b 3b 4b 5b
1c 2c 3c 4c 5c
1d 2d 3d 4d 5d
1e 2e 3e 4e 5e

Лучший элемент - 1a. Сравните 1b 1c 2a 2b 3a, и вы найдете следующие два лучших элемента.

У меня нет доказательств того, что вы не можете сделать это с 6. Но я уверен, что это правда.