информационная безопасность
без паники и всерьез
 подробно о проектеRambler's Top100
Все любят медСтрашный баг в WindowsГде водятся OGRы
BugTraq.Ru
Русский BugTraq
 Анализ криптографических сетевых... 
 Модель надежности двухузлового... 
 Специальные марковские модели надежности... 
 Три миллиона электронных замков... 
 Doom на газонокосилках 
 Умер Никлаус Вирт 
главная обзор RSN блог библиотека закон бред форум dnet о проекте
bugtraq.ru / форум / theory
Имя Пароль
ФОРУМ
если вы видите этот текст, отключите в настройках форума использование JavaScript
регистрация





Легенда:
  новое сообщение
  закрытая нитка
  новое сообщение
  в закрытой нитке
  старое сообщение
  • Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
  • Новичкам также крайне полезно ознакомиться с данным документом.
Спасибо за поправку. А можешь названия и авторов книг,... 31.01.08 04:20  Число просмотров: 4777
Автор: Vedrus <Serokhvostov Anton> Статус: Member
Отредактировано 31.01.08 04:28  Количество правок: 1
<"чистая" ссылка>
Спасибо за поправку. А можешь названия и авторов книг, которые у тебя есть выписать?
Можешь прямую ссылку дать на лекции? Я там их не нашёл.
<theory>
Составить алгоритм генерации всех сочетаний 27.01.08 08:32  
Автор: Vedrus <Serokhvostov Anton> Статус: Member
<"чистая" ссылка>
Под «сочетаниями» понимается (Новиков. Дискретная математика для программистов):

1. Число строго монотонных функций, или число размещений n неразличимых предметов по m ящикам, не более чем по одному в ящик, то есть число способов выбрать из m ящиков n ящиков с предметами, называется числом сочетаний и обозначается C(m, n)

2. Число монотонных функций, или число размещений n неразличимых предметов по m ящикам, называется числом сочетаний с повторениями и обозначается V(m, n)

Может кто-нибудь мне разъяснить различие между двумя этими понятиями? Сколько голову не ломал, так и не нашёл.

Теперь к сути вопроса: есть массив из n элементов, элементы могут принимать значения либо 0, либо 1. Нужно найти все варианты заполнения этого массива единицами (общее число единиц = k < n). Алгоритм должен выполняться как можно более быстрее.

Мне это нужно для проведения экспериментов при поиске оптимальной стратегии в игре крестики-нолики.

Перебрал пять книжек по дискретной математике и комбинаторике, перелистал Кнута, но алгоритма так и не нашёл. Придумал я один алгоритм с кучей вложенных циклов, но в плане быстродействия он вообще никакой.
Мое мнение - совершенно паршивая книжка. Разобраться по ней... 27.01.08 21:17  
Автор: Heller <Heller> Статус: Elderman
<"чистая" ссылка>
> Под «сочетаниями» понимается (Новиков. Дискретная
> математика для программистов):
Мое мнение - совершенно паршивая книжка. Разобраться по ней в чем-либо совершенно невозможно. Приводится куча материала, но все с одной стороны очень поверхностно, но с другой стороны местами с залезанием в дебри, которые не нужны (на том уровне, что изложен в книге). Одна из худших книг по предмету, что я когда-либо видел. Но это так, замечание в сторону.

> 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 крестиков. Если получилось - значит ход компьютера, из которого последовал такой ход человека неприемлим. Сразу прекращаем поиск и рассматриваем другой путь.

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

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

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

> Перебрал пять книжек по дискретной математике и
> комбинаторике, перелистал Кнута, но алгоритма так и не
> нашёл. Придумал я один алгоритм с кучей вложенных циклов,
> но в плане быстродействия он вообще никакой.
Кнута нельзя использовать как справочник по алгоритмам. Его надо читать от корки до корки (но прежде чем за него браться надо перечитать кучу других книг по алгоритмам, так как сходу Кнут весьма трудно воспринимается; хотя после после прочтения несольких других книг уже может случитьсят так, что Кнут и не понадобится). А Новикова выкить.
Heller, спасибо за ответ. Новиков и правда мудрёная... 28.01.08 03:26  
Автор: Vedrus <Serokhvostov Anton> Статус: Member
<"чистая" ссылка>
Heller, спасибо за ответ. Новиков и правда мудрёная книжка, но были моменты когда она мне помогала.

По поводу твоего объяснения и формулировок Новикова. Оба определения ты разъясняешь на шарах К Ж З, но из второго определения Новикова можно предположить, что речь идёт об абсолютно одинаковых шарах. Или я чего-то не понял?

> N!/(K!(N-K)!
Проблема в том, что текущий мой алгоритм перебирает куда больше вариантов. Эту оценку я тоже нашёл, но вот как добиться такого результата - нет.

За алгоритм спасибо, буду вникать, но предварительно. Рекурсия ведь довольно медленная вещь, так что вряд ли он меня устроит.

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

> Кнута нельзя использовать как справочник по алгоритмам.
Спасибо, учту.

Т.е. Вы предлагаете полным перебором выигрышную ситуацию искать?

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

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

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

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

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

Вообще на этот счет ты начал читать немного не то. Вопросами оптимальных стратегий занимается теория игр. В книгах по алгоритмам ты ничего не найдешь.
Рассмотрим такую простую игру... Есть кучка камней... Играют... 04.02.08 13:24  
Автор: L Статус: Незарегистрированный пользователь
<"чистая" ссылка>
> Она существует не теоретически, а на самом деле. Эта
> стратерия - перебор всех возможных вариантов. Он
> обязательно приведет минимум к ничьей. Это вполне очевидно
> - если делать каждый раз лучший из возможных ходов, то
> обязательно побелишь. Если твой противник делает тоже
> каждый раз лучший ход, то у нас будет ничья (правда, здесь
> могут быть вариации в зависимости от правил игры). Другой
> вопрос, что это очень трудоемко. Во многих случаях можно
> найти более быстрые стратегии, но это уже частные случаи -
> на этот счет теорем нет.

Рассмотрим такую простую игру... Есть кучка камней... Играют двое. По очереди берут из кучки ровно по одному камню. Выигрывает тот, кто берёт последний камень... Ничьих не бывает.

Придумайте пожалуйста
1) непроигрышную стратегию для первого игрока, если в начале игры в кучке было два камня...
2) непроигрышную стратегию для второго игрока, если в начале игры в кучке было три камня...
Не помню, как дословно об этом говорится в теории игр, но по... 04.02.08 14:12  
Автор: Vedrus <Serokhvostov Anton> Статус: Member
<"чистая" ссылка>
Не помню, как дословно об этом говорится в теории игр, но по сути есть так называемые игры «со сбалансированными возможностями победы», Ваша игра к такой не относится.

Не относится к такой игре и «мои» крестики нолики (официальные названия: Рэндзю, Го-Моку). Чтобы сбалансировать шансы в этой игре накладываются определённые условия на первые два хода.

В общем я спрашиваю не о том, есть ли такая стратегия, а о том, как её искать, т.к. знаю, что теоретически она существует.

Может кто-нибудь поделиться ссылками на информацию о теории игр?
В таком случае, причём тут шахматы (приведённые ранее в... 12.02.08 15:53  
Автор: L Статус: Незарегистрированный пользователь
<"чистая" ссылка>
> Не помню, как дословно об этом говорится в теории игр, но
> по сути есть так называемые игры «со сбалансированными
> возможностями победы», Ваша игра к такой не относится.
>

В таком случае, причём тут шахматы (приведённые ранее в качестве примера)? Очень хотелось бы увидеть ссылку на определение игры «со сбалансированными возможностями победы» и (что более интересно) на теорему о том что шахматы являются такой игрой...

И сразу после этого отменить чемпионат мира по шахматам :)
Как я уже сказал, стратегия существует только теоретически,... 13.02.08 09:53  
Автор: Vedrus <Serokhvostov Anton> Статус: Member
<"чистая" ссылка>
Как я уже сказал, стратегия существует только теоретически, а вот практически её ищут (насколько мне известно) уже больше 50 лет. Так что за чемпионат мира по шахматам можете не беспокоиться… пока ;)
Ссылка на интуите 05.02.08 00:05  
Автор: Heller <Heller> Статус: Elderman
<"чистая" ссылка>
Насчет книжек, то в принципе можно брать любую. Есть книжка Вентцеля, но я ее не читал (однако учебник по терверу у него совершенно роскошный).

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

Вообще самый нормальный вариант: качаешь eMule, выбираешь сеть Kademlia и пишешь в поиске "Теория игр", а вторым запросом "Исследование операций". Вся классика в первом же запросе тебе и сольется.

Может быть солью тебе что-нибудь на днях в личку (если будет нормальная связь).

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

Исследование операций и теория игр
Вот как у меня всё выглядит на псевдоязыке. Мне кажется... 30.01.08 07:28  
Автор: Vedrus <Serokhvostov Anton> Статус: Member
<"чистая" ссылка>
Вот как у меня всё выглядит на псевдоязыке. Мне кажется исправлять здесь нечего, как говорится, ошибка в ДНК. Нужно придумать что-то другое, отличающееся концептуально.
for i1 = I1 to 15 do
for I2 to 15 do
	…
		for In to 15 do
		{
			if I1 <> I2 <> … <> In then
				запомнить расположение
}

---

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

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

Можешь дать ссылки на книги по теории игр? Можно бумажные книги, лучше электронные.

И ещё вопрос, по поводу алгоритма Квайне-Маклатски (может быть неправильно написал) можешь что-нибудь сказать? Вроде как через него можно существенно сократить обход деревьев, вот только кроме названия я про него ничего больше не знаю.
Это очень странно выглядит. Более правильная реализация... 30.01.08 20:07  
Автор: Heller <Heller> Статус: Elderman
<"чистая" ссылка>
>
> for i1 = I1 to 15 do
> for I2 to 15 do
> 	…
> 		for In to 15 do
> 		{
> 			if I1 <> I2 <> …
> <> In then
> 				запомнить расположение
> }
> 

---
Это очень странно выглядит. Более правильная реализация твоей идеи::
for i1 = 1 to n-k do
    for i2 = i1+1 to n-k+1 do
          for i3 = i2+1 to n-k+2 do
               ...
                 запомнить расположение

---

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

> Можешь дать ссылки на книги по теории игр? Можно бумажные
> книги, лучше электронные.
У меня есть электронные книги, но нет нормального инета, так что выложить не могу. Может быть через какое-то время. Вообще есть на эту тему ресурс: http://gametheory.net. Сам там ничего не читал, так что не знаю насколько он хорош. Есть так же электронные лекции, которых я опять же не читал, но вообще ресурс достаточно не плохой: http://intuit.ru - там и алгоритмы, и теория игр и все что хочешь. А вообще я все свои книги по теории игр выкачивал из осла (http://emule-project.net) - очень рекомендую. Там можн найти классические труды, после которых уже ничего не надо.

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

> И ещё вопрос, по поводу алгоритма Квайне-Маклатски (может
> быть неправильно написал) можешь что-нибудь сказать? Вроде
> как через него можно существенно сократить обход деревьев,
> вот только кроме названия я про него ничего больше не знаю.
Первый раз слышу. Если что-либо найдешь сообщи.
Спасибо за поправку. А можешь названия и авторов книг,... 31.01.08 04:20  
Автор: Vedrus <Serokhvostov Anton> Статус: Member
Отредактировано 31.01.08 04:28  Количество правок: 1
<"чистая" ссылка>
Спасибо за поправку. А можешь названия и авторов книг, которые у тебя есть выписать?
Можешь прямую ссылку дать на лекции? Я там их не нашёл.
1




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


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