需要帮助在许多一个字母不同的单词之间创建一个单词梯(java)

Question

我已经在这个问题上付出了很多努力,而且我真的很接近尾声.总体目标是在两个五个字母单词之间创建最小长度的单词梯子,其中梯子的每个"梯级"是与前一个单词不同的一个字母.例如:

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

程序从必须输入开始和结束字以及所需梯形图的长度开始,程序必须解决它.我已经相当远了,所以我将把大部分细节都解释一下,以解释我目前的情况.

说我要从"辣妹"到"孩子",我正在寻找一个10个字母的字梯.

我有几千双字,其中两对是彼此不同的一个字母.这里只是一些对的一小部分样本.

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

这种情况持续了很长时间,但在那里保证我的目的词存在,并且我的起始词(辣妹)和我的结束词(孩子)之间有一条路径,那个梯子是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;
}

Answer 1

好吧,您正在描述一个图形问题,这被称为最短路径问题.

在这里,您的图表是G = (V,E),在哪里V = { 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完成后,你只需要从目标回到源,你就得到了你的路径![逆转,当然......]