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


Редактировать: просто чтобы убедиться, что кто-то не ломает голову над проблемой... Я не ищу лучшего оптимального алгоритма. Некоторая эвристика, которая имеет смысл, - это прекрасно.

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

Ввод:

  • 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, я его не рассматриваю больше). Я ищу онлайн-алгоритм, который поможет мне принять эти решения о том, делать ли объявление и если да, то на основе каких факторов. Есть ли у кого-нибудь идеи о том, какие алгоритмы можно использовать для решения этой или более простой версии этой проблемы?

3   3   2011-04-23 06:17:52

3 ответа:

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

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

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

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

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

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

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

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

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