Сортировка массива на основе бинарных сравнений при минимизации непереходных испытаний

Question

У меня есть список из 15 городов. Я случайно рисую 70 пар из возможных 15*14/2=105 пар городов. Для каждой из 70 пар я прошу своих участников решить, больше ли город А, чем город В. Важно то, что иногда участники делают "ошибки" и дают ответ, который не совместим с их предыдущими ответами. (то есть нарушает транзитивность).

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

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

Как я мог сделать это, кроме как с помощью исчерпывающего поиска?

РЕДАКТИРОВАТЬ: В качестве примера возьмем города A,B,C,D и E. Участник Джон Доу считает, что правильный порядок городов (от самых маленьких до самых больших) - ABCDE. Мне все равно, прав он на самом деле или нет, мне просто важно, насколько хорошо его ответы, перечисленные ниже, соответствуют его вере.

В трех независимых исследованиях Джон ответил следующее:

испытание 1: A

испытание 2: B

испытание 3: C

проба 4: D

проба 5: E > B (*)

Таким образом, ответ в испытании 5 (*) несовместим с ответами в испытаниях 2 и 4 вместе. Либо одно испытание (номер 5) не соответствовало убеждениям Джона, либо 2 испытания (2 и 4) не соответствовали. Мне не важно выяснить, в чем заключался убеждение Джона (ABCDE), мне просто нужно знать, что "минимальное количество непереходных ответов" для Джона Доу равно 1.

Answer 1

Итак... проблема может быть интересной, но не совсем понятно, что вы хотите. Вам нужно отсортировать города, но вам не нужен их заказ?

Минимизируйте количество испытаний, которые нарушают транзитивность... как вы это делаете? Неприкосновенность заключается в ответах, которые вы получаете, а не в том, что вы делаете с ними.

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

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

Надеюсь это поможет.