1

我目前正在做一个任务来构建一个单词阶梯，通过一次只更改一个字母来从一个单词到另一个单词[当然，仍然保持它是一个真实的单词]。

我认为问题在于这种方法 - 通过使用广度优先搜索遍历树来找到两个单词之间的链接。我已经通过按照此处给出的描述实现了该算法，但是，在测试中给出的解决方案并不是最佳的。一个例子[它显然会错过sayer、payer和manor]：

Discovery: link found, 6 words
layer
sayer
payer
mayer
mayor
manor
major

理想的情况是：

Discovery: link found, 3 words
layer
mayer
mayor
major

我已经尝试调试此代码，但由于它涉及大量循环，因此尝试解决问题并不是一种非常可行的方法。

几点建议：

  • 它会在运行时生成图形 [connectionLink()]，从而节省时间。
  • 此方法所在的类将所有节点 [图中的点] 存储在哈希表中，键是单词，对象是单词的对象。

  • 一个节点存储一个它连接到的节点列表[通过不同的字符]，一个布尔值，表示它是否被访问过，并且单词本身作为一个字符串。

    /*
 *  @return     String      Returning a String listing words traversed to the goal
 *  @param      fW          First word
 *  @param      sW          Second word
 */
public String discovery(String fW,String sW){
    String result="Discovery: no link found";
    StringBuffer links=new StringBuffer();
    int i=0;

    Queue<Node> queue=new LinkedList<Node>();               //  Breadth first search uses a queue
    queue.add(hash.get(fW));                                //  Root of the tree, tree generated on the fly

    while(!queue.isEmpty()){
        Node current=(Node)queue.poll();
        if(!current.getVisited()){      
            current.setVisited(true);                       //  Making sure it's only cycled once

            if(current.getWord().equals(sW)){               //  Goal state
                while(current.getParent()!=null){           //  Generating the list words traversed
                    i++;
                    links.insert(0,"\n"+current.getParent().getWord());
                    current=current.getParent();
                }
                result="Discovery: link found, "+i+" words"+links.toString()+"\n"+sW;
                System.out.println(result);
                break;
            }
            else{
                connectionLink(current.getWord());              //  Finding connections

                for(Node node:current.getConnections()){        //  Getting the connections of the Node
                    if(!node.getVisited()){                     //  If child Node isn't visited, add to queue
                        node.setParent(current);                //  Sets parent as Node just left
                        queue.add(node);                        //  Adding Node to queue
                        //  System.out.println("Discovery: adding "+node.getWord()+" to queue. Child of "+node.getParent().getWord());
                        //  System.out.println("Discovery: current queue - "+queue.toString());
                    }
                }
            }
        }
    }
    clearVisited();
    return result;
}

节点 [也有标准的 getter 和设置]：

public class Node{
    private String word;                    //  The data of the Node
    private Node parent;
    private LinkedList<Node> children;  //  Holds children
    private boolean visited=false;


    public Node(String word){
        this.word=word.toLowerCase();
        children=new LinkedList<Node>();
    }

    /*
     *  @param      other       Connecting to another Node - adding a child
     */
    public void connectTo(Node other){
        if(!(children.contains(other))&&!(this==other))     children.add(other);    
    }

}

生成连接的方法，其中 wordDifference 是一种检查单词是否在字母上不同的方法，根据该测试返回一个布尔值：

/*
 *  @param      fW          Finding the links of the inputted String
 */
public void connectionLink(String fW){
    //  dKS=discoveryKeys enum, dK=discoveryKey
    Enumeration<String> dKS=hash.keys();
    while(dKS.hasMoreElements()){               //  Loop checks the word against every other word
        String dK2=dKS.nextElement();
        if(wordDifference(hash.get(fW),hash.get(dK2))){
            (hash.get(fW)).connectTo(hash.get(dK2));
            //  System.out.println("Linking: "+hash.get(fW).getWord()+" & "+hash.get(dK2).getWord());
        }
    }
}

任何帮助是极大的赞赏。这段代码实际上可能没有任何问题，问题可能出在其他地方，但在此先感谢。

主要问题是这并没有产生最佳的[最短路径]结果-它通过不必要的单词来达到目标​​[如示例中所示]，我的广度优先搜索的实现有什么问题[如那应该是最优的]？

4

0 回答 0