2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Альфа-бета отсечения
Сообщение13.10.2018, 19:19 
Здравствуйте, пытаюсь доказать теорему об альфа-бета отсечениях. Теорему формулирую следующим образом: для произвольного узла $X$ графа с дочерними узлами $ X_1,...,X_n $ определим функцию $E(X)$ следующим образом: $E(X)=\max(E(X_1),...,E(X_n))$, если в $X$ ход игрока 1, и $E(X)=\min(E(X_1),...,E(X_n))$, если в $X$ ход игрока 2, $E(X)=$некоторое число, если $X$ конечный узел. Опредеим теперь следующие функции

$ \alpha(X):=\max(E(X_1),...,E(X_{k}),-\infty), k\leq n $,

$ \beta(X)=+\infty $

если $X$ - корневой узел в котором ходит игрок 1, $ X_1,...,X_n $ - дочерние узлы $X$,

$ \alpha(X):=\max(E(X_1),...,E(X_{k}),\alpha(Y)), k\leq n $,

$ \beta(X)=\beta(Y) $,

если $X$ - произвольный узел в котором ходит игрок 1, $Y$ - родительский узел $X$, $ X_1,...,X_n $ - дочерние узлы $X$,

$ \beta(X):=\min(E(X_1),...,E(X_{k}),\beta(Y)), k\leq n $,

$ \alpha(X)=\alpha(Y) $,

если $X$ - произвольный узел в котором ходит игрок 2.

Теперь собственно задача: пусть $X$ --- произвольный узел в котором ходит игрок 1, пусть $ \max(E(X_1),...,E(X_k))\geq \beta(X), k\leq n $ тогда $E(X)=\max(E(X_1),...,E(X_k))$. Проблема в том, что не получается доказать это.

 
 
 
 Re: Альфа-бета отсечения
Сообщение14.10.2018, 16:41 
Прошу прощения - ерунду написал. Тема закрыта.

 
 
 [ Сообщений: 2 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group