1

私は現在、一度に 1 文字だけを変更することによって単語から別の単語に移動する単語のはしごを構築する課題に取り組んでいます [もちろん、実際の単語であることは維持しています]。

問題はこの方法にあると思います-幅優先探索を使用してツリーをトラバースすることにより、2つの単語間のリンクを見つけます。hereの説明を真似てアルゴリズムを実装しましたが、テストで得られるソリューションは最適ではありません。例 [言う人、支払う人、マナーを明らかに見逃す可能性があります]:

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

理想的なシナリオは次のとおりです。

Discovery: link found, 3 words
layer
mayer
mayor
major

このコードのデバッグを試みましたが、多くのループが含まれているため、問題を解決する方法としてはあまり現実的ではありません。

いくつかの指針：

  • [connectionLink()] の進行に合わせてグラフを生成し、時間を節約します。
  • このメソッドが含まれるクラスは、すべてのノード [グラフ内のポイント] を Hashtable に格納します。キーは単語であり、オブジェクトは単語のオブジェクトです。

  • Node は、接続されている Node のリスト、訪問されたかどうかのブール値、および文字列としての単語自体を格納します。

    /*
 *  @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;
}

ノード[標準のゲッターと設定もあります]:

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