алгоритм для случайного распределения объектов с ограничениями

Question

Помогите мне найти хороший алгоритм?

У меня есть сумка, полная n шаров. (Скажем, 28 шариков для примера.)

Шары в этой сумке каждый имеют 1 цвет. В сумке есть < = 4 разных цвета шариков. (Скажем, красный, зеленый, синий и фиолетовый - это возможности.)

У меня есть три ведра, каждая из которых имеет количество шаров, в которых им нужно в конечном итоге. Эти числа составляют n. (Например, для того, чтобы ведро А должно было иметь 7 шаров, ведро B должно было закончиться с 11 шарами, ведро C должно закончиться 10 шарами.)

Ковши также могут иметь или не иметь цвет ограничения - цвета, которые они не будут принимать. (Ковш A не принимает пурпурные шарики или зеленые шарики. Ковш B не принимает красные шарики. Ковш C не принимает пурпурные шары или синие шарики.)

Мне нужно распределять шары эффективно и случайным образом (равным вероятность всех возможностей).

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

Дано указание, что всегда есть возможность распределить шары по крайней мере 1 раз. (У меня не будет мешка только красных шариков, а некоторое ведро с номером> 0 не принимает красные шарики.)

Все шары считаются отличными, даже если они одного цвета. (Одна из возможностей, когда ведро C получает красный шар 1, а не красный шар 2, отличается от возможности, где все одинаково, за исключением того, что ведро C получает красный шар 2, а не красный шар 1.)

Редактировать, чтобы добавить свою идею :

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

Choose a ball from the bag at random. (Call it "this ball".) 

If this ball fits and is allowed in a number of buckets > 0: 
    Choose one of those buckets at random and put this ball in that bucket. 

else (this ball is not allowed in any bucket that it fits in): 
    Make a list of colors that can go in buckets that are not full. 
    Make a list of balls of those colors that are in full buckets that this ball is allowed in. 
    If that 2nd list is length 0 (There are no balls of colors from the 1st list in the bucket that allows the color of this ball): 
     ASSERT: (Please show me an example situation where this might not be the case.) 
       There is a 3rd bucket that is not involved in the previously used buckets in this algorithm. 
       (One bucket is full and is the only one that allows this ball. 
       A second bucket is the only one not full and doesn't allow this ball or any ball in the first bucket. 
       The 3rd bucket is full must allow some color that is in the first bucket and must have some ball that is allowed in the second bucket.) 
     Choose, at random, a ball from the 3rd bucket balls of colors that fit in the 2nd bucket, and move that ball to the 2nd bucket. 
     Choose, at random, a ball from the 1st bucket balls of colors that fit in the 3rd bucket, and move that ball to the 3rd bucket. 
     Put "this ball" (finally) in the 1st bucket. 
    else: 
     Choose a ball randomly from that list, and move it to a random bucket that is not full. 
     Put "this ball" in a bucket that allows it. 
Next ball. 

Answer 1

Вот алгоритм O (n^3). (3 получается из числа ковшей.)

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

Мы перечислим алгоритм с двумя вложенными циклами. Внешняя петля проходит через шары. Цвет каждого шара не имеет значения; только чтобы его можно было разместить в определенных ведрах, но не в других. В начале каждой внешней итерации у нас есть список частичных решений (присваивание шаров, рассматриваемых до сих пор в ведра). Внутренний цикл связан с частичными решениями; мы добавляем несколько частичных решений в новый список, расширяя назначение всеми допустимыми способами. (Исходный список имеет один элемент, пустое назначение.)

Чтобы более эффективно рассчитывать решения, мы применяем метод динамического программирования или кодирования длины в зависимости от того, как вы его смотрите. Если два частичных решения имеют одинаковые подсчеты в каждом ведре (O (n^3) возможности в течение всего срока действия алгоритма), то все допустимые расширения одного из них являются действительными расширениями другого и наоборот.Мы можем аннотировать элементы списка счетчиком и отбрасывать всех, кроме одного представителя каждого класса эквивалентности частных решений.

Наконец, чтобы получить случайный образец, вместо того, чтобы выбирать представителя произвольно, когда мы объединяем две записи списка, мы проецируем представителя с каждой стороны пропорционально счету этой стороны.

Рабочий код Python (O (n^4) для простоты, возможны структурные улучшения данных).

#!/usr/bin/env python3 
import collections 
import random 


def make_key(buckets, bucket_sizes): 
    return tuple(bucket_sizes[bucket] for bucket in buckets) 


def sample(balls, final_bucket_sizes): 
    buckets = list(final_bucket_sizes) 
    partials = {(0,) * len(buckets): (1, [])} 
    for ball in balls: 
     next_partials = {} 
     for count, partial in partials.values(): 
      for bucket in ball: 
       next_partial = partial + [bucket] 
       key = make_key(buckets, collections.Counter(next_partial)) 
       if key in next_partials: 
        existing_count, existing_partial = next_partials[key] 
        total_count = existing_count + count 
        next_partials[key] = (total_count, existing_partial if random.randrange(total_count) < existing_count else next_partial) 
       else: 
        next_partials[key] = (count, next_partial) 
     partials = next_partials 
    return partials[make_key(buckets, final_bucket_sizes)][1] 


def test(): 
    red = {'A', 'C'} 
    green = {'B', 'C'} 
    blue = {'A', 'B'} 
    purple = {'B'} 
    balls = [red] * 8 + [green] * 8 + [blue] * 8 + [purple] * 4 
    final_bucket_sizes = {'A': 7, 'B': 11, 'C': 10} 
    return sample(balls, final_bucket_sizes) 


if __name__ == '__main__': 
    print(test()) 

Answer 2

Я не совсем уверен, что такое компромисс между случайным, правильным и эффективным распределением.

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

Если вы хотите быть уверены, что будете быть верными и случайными, вы можете попытаться получить все возможное распространение и выбрать один из них случайным образом, но это может быть очень неэффективно, поскольку базовый алгоритм грубой силы для создания всех возможностей распространения почти быть в сложности NumberOfBucket^NumberOfBalls.

Лучшим алгоритмом для создания всего правильного случая было бы попытаться построить все случаи, проверяющие ваши два правила (в ведро B1 могут быть только шары N1 & ведро принимает только определенные цвета) цвет по цвету. Например:

//let a distribution D be a tuple N1,...,Nx of the current number of balls each bucket can accept 

void DistributeColor(Distribution D, Color C) { 
    DistributeBucket(D,B1,C); 
} 

void DistributeBucket(Distribution D, Bucket B, Color C) { 
    if B.canAccept(C) { 
    for (int i = 0; i<= min(D[N],C.N); i++) { 
     //we put i balls of the color C in the bucket B 
     C.N-=i; 
     D.N-=i; 
     if (C.N == 0) { 
     //we got no more balls of this color 
     if (isLastColor(C)){ 
      //this was the last color so it is a valid solution 
      save(D); 
     } else { 
      //this was not the last color, try next color 
      DistributeColor(D,nextColor(C)) 
     } 
     } else { 
     //we still got balls 
     if (isNotLastBucket(B)) { 
      //This was not the last bucket let's try to fill the next one 
      DistributeBucket(D, nextBucket(B), C) 
     } else { 
      //this was the last bucket, so this distibution is not a solution. Let's do nothing (please don't kill yourself :/) 
     } 
     } 
     //reset the balls for the next try 
     C.N+=i; 
     D.N+=i; 
    } 
    } 
    //it feel like déjà vu 
    if (isNotLastBucket(B)) { 
    //This was not the last bucket let's try to fill the next one 
    DistributeBucket(D, nextBucket(B), C) 
    } else { 
    //this was the last bucket, so this distribution is not a solution. 
    } 
} 

(Этот код является псевдо C++ и не предназначены для работоспособной)

Answer 3

1 Сначала вы выбираете 7 между 28: у вас есть C28,7 = 1184040 возможности.

2 Во-вторых, вы выбираете 11 между оставшимися 21: у вас есть C21,11 = 352716 возможностей.

3 остальные 10 элементов в ведре C.

На каждом шаге, если ваш выбор не приспосабливает правила, вы останавливаетесь и сделать это снова.

Все предлагает 417629852640 возможностей (без ограничений).

Это не очень эффективно, но для одного выбора это не имеет большого значения. Если ограничений не слишком ограничительный, вы не теряете слишком много времени.

Если решений очень мало, вы должны ограничить комбинации (только хорошие цвета).

Answer 4

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

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

Чтобы переформулировать задачу и уточнить понятие о равной вероятности, здесь наивный алгоритм, который является простым и правильным, но потенциально очень неэффективна:

• Сортировать шары в случайном порядке с равновероятно. Каждый n! перестановки одинаково вероятны. Это можно сделать с помощью известных алгоритмов перетасовки.
• Назначьте шары ковшим последовательно в соответствии с мощностью. В другими словами, используя пример ковшей, сначала от 7 до A, от 11 до B, от 10 до C.
• Проверьте соответствие цветовых ограничений. Если они не были встретились, вернитесь к началу; иначе остановитесь.

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

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

• A: 7 мячей; разрешенные цвета (красный, синий)
• B: 11 мячей; разрешенные цвета (зеленый, синий, фиолетовый)
• C: 10 мячей; разрешенные цвета (красный, зеленый)
• Шариков: 6 красных, 6 зеленых, 10 синих, 6 фиолетового

В апробировании с этими параметрами, наивный алгоритм не удались найти допустимое решение в 20 миллионов итераций. Но теперь давайте уменьшим проблему .

Обратите внимание, что все 6 фиолетовых шаров должны идти в B, потому что это единственное ведро , которое может их принять. Таким образом, проблема сводится к:

• наперед заданный: 6 фиолетового B
• A: 7 шаров; разрешенные цвета (красный, синий)
• B: 5 мячей; разрешенные цвета (зеленый, синий)
• C: 10 мячей; разрешенные цвета (красный, зеленый)
• Шарики: 6 красных, 6 зеленых, 10 синий

C нуждается в 10 мячей, и может принимать только красный и зеленый. Их 6. Возможные значения: 4 + 6, 5 + 5, 6 + 4. Поэтому мы должны поставить не менее 4 красных и 4 зеленых в C.

• наперед заданный: 6 фиолетового B, 4 красного С, 4-зеленые C
• A: 7 шаров; разрешенные цвета (красный, синий)
• B: 5 мячей; разрешенные цвета (зеленый, синий)
• C: 2 мяча; разрешенные цвета (красный, зеленый)
• Шарики: 2 красных, 2 зеленых, 10 синий

Мы должны поставить 10 синих шаров где-то. C не возьмет. B может принимать максимум 5 ; другие 5 должны идти в A. A может принимать 7 максимум; другой 3 должен идти в B. Таким образом, A должен принимать не менее 5 синих, а B должен принимать по не менее 3 синих.

• наперед заданный: 6 фиолетового B, 4 красных в C, 4-зеленых в C, 5 синих в 3 синих в B
• A: 2 шаров; разрешенные цвета (красный, синий)
• B: 2 мяча; разрешенные цвета (зеленый, синий)
• C: 2 мяча; разрешенные цвета (красный, зеленый)
• Шариков: 2 красных, 2 зеленых, 2 синего

На данный момент, задача тривиальна: проверка случайных решений редуцированной задачи найти верное решение в течение несколько попыток.

Для полностью уменьшенной задачи, 80 из 720 перестановок действительны, поэтому верное решение будет найдено с вероятностью 1/9. Для оригинальной проблемы , из 28! перестановок есть 7! * 11! * 10! * 80 действительных решений, и вероятность их нахождения меньше одного из пяти миллиардов.

Превращение человеческого рассуждения, используемого выше в алгоритм уменьшения, является более сложным, и я буду рассматривать его кратко. Обобщение из приведенных выше случаев :

• Есть ли какие-либо шары, которые войдут только в одно ведро?
• Есть ли ведро, которое должно занимать минимальное количество шаров одного или больше цветов?
• Есть ли цвет, который может входить только в определенные ведра?

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

И наконец: будет ли это работать хорошо? Трудно быть уверенным, но я подозреваю, что в большинстве случаев это будет , потому что ограничения являются причиной того, что алгоритм наивного терпит неудачу. Если мы сможем использовать ограничения, чтобы свести проблему к тому, где ограничения не имеют большого значения, наивный алгоритм должен найти решение без особых проблем; количество допустимых решений должно быть достаточно большой долей от всех возможностей .

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