Какой класс алгоритмов может быть использован для решения этой проблемы?

Question

РЕДАКТИРОВАТЬ: Просто чтобы убедиться, что кто-то не ломает голову над проблемой ... Я не ищу лучший оптимальный алгоритм. Эвристика, которая имеет смысл, в порядке.

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

Введите:

• N человек
• k объявлений, которые я могу сделать
• Расстояние, на котором мой голос может быть услышан (скажем, 5 метров), т. Е. Я могу решить объявить или нет, в зависимости от количества людей в этих 5 метрах

Цель:

• Максимизируйте общее количество людей, которые услышали мои k объявлений и (опционально) минимизируйте время, за которое я смогу закончить объявление всех k объявлений

Ограничения:

• Как только человек услышит мое объявление, он будет удален из общего числа, т. Е. Если он услышал мое первое объявление, я не буду считать его, даже если он услышит мое второе объявление
• Я могу видеть одного и того же человека и множество людей в моей близости

Пример: Давайте рассмотрим 10 человек с номерами от 1 до 10 и следующую схему прибытия:

• Временной интервал 1: 1 (выплата = 1)
• Временной интервал 2: 2 3 4 5 (выплата = 4)
• Временной интервал 3: 5 6 7 8 (выплата = 4, если во временном интервале 2 не было объявлено ранее, 3, если объявление было сделано во временном интервале 2)
• Временной интервал 4: 9 10 (выплата = 2)

и мне дают 2 объявления. Теперь, если бы я был оракулом, я бы выбрал временные интервалы 2 и временные интервалы 3, потому что тогда бы 7 человек услышали (потому что 5 уже слышали мое объявление во временном интервале 2, я его больше не считаю). Я ищу онлайн-алгоритм, который поможет мне принять решение о том, делать или не делать объявление, и если да, основываясь на каких факторах. У кого-нибудь есть идеи о том, какие алгоритмы можно использовать для решения этой или более простой версии этой проблемы?

Answer 1

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

Answer 2

Давайте начнем пытаться решить простейший из возможных вариантов проблемы: предположим, N человек и K временных интервалов, но только одно возможное объявление.Предположим также, что каждый человек когда-либо останется только на один временной интервал, и что у каждого человека, который еще не появился, есть одинаково вероятный шанс появления на любом будущем временном интервале.

Учитывая эти упрощения, на каждом временном интервалевы смотрите на отдачу от объявления в текущем временном интервале и сравниваете со шансом того, что у будущего временного интервала будет более высокая выплата, например, давайте предположим, что 4 человека имеют 3 временных интервала:

Таймслот 1: появляется человек 1, поэтому выЯ знаю, что вы можете получить выплату 1, объявив, но тогда у вас есть 3 человека, которые появятся в 2 оставшихся таймслотах, так что по крайней мере один из этих интервалов гарантированно будет иметь 2 человек, поэтому не объявляйте ..

Таким образом, в каждом временном интервале вы можете рассчитать вероятность того, что более поздний временной интервал будет иметь более высокую выплату, чем текущий, рассматривая оставшихся (N) людей и (K) временных интервалов как N независимых случайных чисел каждое из 1..k,и рассчитать вероятность того, что по меньшей мере одно значение k будет больше или равно текущему выигрышу tiтез.(Аналогично проблеме дня рождения, но для более чем одного столкновения), а затем вам нужно решить, сколько скидок, исходя из ожидаемых отклонений.(птица в руке и т. д.)

Обобщение этого решения исходной задачи оставлено в качестве упражнения для читателя.

Answer 3

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

Кажется, что в основном вы пытаетесь достичь максимального количества людейровно 2 объявления.Но, не зная заранее никакой информации о группах людей, вы не сможете принять разумного решения о том, стоит ли использовать ваше первое объявление или нет.Ваш второй, по крайней мере, имеет то преимущество, что знает, когда его не следует использовать (т. Е. Если в группе нет новых членов, вы можете знать, что объявление не стоит тратить впустую).Но в основном это та же проблема.

Единственный реальный способ решить эту проблему - использовать знания о типе данных или желаемом результате для составления догадок.Если вы знаете, что в среднем по группам 100 человек со стандартным отклонением 10, вы можете просто отказаться объявлять, если присутствует менее 90 человек.Или, если вы знаете, что вам нужно набрать не менее 100 человек с двумя объявлениями, вы можете выбрать не объявлять менее 50 одновременно.Очевидно, что эти подходы рискуют вообще никогда не объявлять, если фактические данные не соответствуют ожидаемым.Но это всегда будет риском, так как вы можете получить 1 человека в первой группе, а затем 0 во всех остальных, независимо от того, что вы делаете.

Или вы можете попытаться более четко определить проблемуМне трудно понять, как это соотнести с компьютерами.