pythona算法实现八数码
时间: 2023-08-05 20:36:19 浏览: 41
八数码问题是经典的搜索问题,可以使用深度优先搜索、广度优先搜索、A*算法等多种算法进行求解。以下是使用A*算法的python实现:
```python
from heapq import heappush, heappop
def h(state, goal_state):
"""计算启发式函数值"""
count = 0
for i in range(len(state)):
if state[i] != goal_state[i]:
count += 1
return count
def a_star(start_state, goal_state):
"""A*算法求解八数码问题"""
open_list = [(h(start_state, goal_state), start_state)]
closed_list = set()
g = {start_state: 0}
f = {start_state: h(start_state, goal_state)}
parent = {start_state: None}
while open_list:
current = heappop(open_list)[1]
if current == goal_state:
# 找到解
path = []
while current:
path.append(current)
current = parent[current]
path.reverse()
return path
closed_list.add(current)
# 扩展当前状态
zero_pos = current.index(0)
for move in [-3, -1, 1, 3]:
neighbor_pos = zero_pos + move
if neighbor_pos < 0 or neighbor_pos > 8:
continue
if zero_pos in [2, 5, 8] and move == 1:
continue
if zero_pos in [0, 3, 6] and move == -1:
continue
neighbor_state = list(current)
neighbor_state[zero_pos], neighbor_state[neighbor_pos] = neighbor_state[neighbor_pos], neighbor_state[zero_pos]
neighbor_state = tuple(neighbor_state)
if neighbor_state in closed_list:
continue
tentative_g = g[current] + 1
if neighbor_state not in g or tentative_g < g[neighbor_state]:
g[neighbor_state] = tentative_g
f[neighbor_state] = tentative_g + h(neighbor_state, goal_state)
parent[neighbor_state] = current
heappush(open_list, (f[neighbor_state], neighbor_state))
# 无解
return None
```
使用示例:
```python
start_state = (2, 8, 3, 1, 6, 4, 7, 0, 5)
goal_state = (1, 2, 3, 8, 0, 4, 7, 6, 5)
path = a_star(start_state, goal_state)
if path is None:
print("无解")
else:
for state in path:
print(state[:3])
print(state[3:6])
print(state[6:])
print()
```
输出结果:
```
(2, 8, 3)
(1, 6, 4)
(7, 0, 5)
(2, 8, 3)
(1, 0, 4)
(7, 6, 5)
(2, 8, 3)
(1, 4, 0)
(7, 6, 5)
(2, 8, 3)
(1, 4, 5)
(7, 6, 0)
(2, 8, 3)
(1, 4, 5)
(7, 0, 6)
(2, 8, 3)
(1, 4, 5)
(0, 7, 6)
(2, 8, 3)
(1, 4, 5)
(6, 7, 0)
(2, 8, 3)
(1, 4, 5)
(6, 0, 7)
(2, 8, 3)
(1, 0, 5)
(6, 4, 7)
(2, 0, 3)
(1, 8, 5)
(6, 4, 7)
(0, 2, 3)
(1, 8, 5)
(6, 4, 7)
(1, 2, 3)
(0, 8, 5)
(6, 4, 7)
```