㈠ 剪枝演算法和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）求倒推值時，兩位選手應採取不同的策略，從下往上逐層交替使用極小和極大的選值方法，故稱極小極大過程。