информационная безопасность
без паники и всерьез
 подробно о проектеRambler's Top100
Spanning Tree Protocol: недокументированное применениеВсе любят медГде водятся OGRы
BugTraq.Ru
Русский BugTraq
 Анализ криптографических сетевых... 
 Модель надежности двухузлового... 
 Специальные марковские модели надежности... 
 Phrack #70/0x46 
 Возможно, Facebook наступил на... 
 50 лет электронной почте 
главная обзор RSN блог библиотека закон бред форум dnet о проекте
bugtraq.ru / форум / theory
Имя Пароль
ФОРУМ
все доски
FAQ
IRC
новые сообщения
site updates
guestbook
beginners
sysadmin
programming
operating systems
theory
web building
software
hardware
networking
law
hacking
gadgets
job
dnet
humor
miscellaneous
scrap
регистрация





Легенда:
  новое сообщение
  закрытая нитка
  новое сообщение
  в закрытой нитке
  старое сообщение
  • Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
  • Новичкам также крайне полезно ознакомиться с данным документом.
Re 28.01.08 15:53  Число просмотров: 4452
Автор: 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 ноликов.
Ну тогда просто перебирай все возможные ходы и смотри не получилось ли где чего. Зачем здесь комбинаторика не совсем понятно.

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

> Я слышал есть теорема о том, что в любой игре, где доступна
> вся информация (шахматы, шашки, крестики-нолики),
> теоретически существует стратегия, следуя которой в худшем
> случае придёшь к ничьёй. Если такая стратегия будет
> известна, можно ли будет обойтись без полного перебора?

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

Вообще на этот счет ты начал читать немного не то. Вопросами оптимальных стратегий занимается теория игр. В книгах по алгоритмам ты ничего не найдешь.
<theory> Поиск 








Rambler's Top100
Рейтинг@Mail.ru


  Copyright © 2001-2021 Dmitry Leonov   Page build time: 0 s   Design: Vadim Derkach