什么是最好的算法来找到一个双峰/字梯？ [英] What is the best algorithm to find a doublet / word ladder?

问题描述

是否有一个有效的算法来找到一个双峰/字梯？这是可以做到蛮力，但必须有一个更好的方式来做到这一点。怎么样？

Is there an efficient algorithm to find a doublet/word ladder? It can be done brute force, but there has to be a better way to do it. How?

http://en.wikipedia.org/wiki/Word_Ladder

推荐答案

如果你认为这是一个寻路问题，您可以尝试一个A *算法。

If you think of this as a path finding problem you could try an A* algorithm.

（A基于启发式搜索的答案空间。）

(A heuristic based search of the answer space.)

另外，你只是想找到一个解决方案或最佳的解决方案？

Also, do you just want to find a solution or the best solution?

修改

我不喜欢改变，但我看到，我的例子是不好的，因为一个单一的步骤解决它。当看的例子忽略这个问题。的

快速概述如何A *工程（略应用到这个问题）

Quick overview of how A* works (and slightly applied to this problem)

要使用A *您需要一个函数来计算（完成）给定的状态。你要为国家这是更接近球门更高的价值。

To use A* you need a function that evaluates a given state (of completion). You want a higher value for states which are closer to the goal.

有关此问题的两个示例功能

For this problem two example functions

• （每个英文字母这是正确的* 1） - （信件从不同的目标数* 10）
• （每个英文字母这是正确的* 100） - （字母距离球门不同的数字）

正如你所看到的第一个好处字的大小是密切了正确的字母 第二有利于字母正确的。

As you can see the first favors word size being close over correct letters The 2nd favors letters correct.

不知道哪个好 - 寿你可以做一个平衡的公式太

Not sure which is better -- tho you could do a balanced formula too.

可以说，我们正试图从BOT让 - >船

Lets say we are trying to get from bot -> boat

您会再评估男孩所有可能发生的变化，让我们用第一个功能 所以你会评估两个例子是引导和蝙蝠（和其他人。）引导具有值3和蝙蝠有一个值-7。引导比较好（根据此功能），所以接下来我们将评估启动（之前任何其他人）的所有可能发生的变化，并找到解决方案。

You would then evaluate all possible changes of boy, lets use the first function so two examples you would evaluate would be boot and bat (and others.) boot has a value of 3 and bat has a value of -7. Boot is better (according to this function) so then we would evaluate all possible changes of Boot (before any of the others) and find the solution.

清除泥？也许维基百科的解释更好。

Clear as mud? Maybe Wikipedia explains it better.

http://en.wikipedia.org/wiki/A * _search_algorithm

http://en.wikipedia.org/wiki/A*_search_algorithm

便笺：

• A *会找到最佳的解决方案，如果该功能的目的是对的，如果存在一个问题，给予这样的功能。这是纯功能的A *。

• A* will find the best solution if the function is designed right, if such a function exists for a give problem. This is the neat feature of A*.

这是A *改进是短路的状态在上面的例子中寻找（例如 - 正3是一​​款非常不错的成绩。（4是最高分），这样你的算法可以停止寻找在其他国家和移动到一个是非常接近的。

An A* enhancement is to short circuit looking at states (for example in the case above -- positive 3 is a very good score (4 is the max score) so your algorithm could stop looking at other states and move on to the one that is very close.

的A *的两个硬的部分是：1）寻找合适的功能; 2）能够列举出所有可能的状态。我认为2是不是很难做的一个很好的字典文件和一些快速散列/搜索功能。

The two hard parts of A* are 1) finding the right function and 2) being able to enumerate all the possible states. I think 2 is not so hard to do with a good dictionary file and some fast hashing/searching functions.

这篇关于什么是最好的算法来找到一个双峰/字梯？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！