I keep calculating (manual) for h(n) as manhattan distance to check, but I think some steps are wrong. The example, there are 2 values of f (20 and 12). the code is choosing 20 instead 12 (cause from what I learn, manhattan distance is for lower f value).
code (python):
#direction matrix
DIRECTIONS = {"U": [-1, 0], "D": [1, 0], "L": [0, -1], "R": [0, 1]}
#target matrix
END = [[1, 2, 3], [4, 5, 6], [7, 8, 0]]
left_down_angle="\u2514"
right_down_angle="\u2518"
right_up_angle="\u2510"
left_up_angle="\u250C"
middle_junction = '\u253C'
top_junction = '\u252C'
bottom_junction = '\u2534'
right_junction = '\u2524'
left_junction = '\u251C'
#bar color
bar = Style.BRIGHT + Fore.CYAN + '\u2502' + Fore.RESET + Style.RESET_ALL
dash="\u2500"
#Line draw code
first_line = Style.BRIGHT + Fore.CYAN + left_up_angle + dash + dash + dash + top_junction + dash + dash + dash + top_junction + dash + dash + dash + right_up_angle + Fore.RESET + Style.RESET_ALL
middle_line = Style.BRIGHT + Fore.CYAN + left_junction + dash + dash + dash + middle_junction + dash + dash + dash + middle_junction + dash + dash + dash + right_junction + Fore.RESET + Style.RESET_ALL
last_line = Style.BRIGHT + Fore.CYAN + left_down_angle + dash + dash + dash + bottom_junction + dash + dash + dash + bottom_junction + dash + dash + dash + right_down_angle + Fore.RESET + Style.RESET_ALL
def print_puzzle(array):
print(first_line)
for a in range(len(array)):
for i in array[a]:
if i == 0:
print(bar, Back.RED + ' ' + Back.RESET, end=' ')
else:
print(bar, i, end=' ')
print(bar)
if a == 2:
print(last_line)
else:
print(middle_line)
#it is the node which store each state of puzzle
class Node:
def __init__(self, current_node, previous_node, g, h, dir):
self.current_node = current_node
self.previous_node = previous_node
self.g = g
self.h = h
self.dir = dir
def f(self):
return self.g + self.h
def get_pos(current_state, element):
for row in range(len(current_state)):
if element in current_state[row]:
return (row, current_state[row].index(element))
def manhattanCost(current_state):
cost = 0
for row in range(len(current_state)):
for col in range(len(current_state[0])):
pos = get_pos(END, current_state[row][col])
cost += abs(row - pos[0]) + abs(col - pos[1])
return cost
#get adjucent Nodes
def getAdjNode(node):
listNode = []
emptyPos = get_pos(node.current_node, 0)
for dir in DIRECTIONS.keys():
newPos = (emptyPos[0] + DIRECTIONS[dir][0], emptyPos[1] + DIRECTIONS[dir][1])
if 0 <= newPos[0] < len(node.current_node) and 0 <= newPos[1] < len(node.current_node[0]):
newState = deepcopy(node.current_node)
newState[emptyPos[0]][emptyPos[1]] = node.current_node[newPos[0]][newPos[1]]
newState[newPos[0]][newPos[1]] = 0
# listNode += [Node(newState, node.current_node, node.g + 1, manhattanCost(newState), dir)]
listNode.append(Node(newState, node.current_node, node.g + 1, manhattanCost(newState), dir))
return listNode
def getBestNode(openSet):
firstIter = True
bestF = float('inf') # Initialize bestF
for node in openSet.values():
if firstIter or node.f() < bestF:
firstIter = False
bestNode = node
bestF = bestNode.f()
return bestNode
def buildPath(closedSet):
node = closedSet[str(END)]
branch = list()
while node.dir:
branch.append({
'dir': node.dir,
'node': node.current_node
})
node = closedSet[str(node.previous_node)]
branch.append({
'dir': '',
'node': node.current_node
})
branch.reverse()
return branch
def main(puzzle):
open_set = {str(puzzle): Node(puzzle, puzzle, 0, manhattanCost(puzzle), "")}
closed_set = {}
while True:
test_node = getBestNode(open_set)
closed_set[str(test_node.current_node)] = test_node
if test_node.current_node == END:
return buildPath(closed_set)
adj_node = getAdjNode(test_node)
for node in adj_node:
if str(node.current_node) in closed_set.keys() or (str(node.current_node) in open_set.keys() and open_set[str(node.current_node)].f() < node.f()):
continue
open_set[str(node.current_node)] = node
del open_set[str(test_node.current_node)]
if __name__ == '__main__':
#it is start matrix
br = main([[7, 2, 8],
[1, 3, 4],
[0, 5, 6]])
print('total steps : ', len(br) - 1)
print()
print(dash + dash + right_junction, "INPUT", left_junction + dash + dash)
for b in br:
if b['dir'] != '':
letter=""
if b['dir'] == 'U':
letter="UP"
elif b['dir'] == 'R':
letter = "RIGHT"
elif b['dir'] == 'L':
letter="LEFT"
elif b['dir'] == 'D':
letter="DOWN"
print(dash + dash + right_junction, letter, left_junction + dash + dash)
print_puzzle(b['node'])
print()
print(dash + dash + right_junction, 'ABOVE IS THE OUTPUT', left_junction + dash + dash)
I’m trying to calculate using manhattan distance (like sum vertical and horizontal squares), but sometimes the output that given by the code is not matching with my calculating.
“sometimes the output that given by the code is not matching with my calculating.”: can you be concrete about which output and which calculation don’t match?