㈠ 剪枝算法和A*算法的区别
剪枝完全忽略了后面过程带来的代价，而A*给了后面的过程一个估价
㈡ 怎么优化alphabeta剪枝算法
貌似是折半查找法publicclassLianXi5{publicstaticvoidmain(String[]args){intstart,end,middle,n=12;int[]a={-2,1,5,4,8,12,17,45,56,90,100};start=0;end=a.length-1;middle=(start+end)/2;intcount=0;while(n!=a[middle]){if(n>a[middle]){start=middle;}elseif(na.length/2)break;}if(count>a.length/2)System.out.println(":"+n+"不在数组中");elseSystem.out.println(":"+n+"是数组中的第"+middle+"个元素");}}
㈢ 为什么使用剪枝算法
避免不必要的运算，减少开销。
㈣ 10、填空在AlphaBeta剪枝算法中,我们把一个结点可能取值的上界记作____值
这个问题问的不是很清楚，个人理解，在AlphaBeta剪枝算法中，可以把一个节点可能取值的上界记作 Beta 值。
AlphaBeta剪枝算法是对极大极小算法的优化，效率更高。极大极小是一种暴力搜索策略，需要遍历所有可能的情况，随着节点数特别是深度的增加，算法性能会大幅下降。AlphaBeta剪枝算法采用递归的方式进行倒推估算，可以在搜索过程中剪除无用的分支，从而减少不必要的搜索（这些搜索中不会有满足要求的答案），提升算法的效率。
可以这样简单地理解吧，每一层的节点都有Alpha（下界）、Beta（上界），而且是动态调整的，如果在推导过程中发现 Alpha>=Beta，那么就可以终止当前节点往下各层级的搜索，达到提高效率的目的。
㈤ 什么是alpha-beta剪枝算法
貌似是折半查找法
public class LianXi5 {
public static void main(String[] args)
{
int start,end,middle,n=12;
int []a={-2,1,5,4,8,12,17,45,56,90,100};
start = 0;
end = a.length-1;
middle = (start + end)/2;
int count=0;
while(n!=a[middle])
{
if(n>a[middle])
{
start = middle;
}
else if(n<a[middle])
{
end = middle;
}
middle=(start + end)/2;
count++;
if(count>a.length/2)
break;
}
if(count>a.length/2)
System.out .println (":"+n+"不在数组中");
else
System.out .println (":"+n+"是数组中的第"+middle+"个元素");
}
}
㈥ python 井字棋 ALPHA-BETA剪枝算法和暴力算法 具体代码
#!/usr/bin/env python
'''Tic tac toe in python, Minimax with alpha-beta pruning.'''
import sys
import random
import getopt
# Board: array of 9 int, positionally numbered like this:
# 0 1 2
# 3 4 5
# 6 7 8
# Well-known board positions
WINNING_TRIADS = ((0, 1, 2), (3, 4, 5), (6, 7, 8), (0, 3, 6), (1, 4, 7),
(2, 5, 8), (0, 4, 8), (2, 4, 6))
PRINTING_TRIADS = ((0, 1, 2), (3, 4, 5), (6, 7, 8))
# The order in which slots get checked for absence of a player's token:
SLOTS = (0, 1, 2, 3, 4, 5, 6, 7, 8)
# Internal-use values. Chosen so that the "winner" of a finished
# game has an appropriate value, as X minimizes and O maximizes
# the board's value (function board_valuation() defines "value")
# Internally, the computer always plays Os, even though the markers[]
# array can change based on -r command line flag.
X_token = -1
Open_token = 0
O_token = 1
# Strings for output: player's markers, phrase for end-of-game
MARKERS = ['_', 'O', 'X']
END_PHRASE = ('draw', 'win', 'loss')
HUMAN = 1
COMPUTER = 0
def board_valuation(board, player, next_player, alpha, beta):
'''Dynamic and static evaluation of board position.'''
# Static evaluation - value for next_player
wnnr = winner(board)
if wnnr != Open_token:
# Not a draw or a move left: someone won
return wnnr
elif not legal_move_left(board):
# Draw - no moves left
return 0 # Cat
# If flow-of-control gets here, no winner yet, not a draw.
# Check all legal moves for "player"
for move in SLOTS:
if board[move] == Open_token:
board[move] = player
val = board_valuation(board, next_player, player, alpha, beta)
board[move] = Open_token
if player == O_token: # Maximizing player
if val > alpha:
alpha = val
if alpha >= beta:
return beta
else: # X_token player, minimizing
if val < beta:
beta = val
if beta <= alpha:
return alpha
if player == O_token:
retval = alpha
else:
retval = beta
return retval
def print_board(board):
'''Print the board in human-readable format.
Called with current board (array of 9 ints).
'''
for row in PRINTING_TRIADS:
for hole in row:
print MARKERS[board[hole]],
print
def legal_move_left(board):
''' Returns True if a legal move remains, False if not. '''
for slot in SLOTS:
if board[slot] == Open_token:
return True
return False
def winner(board):
''' Returns -1 if X wins, 1 if O wins, 0 for a cat game,
0 for an unfinished game.
Returns the first "win" it finds, so check after each move.
Note that clever choices of X_token, O_token, Open_token
make this work better.
'''
for triad in WINNING_TRIADS:
triad_sum = board[triad[0]] + board[triad[1]] + board[triad[2]]
if triad_sum == 3 or triad_sum == -3:
return board[triad[0]] # Take advantage of "_token" values
return 0
def determine_move(board):
''' Determine Os next move. Check that a legal move remains before calling.
Randomly picks a single move from any group of moves with the same value.
'''
best_val = -2 # 1 less than min of O_token, X_token
my_moves = []
for move in SLOTS:
if board[move] == Open_token:
board[move] = O_token
val = board_valuation(board, X_token, O_token, -2, 2)
board[move] = Open_token
print "My move", move, "causes a", END_PHRASE[val]
if val > best_val:
best_val = val
my_moves = [move]
if val == best_val:
my_moves.append(move)
return random.choice(my_moves)
def recv_human_move(board):
''' Encapsulate human's input reception and validation.
Call with current board configuration. Returns
an int of value 0..8, the Human's move.
'''
looping = True
while looping:
try:
inp = input("Your move: ")
yrmv = int(inp)
if 0 <= yrmv <= 8:
if board[yrmv] == Open_token:
looping = False
else:
print "Spot already filled."
else:
print "Bad move, no donut."
except EOFError:
print
sys.exit(0)
except NameError:
print "Not 0-9, try again."
except SyntaxError:
print "Not 0-9, try again."
if looping:
print_board(board)
return yrmv
def usage(progname):
'''Call with name of program, to explain its usage.'''
print progname + ": Tic Tac Toe in python"
print "Usage:", progname, "[-h] [-c] [-r] [-x] [-X]"
print "Flags:"
print "-x, -X: print this usage message, then exit."
print "-h: human goes first (default)"
print "-c: computer goes first"
print "-r: computer is X, human is O"
print "The computer O and the human plays X by default."
def main():
'''Call without arguments from __main__ context.'''
try:
opts, args = getopt.getopt(sys.argv[1:], "chrxX",
["human", "computer", "help"])
except getopt.GetoptError:
# print help information and exit:
usage(sys.argv[0])
sys.exit(2)
next_move = HUMAN # Human goes first by default
for opt, arg in opts:
if opt == "-h":
next_move = HUMAN
if opt == "-c":
next_move = COMPUTER
if opt == "-r":
MARKERS[-1] = 'O'
MARKERS[1] = 'X'
if opt in ("-x", "-X", "--help"):
usage(sys.argv[0])
sys.exit(1)
# Initial state of board: all open spots.
board = [Open_token, Open_token, Open_token, Open_token, Open_token,
Open_token, Open_token, Open_token, Open_token]
# State machine to decide who goes next, and when the game ends.
# This allows letting computer or human go first.
while legal_move_left(board) and winner(board) == Open_token:
print
print_board(board)
if next_move == HUMAN and legal_move_left(board):
humanmv = recv_human_move(board)
board[humanmv] = X_token
next_move = COMPUTER
if next_move == COMPUTER and legal_move_left(board):
mymv = determine_move(board)
print "I choose", mymv
board[mymv] = O_token
next_move = HUMAN
print_board(board)
# Final board state/winner and congratulatory output.
try:
# "You won" should never appear on output: the program
# should always at least draw.
print ["Cat got the game", "I won", "You won"][winner(board)]
except IndexError:
print "Really bad error, winner is", winner(board)
sys.exit(0)
#-------
if __name__ == '__main__':
try:
main()
except KeyboardInterrupt:
print
sys.exit(1)
㈦ 求αβ剪枝算法应用于五子棋中,急!!!
int ab(int n,int a,int b)
{
int temp;
if(n<=0)
return (评价函数); /*评价函数*/
for(每一个走法)
{
（产生节点函数）；
temp=-ab(n-1,-b,-a);
(撤消产生的节点函数);
if(temp>a)
a=temp;(此处可保留搜索的最佳位置)
if(a>b)
break;
}
return a;
}
㈧ 剪枝算法怎么弄 大数取模
α-β剪枝技术
首先分析极小极大分析法效率，上述的极小极大分析法，实际是先生成一棵博弈树，然后再计算其倒推值，至使极小极大分析法效率较低。于是在极小极大分析法的基础上提出了α-β剪枝技术。
α-β剪枝技术的基本思想或算法是，边生成博弈树边计算评估各节点的倒推值，并且根据评估出的倒推值范围，及时停止扩展那些已无必要再扩展的子节点，即相当于剪去了博弈树上的一些分枝，从而节约了机器开销，提高了搜索效率。具体的剪枝方法如下：
(1) 对于一个与节点MIN，若能估计出其倒推值的上确界β，并且这个β值不大于 MIN的父节点(一定是或节点)的估计倒推值的下确界α，即α≥β，则就不必再扩展该 MIN节点的其余子节点了(因为这些节点的估值对MIN父节点的倒推值已无任何影响 了)。这一过程称为α剪枝。
(2) 对于一个或节点MAX，若能估计出其倒推值的下确界α，并且这个α值不小于 MAX的父节点(一定是与节点)的估计倒推值的上确界β，即α≥β，则就不必再扩展该MAX节点的其余子节点了(因为这些节点的估值对MAX父节点的倒推值已无任何影响 了)。这一过程称为β剪枝。
㈨ 在AlphaBeta剪枝的方法中,对树进行分析的+顺序包括
摘要 AlphaBeta剪枝算法是一个搜索算法旨在减少在其搜索树中，被极大极小算法评估的节点数。
㈩ 博弈算法里的剪枝怎么用（具体的）
极大极小过程，以及阿尔法-贝塔剪纸。极小极大搜索方法是博弈树搜索的基本方法，现在博弈树搜索中最常用的α-β剪枝搜索方法，就是从这一方法发展而来的。
首先假定，有一个评价函数可以对所有的棋局进行评估。当评价函数值大于0时，表示棋局对我方有利，对对方不利。当评价函数小于0时，表示棋局对我方不利，对对方有利。而评价函数值越大，表示对我方越有利。当评价函数值等于正无穷大时，表示我方必胜。评价函数值越小，表示对我方越不利。当评价函数值等于负无穷大时，表示对方必胜。假设双方都是对弈高手，在只看一步棋的情况下，我方一定走评价函数值最大的一步棋，而对方一定走评价函数值最小的一步棋。会下棋的读者都知道，在只看一步的情况下最好的棋，从全局来说不一定就好，还可能很不好。因此为了走出好棋，必须多看几步，从多种可能状态中选择一步好棋。
想一想人是如何下棋的呢？人实际上采用的是一种试探性的方法。首先假定走了一步棋，看对方会有那些应法，然后再根据对方的每一种应法，看我方是否有好的回应......这一过程一直进行下去，直到若干步以后，找到了一个满意的走法为止。初学者可能只能看一、两个轮次，而高手则可以看几个，甚至十几个轮次。
极小极大搜索方法，模拟的就是人的这样一种思维过程。当轮到我方走棋时，首先按照一定的搜索深度生成出给定深度d以内的所有状态，计算所有叶节点的评价函数值。然后从d-1层节点开始逆向计算：对于我方要走的节点（用MAX标记，称为极大节点）取其子节点中的最大值为该节点的值（因为我方总是选择对我方有利的棋）；对于对方要走的节点（用MIN标记，称为极小节点）取其子节点中的最小值为该节点的值（对方总是选择对我方不利的棋）。一直到计算出根节点的值为止。获得根节点取值的那一分枝，即为所选择的最佳走步。
在图3.5所示的例子中，假定搜索深度为2，D～J是7个叶节点，在它们下边括号中的数字是这些节点的评价函数值（假定可以计算得到）。A、B、C是三个极小节点，它们分别取各自子节点最小值为自己的值，得到三个节点的值分别为-6、-2和-4。s是极大节点，从A、B、C三个节点的值中取最大值，得到-2。由于-2来自于节点B，所以搜索的结果是应选择B作为我方的走步。对于我方来说，-2并不是一个好的结果，但却是在对方不犯错误的情况下，对我方最有利的结果。因为从图中可以看出，如果选择A为我方的走步，如果对方回应D的话，我方可以得到评价值9，固然对我方有利。但是如果对方是一个高手的话，他一定回选择E，而不是D。在这种情况下，我方只能得到-6，结果岂不是更差。因此，极小极大过程是一种假定对手每次回应都正确的情况下，如何从中找出对我方最有利的走步的搜索方法。
值得注意的是，不管设定的搜索深度是多少层，经过一次搜索以后，只决定了我方一步棋的走法。等到对方回应一步棋之后，需要在新的棋局下重新进行搜索，来决定下一步棋如何走。极小极大搜索策略是考虑双方对弈若干步之后，从可能的走步中选一步相对好棋的着法来走，即在有限的搜索深度范围内进行求解。为此要定义一个静态估计函数f，以便对棋局的势态（节点）作出优劣估值，这个函数可根据势态优劣特征来定义（主要用于对端节点的"价值"进行度量）。一般规定有利于MAX的势态，f（p）取正值，有利于MIN的势态，f（p）取负值，势均力敌的势态，f（p）取0值。若f（p）＝＋∞，则表示MAX赢，若f（p）＝－∞，则表示MIN赢。下面的讨论规定：顶节点深度d＝0，MAX代表程序方，MIN代表对手方，MAX先走。
图3.5是一个表示考虑两步棋的例子，图中端节点给出的数字是用静态函数f（p）计算得到，其他节点不用f（p）估计，因为不够精确，而应用倒推的办法取值。例如A、B、C是MIN走步的节点，MAX应考虑最坏的情况，故其估值应分别取其子节点f（p）估值中最小者，而s是MAX走步的节点，可考虑最好的情况，故估值应取A、B、C值中的最大者。这样求得f（s）＝－2，依此确定了相对较优的走步应是走向B，因为从B出发，对手不可能产生比f（s）＝－2更差的效果。实际上可根据资源条件，考虑更多层次的搜索过程，从而可得到更准确的倒推值，供MAX选取更正确的走步。当用端节点的静态估计函数f（p）求倒推值时，两位选手应采取不同的策略，从下往上逐层交替使用极小和极大的选值方法，故称极小极大过程。