Самый быстрый алгоритм поиска не более (n / 2) -1 лжецов в n человек

Question

Вот мой сценарий:

Эта проблема сформулирована с точки зрения лжецов и рассказчиков правды, но она имеет реальные приложения для определения, какие компоненты сложной системы хороши (функционируют правильно), а какие - неисправны.Предположим, у нас есть сообщество из n человек, и мы знаем целое число t

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

Мы будем идентифицировать лжецов в сообществе, последовательно выбирая пары людей, (X, Y) скажем, и спросим Х: Является ли Y лжецом ?.Ответ: «да» или «нет»;

Какой оптимальный алгоритм (минимальное количество шагов) для поиска всех лжецов?

Answer 1

Случайный алгоритм с оптимальным ожидаемым временем выполнения O (n) и отличными константами:

1. Выбор случайного человека
2. Спросите остальных, является ли он лжецом,пока один из вариантов («да» или «нет») не будет иметь вес> n / 2 (т. е. до тех пор, пока более n / 2 человек не ответили одинаково).
   Большинство принимает решение (это ключевое наблюдение!).
3. Если он не лжец, переберите оставшихся людей и спросите только его , является ли каждый человек лжецом (поскольку мы определили, что он говорит правду).
4. Если он лжец, выведите его из группы и вернитесь к 1.

Ключевое наблюдение состоит в том, что если мы спросим всех об одном человеке, мнение большинства должно быть правильным(так как есть большинство рассказчиков правды).Небольшая техническая составляющая: если мы сначала выберем не-лжеца и спросим всех остальных, если предположим, что все лжецы лгут, мы достигнем 50-50, так как мы решим, какая сторона говорит правду?Это не проблема, так как мы можем достичь 50-50, только если выберем не-лжеца, поэтому наш человек действительно рассказчик правды.

Ожидаемое числолюди, которых нам придется выбирать случайным образом, - это O (1) (это самая важная часть этого вопроса, и поскольку это может быть домашнее задание, я пропущу доказательство, но намекну на простое доказательство: геометрическое распределение), что означает, что мынайдем наш правдивый и надежный источник за O (1) * O (n) раз, а оттуда еще один O (n) до финиша.Всего O (n).

Answer 2

Хорошей статьей на эту тему является «Проблема византийских генералов» Лесли Лампорта, доступная по адресу http://research.microsoft.com/en-us/um/people/lamport/pubs/byz.pdf

Не прямое решение, но хорошее справочное чтение для заинтересованных.

Answer 3

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

Пусть G будет группой интересов. Выберите произвольного члена группы, X скажем. Заметьте, что процедура запроса X "является ли Y лжецом?" выдает ответ «нет», если X и Y оба являются рассказчиками правды или оба являются лжецами, и ответ «да» в противном случае. Таким образом, спрашивая X "является ли Y лжецом?" для каждого Y в G (исключая X) вы можете узнать, какие члены Y входят в ту же «команду», что и X. Из того факта, что должно быть больше рассказчиков правды, чем лжецов, это позволяет вам определить, в какую «команду» входит X, после чего просто определить лжецов.

Answer 4

Псевдокод для моего решения, который в основном совпадает с решением Дэвина.Одно заметное отличие состоит в том, что вам нужен только консенсус максимально возможных оставшихся лжецов + 1.

set unknown = all
set known_true = {}
set known_lie = {}

while known_true.is_empty()
  voted_lie = {}
  voted_true = {}
  truth_votes = 0
  lie_votes = 0
  to_check = unknown.get(0)
  while truth_votes < t - known_lie.size() + 1 && lie_votes < t - known_lie.size() + 1:
    checker = unknown.get_next()
    if checker.is_liar(to_check):
      lie_votes++
      voted_lie.add(checker)
    else
      truth_votes++
      voted_true.add(checker)

  if truth_votes > t + 1:
    unknown.remove(to_check)
    known_true.add(to_check)
    known_lie.add_all(voted_lie)
    unknown.remove_all(voted_lie)
  else:
    unknown.remove(to_check)
    known_lie.add(to_check)
    known_lie.add_all(voted_true)
    unknown.remove_all(voted_true)


while not unknown.is_empty() && known_liar.size() < t:
  to_check = unknown.get(0)
  if known_true.get(0).is_liar(to_check):
    unknown.remove(to_check)
    known_lie.add(to_check)
  else
    unknown.remove(to_check)
    known_true.add(to_check)

Answer 5

Если вы запрашиваете все пары, то рассказчики правды отображаются как уникальная максимальная клика размера> n / 2. Я оставлю это на те удобные испорченные домашние вопросы, чтобы оптимизировать.