> Под «сочетаниями» понимается (Новиков. Дискретная
> математика для программистов):
Мое мнение - совершенно паршивая книжка. Разобраться по ней в чем-либо совершенно невозможно. Приводится куча материала, но все с одной стороны очень поверхностно, но с другой стороны местами с залезанием в дебри, которые не нужны (на том уровне, что изложен в книге). Одна из худших книг по предмету, что я когда-либо видел. Но это так, замечание в сторону.
> 1. Число строго монотонных функций, или число
> размещений n неразличимых предметов по m ящикам, не более
> чем по одному в ящик, то есть число способов выбрать из m
> ящиков n ящиков с предметами, называется числом
> сочетаний и обозначается C(m, n)
> 2. Число монотонных функций, или число размещений
> n неразличимых предметов по m ящикам, называется
> числом сочетаний с повторениями и
> обозначается V(m, n)
> Может кто-нибудь мне разъяснить различие между двумя этими
> понятиями? Сколько голову не ломал, так и не нашёл.
Совершенно дурацкие формулировки и определения (формально конечно все правильно, но я бы никому не рекомендовал по таким определениям изучать дискретку).
В общем представь, что у тебя есть ящик с N предметами в нем. Ты вытаскиваешь из него M предметов. Но сделать ты это можешь на самом деле двумя способами:
1. Вытащить сразу целую охапку.
2. Вытащить первый, положить обратно. Вытащить второй, положить опять обратно и т. д.
Пускай у тебя в урне лежат три шара - красный (К), желтый (Ж) и зеленый (З). Ты вытаскиваешь два шара наугад.
По первой схеме ты можешь вытащить наборы {К, З}, {К, Ж}, {Ж, З}.
По второй схеме помимо уже перечисленных наборов можешь вытащить еще {К, К}, {З, З} и {Ж, Ж}, потому что перед тем как тянуть второй шар, ты сначала кладешь то что вытянул обратно. Поэтому схема и называется схемой с повторениями (ее так же называют схемой с возвращениями).
> Теперь к сути вопроса: есть массив из n элементов,
> элементы могут принимать значения либо 0, либо 1. Нужно
> найти все варианты заполнения этого массива единицами
> (общее число единиц = k < n). Алгоритм должен
> выполняться как можно более быстрее.
Количество вариантов здесь будет N!/(K!(N-K)!). Какой бы алгоритм ты не придумал, именно такое количество значений должна будет сгенерить программа. Величина этого числа вообще говоря может быть различной, и зависит оно и от K и от N. Наибольшее значение достигается при K=N/2, наименьшее при K=0. В зависимости от K можно придумать различные алгоритмы перебора всех значений, для произвольного K вряд ли удастся придумат что-то очень быстрое.
> Мне это нужно для проведения экспериментов при поиске
> оптимальной стратегии в игре крестики-нолики.
Если тебе нужен алгоритм для компьютерных крестиков-ноликов, то ты пошел скорее всего не по тому пути (это моя догадка - сам я крестиков-ноликов никогда не писал). Методы полного перебора как правило весьма трудоемки.
Попробуй воспользоваться рекурсией. Примерный алгоритм такой:
sometype fileld[M, N];
//Матрица, характеризующая поле
vector<point> list;
//Список возможных ходов
int search(point T, bool AI) {
/*Получает в качестве параметра клетку на поле
и флаг - чей это ход, компьютера или человека.
Возвращает насколько этот ход полезен для компьютера*/
/*Эта функция должна проставить в поле fileld текущий ход
и запомнить его - она должна будет его отменить при завершении
своей работы*/
/*Так же она должна обновить список возможных ходов list
и опять же по своему завершению восстановить его - пиши это сам.
Все это не сложно, но мне просто лень.*/
/*Про то что это значение, возвращаемое через search - читай ниже*/
if (AI) {
point p=0;
int score=-1;
//Премия за лучшый ход
foreach (i=0; i<list.size; i++) {
if (int s = search(list[i], !AI) > score) {
p = list[i];
score = s;
}
else if (s<0) return -1;
}
}
else {
//Про ход человека читай ниже
}
/*После этого цикла в p лежит оптимальный ход
Не забуть в конце функции восстановить list и field
Так же надо расчитать и вернуть полезность хода,
о чем тоже ниже*/
}
---
Одно "но": представленный алгоритм вообще говоря бесконечен. Тебе надо отдельным параметром передавать глубину поиска, и останавливать его на каком-то этапе.
Теперь о значении, возвращаемом search. Оно зависит от того, чей это ход - твой или противника. Если search рассматривает ход противника, то тебе надо проверять, а не получилось ли выстроить в ряд 5 крестиков. Если получилось - значит ход компьютера, из которого последовал такой ход человека неприемлим. Сразу прекращаем поиск и рассматриваем другой путь.
В случае если это ход компьютера, то надо каким-либо образом оценивать полезность хода (если из него следует выигрышный ход человека, то полезность этого отрицательная). Например, полезность можно оценивать количеством крестиков твоих и противника выставленных в ряд. Или общим количеством возможных ходов, которые увеличивает количество крестиков, выставленных в ряд, или количество возможных ходов компьютера, следующих из хода человека, которые приводят к выигрышу одной из сторон.
При вычислении полезность хода так же надо учитывать, что человек скорее всего выберет наиболее оптимальный ход. То есть рассматривать те возможные ходы, где человек совершает откровенно дурацкие поступки не стоит.
В общем это сравнительно серьезная задача, в которой есть над чем подумать.
> Перебрал пять книжек по дискретной математике и
> комбинаторике, перелистал Кнута, но алгоритма так и не
> нашёл. Придумал я один алгоритм с кучей вложенных циклов,
> но в плане быстродействия он вообще никакой.
Кнута нельзя использовать как справочник по алгоритмам. Его надо читать от корки до корки (но прежде чем за него браться надо перечитать кучу других книг по алгоритмам, так как сходу Кнут весьма трудно воспринимается; хотя после после прочтения несольких других книг уже может случитьсят так, что Кнут и не понадобится). А Новикова выкить.
|
подробно о проекте
Анализ криптографических сетевых...
новое сообщение
закрытая нитка
новое сообщение
в закрытой нитке
старое сообщение
