В настоящее время я пишу алгоритм оптимизации раскладки клавиатуры на C (например, разработанный Питером Клауслером), и я хочу реализовать пропорциональный выбор, как описано здесь (PDF Ссылка):

При выборе рулетки вы выбираете членов населения на основе модели колеса рулетки. Сделайте круговую диаграмму, где область членаS срез ко всему кругу является отношение членовTness для всего населения. Как вы можете видеть, случайным образом ли выбрана точка на окружности круга тех членов группы населения с более высокимУ tness будет больше шансов быть выбранным. Это обеспечивает естественный отбор.

Проблема в том, что я нене вижу, как это эффективно реализовать. Я'Мы думали о двух методах: один ненадежный, а другой медленный.

Во-первых, медленный:

Для пула клавиатуры длиной N создайте массив длины N, где каждый элемент массива фактически содержит два элемента, минимальное и максимальное значение. Каждая клавиатура имеет соответствующее минимальное и максимальное значение, а диапазон зависит от пригодности клавиатуры. Например, если клавиатура имеет пригодность 10, клавиатура 1 - 20, а клавиатура 2 - 25, это будет выглядеть так: Код:

array[0][0] = 0; // minimum
array[0][1] = 9; // maximum
array[1][0] = 10;
array[1][1] = 30;
array[2][0] = 31;
array[2][1] = 55;

(В этом случае более низкая приспособленность лучше, так как это означает, что требуется меньше усилий.)

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

Проблема в том, что это очень медленно. Для завершения требуется O (N ^ 2) операций.

Следующий быстрый:

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

Итак, вопрос в том, что такое эффективная реализация?

На странице 36 этой книги есть несколько эффективный алгоритм (Ссылка на сайт), но проблема в том, чтоЭффективно, только если вы выбираете рулетку только один или несколько раз. Есть ли эффективный способ сделать много выборов рулетки параллельно?