5

我已经在这个问题上做了很多工作，并且真的接近尾声。总体目标是在两个五个字母的单词之间创建最小长度的单词阶梯，其中阶梯的每个“梯级”与前一个单词不同一个字母。例如：

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

程序从你必须输入一个开始和结束字以及你想要的梯子的长度开始，程序必须解决它。我已经走得很远了，所以我会省略很多细节来解释我目前的情况。

假设我要从“宝贝”到“孩子”，我正在寻找一个 10 个字母的单词阶梯。

我有数千对单词，其中两对是一个不同的字母。这里只是其中一些配对的一小部分。

[(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)、 whereV = { all words}和E = {(u,v) | there is a direct "ladder" from word u to word v}。

在这种情况下，图是未加权的，因此您可以使用BFS找到从源到目标的最短路径。

在找到一个可接受的启发式函数来评估您与目标节点的距离后，也可以使用A* 算法。正如@trutheality 所指出的，一种可能的启发式函数是不匹配字母的数量。

请注意，您实际上不需要在开始搜索之前“创建”整个图形，您可以使用函数“即时”生成它：next(w) = { u | (w,u) is in E, or in other words - there is a direct ladder from w to u }

通过运行 BFS 找到最短路径的长度后，您还可以通过返回找到确切的路径。这个线程用更多细节解释了这个问题。这个想法是维护一个Map - 其中键是顶点，值是如何发现这个顶点 - 导致发现键的顶点。BFS 完成后，你只需要从目标回到源，你就得到了你的路径！[逆转，当然……]

于 2012-04-14T22:41:35.600 回答