Algoritma Bidirectional A* N-Puzzle

Algoritma A* adalah suatu algoritma Best First Search yang menggabungkan Uniform Cost Search dan Greedy Best­Fit Search. Cost yang diperhitungkan didapat dari actual cost ditambah dengan heuristic cost. Dengan perhitungan cost seperti ini, algoritma A* adalah complete dan optimal.

Modifikasi dari algoritma A* adalah Bidirectional A*. Berbeda dengan A* dimana pencarian dilakukan pada satu arah, pada Bidirectional A* pencarian dilakukan pada dua arah, yaitu dari simpul asal dan simpul tujuan.

bi-directional

Oke, itu sekilas pembahasan tentang algoritma A* (A Star) Bi-directional.

Mari kita ke masalah yang akan kita tuju, N-Puzzle

Puzzle terdiri dari N kotak yang berisikan value dan satu ruang kosong di mana value bisa dipindahkan. Konfigurasi Start and Goal (juga disebut state) dari puzzle disediakan. 

Puzzle dapat dipecahkan dengan memindahkan value kotak satu per satu di ruang kosong dan dengan demikian mencapai konfigurasi Goal State.

Ste-up 8-Puzzle

Aturan untuk memecahkan teka-teki (Puzzle).

Ruang kosong hanya bisa bergerak dalam empat arah

  1. Up
  2. Down
  3. Right
  4. Left

Ruang kosong tidak dapat bergerak secara diagonal dan hanya dapat mengambil satu langkah pada satu waktu (yaitu memindahkan ruang kosong satu posisi pada suatu waktu).

f(n) = g(n) + h(n)

f(n) = total biaya
g(n) = biaya sebenarnya
h(n) = biaya perkiraaan

h-score = jumlah yang tidak mirip dengan goal state pada current state
g-score = level pencarian
f-score = h-score + g-score

Node berikutnya yang dipilih dari daftar terbuka didasarkan pada skor f-nya , simpul dengan skor f paling sedikit diambil dan dieksplorasi.

Lihat pada penjelasan jawaban digambar berikut, lebih mudah untuk dipahami.

Solved N-Puzzle

Berikut penjelasan secara lengkap by video:

N-Puzzle

Implementasi N-Puzzle dalam Python

Terdapat dua kelas : Node & Puzzle.
Kelas node mendefinisikan struktur state (konfigurasi) dan juga menyediakan fungsi untuk memindahkan ruang kosong dan menghasilkan status child dari state saat ini. 

Kelas puzzle menerima status awal dan tujuan dari masalah N-Puzzle dan menyediakan fungsi untuk menghitung skor-f dari setiap node (keadaan) yang diberikan.

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()

Output:

Output Program N-Puzzle

Leave a Reply

Your email address will not be published. Required fields are marked *

× Mau Merchandise? bisa, Chat WA yak