Hướng dẫn 8-puzzle python - Con trăn 8 câu đố
|
Show
Mã khác ShareCode.vn Cộng đồng chia sẻ và download source code
[Mã code 8619]8619]
Danh mục Thể loại Nhóm code Ngày đăng 24-1-2017 Loại file Full code Dung lượng 2.43 KB Source code 8 puzzle game with AI sử dụng giải thuật tìm kiếm A* viết bằng pulython phù hợp cho bạn tham khảoMÔ TẢ CHI TIẾT source code 8 puzzle game with AI sử dụng giải thuật tìm kiếm A* viết bằng pulython phù hợp cho bạn tham khảo Nguồn: Sharecode.vn HƯỚNG DẪN CÀI ĐẶT CODE GẦN GIỐNGCODE GỢI Ý CHO BẠNBÌNH LUẬNĐÁNH GIÁ1 Đánh giá Code rất tốt (1)(1) Code tốt (0)(0) Code rất hay (0)(0) Code hay (0)(0) Bình thường (0)(0) Thành viên Nội dung đánh giá Code rất tốtCode rất tốt và phù hợp để phát triển  BẠN HÃY MUA CODE QUA SHARECODE.VN ĐỂ ĐƯỢC BẢO VỆSHARECODE.VN ĐỂ ĐƯỢC BẢO VỆ NGƯỜI ĐĂNG
Coder Miễn phí 52 CodeCó phí 326 Code52 Code Giải câu đố trượt bằng thuật toán AI cơ bản. Tôi đã xuất bản bài viết này trên Medium vào tháng 9 năm 2018. Tôi đã quyết định tạo thêm nội dung trên hồ sơ LinkedIn của mình, do đó viết lại bài viết này. Hãy để bắt đầu với những gì tôi có nghĩa là một vấn đề của một trò chơi 8 trò chơi.Câu đố N hoặc câu đố trượt là một câu đố phổ biến bao gồm n gạch trong đó n có thể là 8, 15, 24, v.v. Trong ví dụ của chúng tôi n = 8. Câu đố được chia thành các cột SQRT (N+1) và các cột SQRT (N+1). Ví dụ. 15 trò chơi sẽ có 4 hàng và 4 cột và một chiếc 8-Puolle sẽ có 3 hàng và 3 cột. Câu đố bao gồm N gạch và một không gian trống nơi gạch có thể được di chuyển. Cấu hình bắt đầu và mục tiêu (còn được gọi là trạng thái) của câu đố được cung cấp. Câu đố có thể được giải quyết bằng cách di chuyển từng viên một trong không gian trống duy nhất và do đó đạt được cấu hình mục tiêu.sliding puzzle is a popular puzzle that consists of N tiles where N can be 8, 15, 24 and so on. In our example N = 8. The puzzle is divided into sqrt(N+1) rows and sqrt(N+1) columns. Eg. 15-Puzzle will have 4 rows and 4 columns and an 8-Puzzle will have 3 rows and 3 columns. The puzzle consists of N tiles and one empty space where the tiles can be moved. Start and Goal configurations (also called state) of the puzzle are provided. The puzzle can be solved by moving the tiles one by one in the single empty space and thus achieving the Goal configuration. Các gạch ở trạng thái ban đầu (bắt đầu) có thể được di chuyển trong không gian trống theo một thứ tự cụ thể và do đó đạt được trạng thái mục tiêu. Các quy tắc để giải quyết & nbsp; câu đố.Thay vì di chuyển gạch trong không gian trống, chúng ta có thể hình dung việc di chuyển không gian trống thay cho gạch, về cơ bản hoán đổi gạch với không gian trống. Không gian trống chỉ có thể di chuyển theo bốn hướng viz., 1. Lên 2.Down 3. Phải hoặc 4. Trái Không gian trống không thể di chuyển theo đường chéo và chỉ có thể thực hiện một bước tại một thời điểm (nghĩa là di chuyển không gian trống một vị trí tại một thời điểm).only one step at a time (i.e. move the empty space one position at a time). Bạn có thể đọc thêm về việc giải quyết vấn đề 8 trò chơi ở đây. Trước khi chúng ta nói về thuật toán*, chúng ta cần thảo luận về tìm kiếm heuristic.Về cơ bản, có hai loại kỹ thuật tìm kiếm & nbsp ;: 1. Tìm kiếm không hiểu biết vàUninformed Search and 2. Tìm kiếm thông tinInformed Search Bạn có thể đã nghe nói về tìm kiếm tuyến tính, tìm kiếm nhị phân, tìm kiếm độ sâu đầu tiên hoặc tìm kiếm đầu tiên trên chiều rộng. Các thuật toán tìm kiếm này rơi vào danh mục các kỹ thuật tìm kiếm không xác định, tức là các thuật toán này không biết gì về những gì chúng đang tìm kiếm và nơi chúng nên tìm kiếm nó. Đó là lý do tại sao cái tên tìm kiếm không xác định. Việc tìm kiếm không hiểu biết mất rất nhiều thời gian để tìm kiếm vì nó không biết nơi để đi đến đâu và cơ hội tốt nhất để tìm ra yếu tố này. Tìm kiếm thông tin hoàn toàn trái ngược với tìm kiếm không có thông tin. Trong đó, thuật toán nhận thức được cơ hội tốt nhất để tìm ra yếu tố và thuật toán đầu theo cách đó! Tìm kiếm heuristic là một kỹ thuật tìm kiếm thông tin. Một giá trị heuristic cho thuật toán con đường nào sẽ cung cấp giải pháp càng sớm càng tốt. Chức năng heuristic được sử dụng để tạo ra giá trị heuristic này. Các chức năng heuristic khác nhau có thể được thiết kế tùy thuộc vào vấn đề tìm kiếm. Vì vậy, chúng tôi có thể kết luận rằng tìm kiếm heuristic là một kỹ thuật sử dụng giá trị heuristic để tối ưu hóa việc tìm kiếm.Heuristic search is an informed search technique. A heuristic value tells the algorithm which path will provide the solution as early as possible. The heuristic function is used to generate this heuristic value. Different heuristic functions can be designed depending on the searching problem. So we can conclude that Heuristic search is a technique that uses a heuristic value for optimizing the search. Một* thuật toánA* là một thuật toán máy tính được sử dụng rộng rãi trong việc dẫn đường và truyền hình đồ thị, quá trình vẽ một đường dẫn có thể đi qua hiệu quả giữa nhiều điểm, được gọi là các nút. Được ghi nhận về hiệu suất và độ chính xác của nó, nó thích sử dụng rộng rãi. Tính năng chính của thuật toán A* là nó theo dõi từng nút được truy cập giúp bỏ qua các nút đã được truy cập, tiết kiệm một lượng lớn thời gian. Nó cũng có một danh sách chứa tất cả các nút còn lại để được khám phá và nó chọn nút tối ưu nhất từ danh sách này, do đó tiết kiệm thời gian không khám phá các nút không cần thiết hoặc ít tối ưu hơn. Vì vậy, chúng tôi sử dụng hai danh sách là 'danh sách mở' và 'danh sách đóng' Danh sách mở chứa tất cả các nút đang được tạo và không tồn tại trong danh sách đóng và mỗi nút được khám phá sau khi các nút lân cận được phát hiện Và những người hàng xóm được đưa vào danh sách mở Đây là cách các nút mở rộng. Mỗi nút có một con trỏ đến cha mẹ của nó để tại bất kỳ điểm nào, nó có thể lấy lại đường dẫn đến cha mẹ. Ban đầu, danh sách mở giữ nút bắt đầu (ban đầu). Nút tiếp theo được chọn từ danh sách mở dựa trên điểm F của nó, nút có điểm F ít nhất được chọn và khám phá.f score, the node with the least f score is picked up and explored. f-score = h-score + g-score A* sử dụng kết hợp giá trị heuristic (điểm H: Nút mục tiêu bao xa) cũng như điểm G (nghĩa là số lượng nút đi từ nút bắt đầu đến nút hiện tại). Trong vấn đề 8 hình chữ nhật của chúng tôi, chúng tôi có thể định nghĩa điểm H là số lượng gạch bị đặt sai bằng cách so sánh trạng thái hiện tại và trạng thái mục tiêu hoặc tổng kết khoảng cách Manhattan giữa các nút bị đặt sai.h-score as the number of misplaced tiles by comparing the current state and the goal state or summation of the Manhattan distance between misplaced nodes. G-Score sẽ vẫn còn khi số lượng nút đi qua nút bắt đầu để đến nút hiện tại. will remain as the number of nodes traversed from start node to get to the current node. Từ Hình 1, chúng ta có thể tính toán điểm H bằng cách so sánh trạng thái và trạng thái mục tiêu ban đầu (hiện tại) và đếm số lượng gạch không đặt sai.h-score by comparing the initial(current) state and goal state and counting the number of misplaced tiles. Do đó, h-score = 5 và g-score = 0 khi số lượng nút đi từ nút bắt đầu đến nút hiện tại là 0.h-score = 5 and g-score = 0 as the number of nodes traversed from the start node to the current node is 0. Làm thế nào a* giải quyết 8-puzz & nbsp; vấn đề.Trước tiên, chúng tôi di chuyển không gian trống theo tất cả các hướng có thể ở trạng thái bắt đầu và tính toán điểm F cho mỗi trạng thái. Điều này được gọi là mở rộng trạng thái hiện tại.f-score for each state. This is called expanding the current state. Sau khi mở rộng trạng thái hiện tại, nó được đẩy vào danh sách đóng và các trạng thái mới được tạo ra được đẩy vào danh sách mở. Một trạng thái có điểm F ít nhất được chọn và mở rộng lại. Quá trình này tiếp tục cho đến khi trạng thái mục tiêu xảy ra như là trạng thái hiện tại. Về cơ bản, ở đây chúng tôi đang cung cấp cho thuật toán một biện pháp để chọn hành động của nó. Thuật toán chọn hành động tốt nhất có thể và tiến hành trong đường dẫn đó. & Nbsp;closed list and the newly generated states are pushed into the open list. A state with the least f-score is selected and expanded again. This process continues until the goal state occurs as the current state. Basically, here we are providing the algorithm a measure to choose its actions. The algorithm chooses the best possible action and proceeds in that path. Điều này giải quyết vấn đề tạo trạng thái trẻ em dư thừa, vì thuật toán sẽ mở rộng nút với điểm F ít nhất.f-score. Việc thực hiện N-Puzz trong & NBSP; PythonTôi đã sử dụng hai lớp trong mã của mình: Node & Puzzle. Lớp nút xác định cấu trúc của trạng thái (cấu hình) và cũng cung cấp các chức năng để di chuyển không gian trống và tạo trạng thái con từ trạng thái hiện tại. Lớp Puzzle chấp nhận trạng thái ban đầu và mục tiêu của bài toán N-Guzle và cung cấp các chức năng để tính toán điểm F của bất kỳ nút nào (trạng thái).f-score of any given node(state). """
Author : Ajinkya Sonawane
"""
class Node:
def __init__(self,data,level,fval):
""" Initialize the node with the data, level of the node and the calculated fvalue """
self.data = data
self.level = level
self.fval = fval
def generate_child(self):
""" Generate child nodes from the given node by moving the blank space
either in the four directions {up,down,left,right} """
x,y = self.find(self.data,'_')
""" val_list contains position values for moving the blank space in either of
the 4 directions [up,down,left,right] respectively. """
val_list = [[x,y-1],[x,y+1],[x-1,y],[x+1,y]]
children = []
for i in val_list:
child = self.shuffle(self.data,x,y,i[0],i[1])
if child is not None:
child_node = Node(child,self.level+1,0)
children.append(child_node)
return children
def shuffle(self,puz,x1,y1,x2,y2):
""" Move the blank space in the given direction and if the position value are out
of limits the return None """
if x2 >= 0 and x2 < len(self.data) and y2 >= 0 and y2 < len(self.data):
temp_puz = []
temp_puz = self.copy(puz)
temp = temp_puz[x2][y2]
temp_puz[x2][y2] = temp_puz[x1][y1]
temp_puz[x1][y1] = temp
return temp_puz
else:
return None
def copy(self,root):
""" Copy function to create a similar matrix of the given node"""
temp = []
for i in root:
t = []
for j in i:
t.append(j)
temp.append(t)
return temp
def find(self,puz,x):
""" Specifically used to find the position of the blank space """
for i in range(0,len(self.data)):
for j in range(0,len(self.data)):
if puz[i][j] == x:
return i,j
class Puzzle:
def __init__(self,size):
""" Initialize the puzzle size by the specified size,open and closed lists to empty """
self.n = size
self.open = []
self.closed = []
def accept(self):
""" Accepts the puzzle from the user """
puz = []
for i in range(0,self.n):
temp = input().split(" ")
puz.append(temp)
return puz
def f(self,start,goal):
""" Heuristic Function to calculate hueristic value f(x) = h(x) + g(x) """
return self.h(start.data,goal)+start.level
def h(self,start,goal):
""" Calculates the different between the given puzzles """
temp = 0
for i in range(0,self.n):
for j in range(0,self.n):
if start[i][j] != goal[i][j] and start[i][j] != '_':
temp += 1
return temp
def process(self):
""" Accept Start and Goal Puzzle state"""
print("Enter the start state matrix \n")
start = self.accept()
print("Enter the goal state matrix \n")
goal = self.accept()
start = Node(start,0,0)
start.fval = self.f(start,goal)
""" Put the start node in the open list"""
self.open.append(start)
print("\n\n")
while True:
cur = self.open[0]
print("")
print(" | ")
print(" | ")
print(" \\\'/ \n")
for i in cur.data:
for j in i:
print(j,end=" ")
print("")
""" If the difference between current and goal node is 0 we have reached the goal node"""
if(self.h(cur.data,goal) == 0):
break
for i in cur.generate_child():
i.fval = self.f(i,goal)
self.open.append(i)
self.closed.append(cur)
del self.open[0]
""" sort the opne list based on f value """
self.open.sort(key = lambda x:x.fval,reverse=False)
puz = Puzzle(3)
puz.process()
Đây là một hướng dẫn thực sự đơn giản về việc giải quyết vấn đề N Puzzle bằng cách sử dụng thuật toán* trong Python. Tôi hy vọng bài viết này là hữu ích, thích và chia sẻ nó nếu bạn thích nó. |
