RBFS的8个拼图解决方案 [英] 8 puzzle Solution whit RBFS

问题描述

我想要一个解决8个拼图的RBFS的解决方案.请帮助我！

i want a solution for solving 8 puzzle whit RBFS.please help me!

推荐答案

您知道我们需要什么吗?真的，真的需要吗?

世界和平?会很好，但不太可能.

所有人都有公平的股份吗?再说一次，好主意.

西蒙·科维尔(Simon Cowel)制作的音乐还不错吗?现在你只是傻了.

一个可以查找您想知道的事情的互联网站点?那会很方便，但是在哪里可以找到这样的东西.


什么！最后一个存在！他们为什么不告诉任何人呢?那是黑烟?它叫Goggle或其他什么?好吧，我希望我对此有所了解！

搜索:拼图RBFS [ ^ ]

You know what we need? Really, really nead?

World Peace? Would be nice, but not that likely really.

Fair shares for all? Again, good idea.

Decent music produced by Simon Cowel? Now you''re just being silly.

An internet site that could look up thing you want to know about? That would be handy, but where would we find such a thing.


What! The last one exists! Why didn''t they tell anyone about it? What''s that Sooty? It''s called Goggle or something? Well, I wish I''d known about that!

Goggle look for: puzzle whit RBFS[^]

您应该做自己的作业，但我会给您一些提示.

您首先需要做的是定义板状态.假设数字0代表空白区域，数字1-8代表方块.

因此，我们将获得一个3x3 2D整数数组.

You should be doing your own homework, but I will give you some pointers.

What you first need to do is define a board state. Lets say the number 0 represents the empty space and numbers 1-8 represent the tiles.

So, we will have a 3x3 2D array of integers.

typedef struct {
	int Board[3][3];
} BoardState;

现在我们需要定义有效的动作.我们将它们分别称为上"，下"，左"和右"，这是我们将移动孔的相应方向.

Now we need to define valid moves. Lets call these Up, Down, Left and Right, which are the respective directions that we will move the hole.

typedef enum {
	Up,
	Down,
	Left,
	Right,
} Moves;

然后，您将需要定义函数以将每个移动应用到板上，并检查移动是否有效.你可以做到的.

You will then need to define functions to apply each move to the board and to check if a move is valid. You can do this.

bool IsMoveValid(const BoardState &Board, Moves move);
void MoveUp(const BoardState &OrigBoard, BoardState *pNewBoard);
void MoveDown(const BoardState &OrigBoard, BoardState *pNewBoard);
void MoveLeft(const BoardState &OrigBoard, BoardState *pNewBoard);
void MoveRight(const BoardState &OrigBoard, BoardState *pNewBoard);

现在您需要的是启动板.

Now what you need is a starting board.

BoardState board = {
	{ 0, 1, 2 },
	{ 3, 4, 5 },
	{ 6, 7, 8 },
};
MyTreeNode<boardstate> TreeRoot(board); //MyTree is a tree structure class that you have to write. This one is templated, and takes 1 parameter, which is the value stored at the root node.
</boardstate>

现在，我们需要以此为基础构建一棵树，其中包括我们可以采取的所有可能措施.
对于我的示例板上的第一种情况，这些动作将为Right和Down.我们将使用通用方法.

From this we now need to build a tree of all the possible moves we can make.
For the first case on my example board, these moves would be Right and Down. We will use a generic approach tho.

void GenerateChildren(const MyTreeNode &node) {
	BoardState temp;
	if (IsValidMove(node.board, Left)) {
		MoveLeft(node.board, temp);
		node.AddChild(new MyTreeNode(temp));
	}
	//Do the same for other directions
}

制作完树后，可以使用递归广度优先搜索(RBFS)在树中搜索解决方案的路径. RBFS首先穿过树，然后进入子树.
为此，您将需要(必须弄清楚顺序):
一个.检查当前节点，看是否可以解决
b.检查所有子节点，看看它们是否是解决方案


希望我给了您足够的信息，因此您现在就可以自己做，而无需给出所有答案.试试看(维基百科帮助).如果仍然遇到问题，请尝试重新尝试时返回代码.

Once we have a tree made, we can use a Recursive Breadth First Search (RBFS) to search it for the path to the solution. RBFS goes across the tree first, then into children.
To do this you will need to (you have to figure out the order):
a. Check the current node to see if it the solution
b. Check all child nodes to see if they are the solution


Hopefully I have given you enough so you can do it on your own now without giving you all the answers. Give it a try (Wikipedia helps). If you are still having trouble come back with code WHEN YOU HAVE TRIED SOMETHING.

这篇关于RBFS的8个拼图解决方案的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！