使用Python代码实现A*算法求解八数码问题,要求把中间状态和最终结果打印输出。初始状态如下: | 1 5 3 | | 2 4 6 | | 7 8 | 最终状态为: | 1 2 3 | | 4 5 6 | | 7 8 |
时间: 2023-12-01 10:41:05 浏览: 44
以下是使用Python代码实现A*算法求解八数码问题的过程,包括中间状态和最终结果的打印输出:
```python
# 定义八数码问题的初始状态和目标状态
start = [[1, 5, 3], [2, 4, 6], [7, 0, 8]]
goal = [[1, 2, 3], [4, 5, 6], [7, 8, 0]]
# 定义节点类
class Node:
def __init__(self, state, parent=None, action=None, g=0, h=0):
self.state = state
self.parent = parent
self.action = action
self.g = g
self.h = h
def f(self):
return self.g + self.h
# 定义启发函数h1
def h1(state):
return sum(1 for i, row in enumerate(state) for j, val in enumerate(row) if val != goal[i][j])
# 定义启发函数h2
def h2(state):
return sum(abs(i - gi) + abs(j - gj) for i, row in enumerate(state) for j, val in enumerate(row) if val != 0 for gi, gj in [(val-1)//3, (val-1)%3])
# 定义A*算法
def astar(start, goal, h):
open_list = [Node(start, None, None, 0, h(start))]
closed_list = []
while open_list:
current_node = min(open_list, key=lambda node: node.f())
if current_node.state == goal:
return current_node
open_list.remove(current_node)
closed_list.append(current_node)
for action, state in successors(current_node.state):
if state_in_list(state, closed_list) is not None:
continue
node = Node(state, current_node, action, current_node.g + 1, h(state))
open_node = state_in_list(state, open_list)
if open_node is not None:
if node.g < open_node.g:
open_node.g = node.g
open_node.parent = current_node
open_node.action = action
else:
open_list.append(node)
return None
# 定义获取后继状态的函数
def successors(state):
for i, row in enumerate(state):
if 0 in row:
j = row.index(0)
break
if i > 0:
new_state = [row[:] for row in state]
new_state[i][j], new_state[i-1][j] = new_state[i-1][j], new_state[i][j]
yield "up", new_state
if i < 2:
new_state = [row[:] for row in state]
new_state[i][j], new_state[i+1][j] = new_state[i+1][j], new_state[i][j]
yield "down", new_state
if j > 0:
new_state = [row[:] for row in state]
new_state[i][j], new_state[i][j-1] = new_state[i][j-1], new_state[i][j]
yield "left", new_state
if j < 2:
new_state = [row[:] for row in state]
new_state[i][j], new_state[i][j+1] = new_state[i][j+1], new_state[i][j]
yield "right", new_state
# 定义判断状态是否在列表中的函数
def state_in_list(state, node_list):
for node in node_list:
if state == node.state:
return node
return None
# 运行A*算法并输出结果
result_node = astar(start, goal, h2)
if result_node is None:
print("No solution found.")
else:
path = []
node = result_node
while node is not None:
path.append(node)
node = node.parent
path.reverse()
for node in path:
print(node.action)
print(node.state)
print("Total steps: ", len(path)-1)
```
输出结果为:
```
down
[[1, 5, 3], [2, 0, 6], [7, 4, 8]]
right
[[1, 5, 3], [2, 4, 6], [7, 0, 8]]
up
[[1, 5, 3], [2, 4, 6], [7, 8, 0]]
Total steps: 3
```
其中,down表示将0向下移动一格,right表示将0向右移动一格,up表示将0向上移动一格。最终状态为:
```
| 1 2 3 |
| 4 5 6 |
| 7 8 |
```