5

私はすでにこの問題に多くの労力を費やしており、本当に終わりに近づいています。全体的な目標は、ラダーの各「ラング」が前の単語とは 1 文字異なる 2 つの 5 文字の単語の間に最小長の単語ラダーを作成することでした。例えば：

[heads, heals, hells, halls, hails, tails]

プログラムは、最初と最後の単語、および必要なはしごの長さを入力する必要がある場所から開始し、プログラムはそれを解決する必要があります。私はすでにかなり進んでいるので、現在の状況を説明するために詳細の多くを割愛します.

たとえば、「babes」から「child」へと移行し、10 文字の単語のはしごを探しているとします。

私は何千もの単語のペアを持っています.2つのペアは互いに1つの文字が異なります. 以下はペアのほんの一部です。

[(bares, babes), (banes, babes), (bates, babes), (babel, babes), (bases, babes), (bales, babes)...] etc.

これは長い間続きますが、そこには目的の単語が存在し、最初の単語 (babes) と最後の単語 (child) の間にパスがあり、そのはしごが 10 単語であることが保証されています。長いです。

どうすればこれを達成できますか?

編集:私はすでにグラフを実装しており、BFS を使用して開始単語から終了単語に移動しています。

public List<T> minLengthPath(T src, T dest, int length) 
{
    T start = src;

    Deque<T> queue = new LinkedList<T>();                       //Holds items to visit
    Queue<List<T>> ladder = new LinkedList<List<T>>();      //Holds all the ladders?
    Set<T> checker = new HashSet<T>();                          //Holds visited items

    queue.add(start);
    checker.add(start);

    while(!queue.isEmpty()){
        T slot = queue.remove();
        if(slot.equals(dest)) 
        { 
            System.out.println(slot);
            return null;  //Should be returning ladder
        }
        Set<Pair<Integer, T>> thing = this.edges.get(slot);
        Set<T> edges = findEdges(thing);     //Returns the edges of the node

        Iterator<T> check = edges.iterator();
        for(int a = 0; a < edges.size(); a ++) 
        {
            T hole = check.next();
            if(!checker.contains(hole))
            {
                checker.add(hole);
                queue.add(hole);
            }
        }           
    }
    return null;
}
4

1 に答える 1

10

さて、あなたは最短経路問題として知られているグラフの問題を説明しています。

ここで、あなたのグラフはG = (V,E)、 どこV = { all words}、E = {(u,v) | there is a direct "ladder" from word u to word v}です。

この場合、グラフは重み付けされていないため、BFSを使用してソースからターゲットへの最短パスを見つけることができます。

ターゲットノードからの距離を評価する許容ヒューリスティック関数を見つけた後、A* アルゴリズムを使用することもできます。@trutheality で指摘されているように、考えられるヒューリスティック関数の 1 つは、一致しない文字の数です。

検索を開始する前にグラフ全体を実際に「作成」する必要はないことに注意してください。関数を使用して「オンザフライ」で生成できます。next(w) = { u | (w,u) is in E, or in other words - there is a direct ladder from w to u }

BFS を実行して最短経路の長さを見つけた後、遡ることによって正確な経路を見つけることもできます。このスレッドでは、この問題について詳しく説明しています。アイデアはマップを維持することです- キーは頂点であり、値はこの頂点がどのように発見されたかです - キーの発見につながった頂点です。BFS が完了したら、ターゲットからソースに戻るだけで、パスを取得できます。【逆はもちろん…】

于 2012-04-14T22:41:35.600 に答える