Интересная теоретическая задача теории графов
Недавно мой отец познакомил меня с трудной проблемой, которую он пытается решить. Исходная проблема возникла при попытке найти оптимальный способ выполнения определенных операций sql. Я перефразирую проблему, чтобы сделать ее более краткой, поскольку меня интересует только теоретический алгоритм, а не конкретная реализация.
Вот мое красочное воссоздание проблемы:
Вам нужно сделать так, чтобы все нравились вам. Вы можете понравиться целевому человеку, подкупив его напрямую или иногда подкупив определенную группу людей, которым вы уже нравитесь, чтобы убедить цель полюбить вас.
Учитывая общее количество людей N и список вариантов подкупа L из K, найдите самый дешевый способ понравиться всем.
Каждый вариант подкупа должен содержать либо
- Два числа, первое число представляет человека, которому вы подкупите, чтобы вы ему понравились, а второе число представляет стоимость взятки.
- Список чисел, обозначающих группу людей, которых можно подкупить, число, обозначающее человека, которого нужно убедить полюбить вас, и последнее число, обозначающее общую стоимость взятки. Чтобы выполнить групповую взятку, вы должны уже сделать каждого человека в этой группе таким же, как вы.
Вот пример: Люди: 3 Параметры:
- 1, 10 (вы можете подкупить человека 1, чтобы он вам понравился, за 10)
- 1, 2, 5 (вы можете подкупить человека 1, чтобы он понравился вам человеку 2, за 5)
- 2, 7 (вы можете подкупить человека 2, чтобы он вам понравился, за 7)
- 1, 2, 3, 3 (вы можете подкупить людей 1 и 2, чтобы сделать человека 3 таким же, как вы, за 3)
В этом примере оптимальное решение — использовать первый, второй и четвертый варианты, чтобы вы нравились всем, за общую стоимость 18.
Можете ли вы помочь мне найти обобщенный алгоритм, который подойдет для любого случая?
Конкретных ограничений по количеству нет, но могу сказать, что количество людей почти всегда будет небольшим (< 10), а количество вариантов подкупа может быть очень большим (N * (2^(N-1)) ).
@nate Можете ли вы поделиться соответствующим вопросом/интерпретацией SQL?
@user24714692 user24714692 Как бы вы использовали раскраску графиков для решения этой проблемы?
@Dave Рассматривайте каждого человека как вершину графа. Каждая взятка как грань, связывающая подкупаемого и дающего взятку. Затем вы можете использовать алгоритмы раскраски графов, чтобы найти минимальную стоимость «чтобы все нравились вам», где каждый цвет представляет группу людей, «которые нравятся друг другу», а стоимость представляет собой общую стоимость их подкупа.
@user24714692 user24714692 Как вы поступаете с взятками группам, как в последнем примере ОП («вы можете подкупить человека 1 и 2, чтобы человек 3 понравился вам, за цену 3)»? Даже если с этим разобраться, как раскрашивание поможет вам решить проблему? Если у вас есть решение, пожалуйста, опубликуйте его.
@Dave Разве мы не можем «раскрасить» человека 1, чтобы он понравился тебе, за цену X? Разве это не проблема раскраски графа? Если вы говорите, что это не так, возможно, это не так. ( ˆ__ )
Стоит отметить, что эта задача является NP-сложной. Доказательство. Возьмем граф G. Пусть стоимость подкупа любого узла будет равна 1, если вы уже подкупили все узлы, имеющие ребра, к этому узлу, и 10 отдельно. Тогда решение этой проблемы позволит решить en.wikipedia.org/wiki/Feedback_vertex_set, чья задача минимизации NP сложна.
Ответы 1
Поскольку n (количество людей) невелико, подход, неэффективный для n, может быть приемлемым.
Давайте подумаем об орграфе вот так. Каждый узел представляет собой состояние, в котором каждый из n человек либо подкуплен, либо не подкуплен. Затем есть 2 ^ n узлов.
Каждый узел получает дугу к каждому узлу, которая непосредственно из него достижима, т. е. состоит из того же набора подкупленных людей, что и рассматриваемый узел, плюс еще один. Вес/стоимость каждой дуги — это самая дешевая стоимость перемещения между узлами.
После того, как веса назначены, остается использовать ваш любимый алгоритм для поиска кратчайшего пути в DAG с (предположительно) неотрицательными весами. https://en.wikipedia.org/wiki/Shortest_path_problem
Так как же нам присвоить эти веса? Вот один из подходов:
Сначала дайте каждому узлу идентификатор, в котором устанавливается i-й бит, если i-й человек подкуплен. Таким образом, узел начального состояния получает идентификатор 0, его дочерние элементы получают идентификаторы с установленным 1 битом и так далее.
Затем свяжите идентификатор, который передается каждой группе, которую можно использовать для взятки, со стоимостью и идентификатором человека, которого нужно подкупить. Поскольку одна группа может быть использована для подкупа нескольких человек, представьте это в виде карты {person_to_bribe => стоимость}.
Затем проанализируйте все узлы в порядке их расстояния от узла 0. Каждая карта узлов создается/обновляется на основе ее предшественников, при этом стоимость каждого узла является минимальной из его карт и карт его предшественников. Как только это будет сделано для глубины i, присвойте соответствующий вес дугам каждого узла глубины i на основе обновленной карты.
Это неэффективно, но поскольку n < 10, все должно быть в порядке.
nodes: 2^n <= 2^9 = 512
arcs: choose(n,0) * choose(n,1) + choose(n,1) + choose(n,2) + ... + choose(n,n-1) * choose(n,n) <= 43,758 (equals this for n=9)
Я думаю, следует явно упомянуть поиск единой стоимости.
@MattTimmermans Я, вероятно, что-то упускаю; почему UCS лучше других вариантов?
Это способ сделать то, что вы написали, не создавая экземпляры всех ребер графа.
Связанный: это чем-то похоже на проблему 5 CCO 2017.