编写一个程序，使用无信息的搜索技术来解决河内塔楼问题:BFS，DFS和IDS. [英] Write a program to solve the Hanoi towers problem using uninformed search techniques: BFS, DFS and IDS.

问题描述

编写一个程序以使用不知情的搜索技术(BFS，DFS和IDS)解决河内塔楼问题.
我编写了三个dfs，ids，bfs和Hanoi塔的代码，但我不知道如何将其中一种技术与Hanoi塔问题结合使用.

这是我在这个不错的网站上遇到的第一个问题.
这是我在bfs中的代码:

Write a program to solve the Hanoi towers problem using uninformed search techniques: BFS, DFS and IDS.
I wrote the code of the three dfs, ids,bfs, and Hanoi Towers but I don''t know how to mix one of the techniques with Hanoi towers problem .

This my first question on this nice site.
Here is my code in bfs:

public void bfs()
{
    //BFS uses Queue 
    Queue q=new LinkedList();
    q.add(this.rootNode);
    printNode(this.rootNode);
    rootNode.visited=true;
    while(!q.isEmpty())
    {
        Node n=(Node)q.remove();
        Node child=null;
        while((child=getUnvisitedChildNode(n))!=null)
        {
            child.visited=true;
            printNode(child);
            q.add(child);
        }
    }
    //Clear visited property of nodes
    clearNodes();
}

对于河内来说:

And this for Hanoi:

public class Hanoi {
public static void hanoi(int n, String from, String temp,
String to) {
if (n == 0) return;
hanoi(n-1, from, to, temp);
System.out.println("Move disc " + n +
" from " + from + " to " + to);
hanoi(n-1, temp, from, to);
}
public static void main(String[] args) {
int N = Integer.parseInt(args[0]);
hanoi(N, "A", "B", "C");
}
}

我首先要做的是河内是所有可能解决方案的树
并让bfs跟踪Hanoi节点.

谢谢:)

I will do this first the Hanoi is the tree with all possible solutions
and make the bfs trace the Hanoi nodes.

Thank you :)

推荐答案

我的朋友，你在学校里会遇到一些严重的麻烦.

您不了解问题所在.用第一句话，您应该使用BFS，DFS和IDS算法找到解决河内塔问题的方法.

您显然以这种方式表示意思，按照Wikipedia针对Hanoi塔的条目所示执行递归解决方案，然后以某种方式试图弄清楚如何将不同的算法包括到其中.

据我所知，这是您应该做的.

假设您不知道解决问题的方法.您只知道自己有3个钉子，一次只能移动一张光盘，也不能将较大的光盘移动到较小的光盘上.

现在，实施广度优先搜索"算法以找到解决方案.

那么，您将如何做呢?问题是试图让您实现每种算法以找到解决方案.

对于BFS，该算法如何工作?好了，您从根节点开始.然后，您构建该根节点的子节点并将其作为邻居链接.因此，首先，您可以执行以下两个步骤:将顶部光盘移至中间或相对端.所以，看看第一个孩子.这样解决吗?如果不是，请看下一个孩子.这样解决吗?

如果没有一个孩子能解决此问题，请查看第一个孩子并添加它的孩子.看他们. Wikipedia的动画效果很好，可以显示要采取的步骤( Animated_BFS.gif [ ^ ])

因此，请实施此算法以解决该问题. BFS在建立子树之前对树一无所知.您无需构建整个树，然后搜索整个树.这就是为什么它被称为不知情的搜索.

我会帮你...如果你付钱的话.

You''re going to have some serious trouble in school my friend.

You''re not understanding the problem as it was given to you. By your first sentence, you''re supposed to find a solution the Tower of Hanoi problem using BFS, DFS, and IDS algorithms.

You apparently took that to mean, implement the recursive solution as shown on wikipedia''s entry for Tower of Hanoi and then you''re somehow trying to figure out how to include the different algorithms into it.

As far as I can tell, here is what you''re supposed to do.

Assume you have no knowledge of the way to solve the problem. You only know that you have 3 pegs, you can only move one disc at a time, and you cannot move a larger disc onto a smaller disc.

Now, implement the Breadth-First Search algorithm to find the solution.

So, how would you do that? The question is trying to get you to implement each algorithm to find the solution.

For BFS, how does the algorithm work? Well, you start with the root node. Then, you build the child nodes of that root node and link them as neighbors. So, to start, you have two moves that you can make...move the top disc to the middle, or to the opposite end. So, look at the first child. Does that solve it? If not, look at the next child. Does that solve it?

If none of the children solve it, look at the first child and add in it''s children. Look at them. Wikipedia has a good animation to show the steps to take (Animated_BFS.gif[^])

So, implement this algorithm to solve the problem. The BFS doesn''t know anything about the tree until it builds the children. You don''t build the whole tree and then search through it. That''s why it''s called an uninformed search.

I''ll do it for you...if you pay me.

每小时我的时间60听起来很合理.


[添加]
除此之外，如果您尝试重新创建路径，则广度优先搜索"会占用大量疯狂的内存.例如，如果树上有6个磁盘，则解决方案需要(2 ^ 6)-1个动作来求解或63个动作要求解.这意味着使用BFS搜索时，将有63个不同的级别...不包括根.

在第63层，这是一个非常荒谬的节点，如果您想遵循这条路，就必须跟踪所有内容.只是作为任意数量的磁盘的示例.

一开始有2个动作.
在第一个动作之后，有6个动作.
在第二步之后，有18步.

它的计算结果为0.9643e ^(1.0995((2 ^ x)-1)，其中x是磁盘数量.使用6个磁盘，总共有1.14 * 10 ^ 30个移动可跟踪.我用光了试图解决只有4个磁盘的问题的内存.

因此，祝您好运.

60 per hour of my time sounds reasonable.


[Added]
Just to add to this, a Breadth-First Search is crazy memory intensive if you are trying to re-create the path. For example, if there are 6 disks on the tree, the solution takes (2^6)-1 moves to solve or 63 moves to solve. That means that with a BFS search, there would be 63 different levels...not including the root.

It''s a ridiculous number of nodes at the 63rd level and if you want to be able to follow the path, you have to keep track of everything. Just as an example for any number of disks.

At the beginning, there are 2 moves.
After the 1st move, there are 6 moves.
After the 2nd move, there are 18 moves.

It works out to 0.9643e^(1.0995((2^x)-1) where x is the number of disks. With 6 disks, that''s a total of 1.14*10^30 moves to keep track of. I ran out of memory trying to solve a problem with only 4 disks.

So, good luck with that.

这不是一项家庭作业服务；没有人会为您做您的工作.

不要问请提供代码给..."，因为这表明您不是在试图帮助自己.您将获得的所有收入都将被忽略，滥用或被告知尝试使用rentacoder(它们使您为软件付费).

如果您有特定问题，请询问.人们会尝试提供帮助.

This is not a homework service; no-one here will do your work for you.

Do not ask "Please provide the code to ..." as it shows you are not trying to help yourself. All you will get is ignored, abused, or told to try rentacoder (where they make you pay for software).

If you have a specific problem, ask about it. People will try to help.

这篇关于编写一个程序，使用无信息的搜索技术来解决河内塔楼问题:BFS，DFS和IDS.的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！