matlab八数码问题代码
时间: 2023-05-17 10:01:15 浏览: 102
八数码问题,又称九宫问题,是一种简单的切入点搜索问题,常用于计算机算法的训练。问题通过确定每个拼图块的初始位置和目标位置来描述。在该问题中,每个拼图块都是由数字“1-8”和一个空格组成,目标是重新排列这些块,使其与目标位置匹配。下面是使用Matlab编写的八数码问题代码:
1. 建立八数码问题矩阵
digits = [2 8 3; 1 6 4; 7 0 5] %初始化第一个状态
goal = [1 2 3; 8 0 4; 7 6 5] %目标状态
2. 定义一个函数,生成一个包含当前状态和使该状态到达目标状态所需步骤的节点对象
function node = createnode(state, parent, cost, heuristic)
node.state = state;
node.parent = parent;
node.cost = cost;
node.heuristic = heuristic;
node.score = cost + heuristic;
end
3. 定义一个函数,计算当前状态到达目标状态的预计成本
function cost = manhattan_distance(state, goal)
cost = 0;
for i=1:3
for j=1:3
if(state(i,j) ~= 0)
x = find(goal == state(i,j));
cost = cost + abs(i - floor((x-1)/3)+1) + abs(j - mod(x-1,3)+1);
end
end
end
end
4. 定义一个搜索函数,用于搜索八数码问题的解决方案
function path = astar_search(start_state, goal_state)
start = createnode(start_state, [], 0, manhattan_distance(start_state, goal_state));
open = PriorityQueue();
open.insert(start, start.score);
closed = containers.Map('KeyType','double','ValueType','any');
count = 0;
while(~isempty(open))
count = count + 1;
curr = open.deletemin();
if(isequal(curr.state, goal_state))
path = reconstruct_path(curr);
return;
end
closed(num2str(curr.state)) = 1;
successors = expand_node(curr, goal_state);
for i=1:numel(successors)
state = successors{i}.state;
cost = curr.cost + 1;
heuristic = manhattan_distance(state, goal_state);
child = createnode(state, curr, cost, heuristic);
if(isKey(closed, num2str(state)))
continue;
end
if(~open.contains(child))
open.insert(child, child.score);
else
open.update(child, child.score);
end
end
end
path = [];
end
5. 创建一个函数,用于展开给定的节点并返回成功后继节点
function successors = expand_node(node, goal)
successors = {};
actions = {'up', 'down', 'left', 'right'};
[row, col] = find(node.state == 0);
for i=1:numel(actions)
if(can_move(node.state, actions{i}, row, col))
new_state = move(node.state, actions{i}, row, col);
cost = node.cost + 1;
heuristic = manhattan_distance(new_state, goal);
successors{end+1} = createnode(new_state, node, cost, heuristic);
end
end
end
6. 判断当前状态能否移动,如果可以,返回移动后的状态;否则,返回当前状态
function [new_state, success] = move(state, move, row, col)
success = true;
new_state = state;
switch move
case 'up'
if(row == 1)
success = false;
return;
end
new_state(row, col) = new_state(row-1, col);
new_state(row-1, col) = 0;
case 'down'
if(row == 3)
success = false;
return;
end
new_state(row, col) = new_state(row+1, col);
new_state(row+1, col) = 0;
case 'left'
if(col == 1)
success = false;
return;
end
new_state(row, col) = new_state(row, col-1);
new_state(row, col-1) = 0;
case 'right'
if(col == 3)
success = false;
return;
end
new_state(row, col) = new_state(row, col+1);
new_state(row, col+1) = 0;
end
end
7. 判断是否能够在给定方向上移动,如果可以,返回true;否则,返回false
function success = can_move(state, move, row, col)
success = true;
switch move
case 'up'
if(row == 1)
success = false;
end
case 'down'
if(row == 3)
success = false;
end
case 'left'
if(col == 1)
success = false;
end
case 'right'
if(col == 3)
success = false;
end
end
end
8. 定义一个函数,用于重构从起始状态到解的路径
function path = reconstruct_path(node)
path = [node.state];
while(~isempty(node.parent))
node = node.parent;
path = [node.state path];
end
end
最后调用搜索函数:
path = astar_search(digits, goal)