Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
Re 28.01.08 15:53 Число просмотров: 4725
Автор: Heller <Heller> Статус: Elderman
Отредактировано 28.01.08 15:58 Количество правок: 2
|
> По поводу твоего объяснения и формулировок Новикова. Оба
> определения ты разъясняешь на шарах К Ж З, но из второго
> определения Новикова можно предположить, что речь идёт об
> абсолютно одинаковых шарах. Или я чего-то не понял?
Они могут быть неразличимы для человека. То есть может быть и три черных шара. Но тем не менее все они разные. То есть можно сказать, что есть шары Ч1, Ч2, Ч3. Человек не скажет где какой шар, но все равно набор {Ч1, Ч2} отличается от набора {Ч2, Ч3}.
Вопрос различимости/неразличимости приходит из тервера. Там типичны задачи вроде: "в урне три шара - два белых и один черный; какова вероятность выташить одновременно они черный и один белый"?. В условии задачи говорится только о черных шарах, то есть подразумевается, что мы их не различаем. Но при подсчете всех возможных комбинаций мы все равно обязаны считать черные шары как различные. Итого всего возможных исходов - {Б1, Б2}, {Б1, Ч}, {Б2, Ч}. Всего три. Требуется найти вероятность того, что вытащили белый и черный. Таких наборов только два: {Б1, Ч}, {Б2, Ч}. Для "пользователя" они неразличимы. Но считаем мы их как разлдичные. В моем примере с шарами К, Ж и З можно считать, что пользователь дальтоник. Шары разные, но он их не различает :-)
> > N!/(K!(N-K)!
> Проблема в том, что текущий мой алгоритм перебирает куда
> больше вариантов. Эту оценку я тоже нашёл, но вот как
> добиться такого результата - нет.
Значит ошибка в алгоритме. Если продоставишь слгоритм, возможно укажу на ошибку.
> За алгоритм спасибо, буду вникать, но предварительно.
> Рекурсия ведь довольно медленная вещь, так что вряд ли он
> меня устроит.
Я не понял твоей идеи, но вряд ли рекурсия окажется сильно медленнее.
> Перебор мне нужен не для зашивания в программу, а только
> чтобы смотреть на оптимальную расстановку крестиков, чтобы
> противник не мог выстроить линию из 5 ноликов.
Ну тогда просто перебирай все возможные ходы и смотри не получилось ли где чего. Зачем здесь комбинаторика не совсем понятно.
> Т.е. Вы предлагаете полным перебором выигрышную ситуацию
> искать?
В общем да. Но здесь надо учесть, что не обязательно делать это каждый ход - рекурсию можно здорово оптимизировать. Например, запоминать возможные ходы и анализировать только новые открывающиеся возможности после хода противника. Тогда каждый ход можно привести к просчету лишь нескольких вариантов. В любом случае у компьютеров сейчас достаточно много тактов с секунду - быстродействие крестиков-ноликов не критично.
> Я слышал есть теорема о том, что в любой игре, где доступна
> вся информация (шахматы, шашки, крестики-нолики),
> теоретически существует стратегия, следуя которой в худшем
> случае придёшь к ничьёй. Если такая стратегия будет
> известна, можно ли будет обойтись без полного перебора?
> Может ли кто-нибудь рассказать об этой теореме, а то я
> только поверхностно о ней знаю.
Она существует не теоретически, а на самом деле. Эта стратерия - перебор всех возможных вариантов. Он обязательно приведет минимум к ничьей. Это вполне очевидно - если делать каждый раз лучший из возможных ходов, то обязательно побелишь. Если твой противник делает тоже каждый раз лучший ход, то у нас будет ничья (правда, здесь могут быть вариации в зависимости от правил игры). Другой вопрос, что это очень трудоемко. Во многих случаях можно найти более быстрые стратегии, но это уже частные случаи - на этот счет теорем нет.
Вообще на этот счет ты начал читать немного не то. Вопросами оптимальных стратегий занимается теория игр. В книгах по алгоритмам ты ничего не найдешь.
|
|
|
подробно о проекте
Анализ криптографических сетевых... 
