廣度優先搜索不起作用

我正在構建一個遊戲，在其中構建單詞（字典）的哈希表，然後從用戶處取兩個字符串和一個int。我嘗試將第一個字符串排列成第二個字符串。這是通過每次排列一個字母來完成的，並且將該新詞放入作爲孩子的樹結構中，該節點持有原始單詞。這樣做直到原始單詞成功排列到第二個單詞中，或者直到數字排列超出用戶給定的整數。在我的基本測試案例中，我給這個程序的貓和嬰兒牀和3跳。這不起作用。我已經嘗試了幾件事情，但在這一點上，我真的不知道更多，不能更具體。下面是代碼廣度優先搜索不起作用

public static void permute(HashTable dict, Queue<TNode> nodes, ArrayList<String> oldWords, String destination, int hops, int hopCounter) { 
    char[] alphabet = { 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', //array with every letter in the alphabet will be used for permutations 
      'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z' }; 
    Queue<TNode> nextGen = new Queue<TNode>(); //holds the deepest generation of nodes 
    TNode goalNode = null;//node to hold a successful node 
    hopCounter++; 
    boolean found = false; 
    while (!nodes.empty()) { 
     TNode parent = nodes.dequeue(); 
     oldWords.add(parent.getWord()); 
     for (int q = 0; q < parent.getWord().length(); q++) { 
      char oldLet = parent.getWord().charAt(q); 
      for (int i = 0; i < alphabet.length; i++) { 
       String test = parent.getWord().replace(oldLet, alphabet[i]); 
       if (dict.contains(test) && !oldWords.contains(test)) { 
        nextGen.enqueue(new TNode(test, parent, hopCounter)); 
        found = test.equals(destination); //determine if successful permutation 
        if (found) { 
         goalNode = new TNode(test); 
        } 
       } 

      } 
     } 
    } 

    if (hopCounter < hops && !found) { 
     permute(dict, nextGen, oldWords, destination, hops, hopCounter); 
    } else { 
     if (hopCounter == hops) { 
      System.out.println("Unable to permute to " + destination + " in " + hops + " hops."); 
     } else { //Successful, found = true 
      StringBuilder path = new StringBuilder(goalNode.getWord()); 
      TNode currentNode = goalNode.getParent(); 
      for (int i = goalNode.getDepth() - 1; i > 0; i--) { 
       path.insert(0, currentNode.getWord() + "==>"); 
      } 
      System.out.println("Successful!"); 
      System.out.println(path.toString()); 
     } 
    } 
}

一個TNODE很簡單，就是有一個字符串的指針，指向父和樹節點的深度int類型的節點。跳數是用戶給出的數字hopCounter保存當前跳數。傳遞的原始隊列與原始單詞保持一個節點。 oldWords包含所有已經創建的排列，所以我可以避免重複。

我可能會談論這一切都錯了，但沒有一個好方法來測試它是否會實際工作。如果有更好的方法來測試和調試循環運行多次，這將是有益的。我已經使用了調試器，但它們對此沒有幫助。任何幫助真的很感激！

來源

2014-12-06 Rostro

那麼，對於一個，parent.getWord().replace(oldLet, alphabet[i])取代的oldLet所有 OCCURENCES用不同字母，不只是在q位置。

此外，輸出結果時，您不更新currentNode。我喜歡寫東西

while (currentNode != null) { 
    path.insert(0, currentNode.getWord() + "==>"); 
    currentNode = currentNode.getParent(); 
}

這當然，假設根節點的父null。

作爲一個方面的評論，爲了表現的利益，我使用HashTable作爲oldWords，因爲ArrayList.contains是O（n）操作。

來源

2014-12-06 11:53:06

廣度優先搜索不起作用

回答

相關問題