Добрый день!

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

1. Есть список из ~80 изданий (газет) с указанием городов, в которых они выходят, и стоимости рекламных блоков в них (как правило каждое издание выходит в 2-10 городах)
2. Есть список целевых городов (около 40), в которых необходимо обязательно подать рекламу

Нужно найти варианты выборки изданий, покрывающих ВСЕ целевые города, упорядоченные по совокупной стоимости подачи рекламы.

Здравствуйте, Zlobnyi Serg, Вы писали:

ZS>Добрый день!

ZS>Жена принесла с работы интересную задачу, для которой я не могу придумать быстрого эффективного решения. Помогите нам, пожалуйста:
ZS>Нужно найти варианты выборки изданий, покрывающих ВСЕ целевые города, упорядоченные по совокупной стоимости подачи рекламы.

Думаю, что одновременно точного и эффективного решения нет.
Вот что пришло в голову. Может что-то поможет:

Вариант 1. Точное решение, но не эффективное

а) определяем максимальную возможную стоимость рекламной компании (т.е. если все издания используем)
б) для каждого X из отрезка [0,максимальной стоимости] подбираем комплект изданий в сумме дающие по стоимости X
в) если комплект изданий покрыл все целевые города, то выводим решение. Если нет двигаемся дальше

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

Вариант 2. Метод Монте-карло — не точное и быстрое.

а) Для каждого издания вводим некую характеристику "качества". Например (стоимость/количество городов).
б) Случайным образом выбираем издание для использования (издание с лучшим качеством выбираются чаше)
в) Повторяем п."б" пока не будут покрыты все целевые города. Фиксируем результат
г) После некоторого количества (несколько миллионов и больше) повторов (а лучше даже в режиме реального времени) выводим лучшие N решений

Еще можно использовать Генетические алгоритмы — для таких задач очень хорошо подходят. И вроде нетрудно придумать операции мутации и скрещивания.
Должно получиться более точно, чем вариант 2. И также быстро.

Здравствуйте, Zlobnyi Serg, Вы писали:

ZS>Нужно найти варианты выборки изданий, покрывающих ВСЕ целевые города, упорядоченные по совокупной стоимости подачи рекламы.
Задача о покрытии множества. NP-полная.
Так что или приближенно, или терпеливо перебирать

Точнее, обобщение задачи о покрытии множества.

Здравствуйте, Zlobnyi Serg, Вы писали:

ZS>Добрый день!
ZS>Жена принесла с работы интересную задачу, для которой я не могу придумать быстрого эффективного решения. Помогите нам, пожалуйста:
ZS>1. Есть список из ~80 изданий (газет) с указанием городов, в которых они выходят, и стоимости рекламных блоков в них (как правило каждое издание выходит в 2-10 городах)
ZS>2. Есть список целевых городов (около 40), в которых необходимо обязательно подать рекламу
ZS>Нужно найти варианты выборки изданий, покрывающих ВСЕ целевые города, упорядоченные по совокупной стоимости подачи рекламы.

Это похоже на задачу о минимальном покрытии множества. Есть множество (40 городов), есть список его подмножеств (80 изданий с указанием городов), есть "вес" каждого подмножества (стоимость), требуется найти совокупность подмножеств (изданий), объединение которых покрывало бы все множество (реклама во всех 40 городах), а суммарный вес (стоимость) был бы минимальным.

Похоже, но не совсем, т.к. вам требуется, видимо, несколько вариантов, упорядоченных по стоимости, а не только самый оптимальный. В любом случае, искать по ключевым словам "задача о покрытии множества", ну и т.к. задача NP-полная, то не бояться применять методы "в лоб", тем более при таких небольших числах (80 изданий, 40 городов).

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

Здравствуйте, vadimcher, Вы писали:

V>Кстати, возможно, что для практической применимости в вашем (с женой) случае задача сформулирована не совсем корректно. Стоимость размещения рекламы в том или ином издании может оказаться скоррелированной с количеством читателей, а потому оптимальный алгоритм может отобрать 40 мелких изданий, которые никто не читает, но зато и реклама там почти бесплатная, вместо пары крупных газет, которые возьмут чуть больше, но и читателей у них на три порядка больше.

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