我在寻找一个有效的字搜索算法。如果你能帮助我想出它的话会更好。

I am looking for an efficient word search algorithm. If you can help me come up with it it would be even better

a h c k 
x r j i
b v t l
c y q s

和我想找到'艺术'。如果斯特拉也是一个有效的话，我希望这样的发现为好。 （垂直，水平，对角线和反向）。我想出了一些算法，但你似乎并不有效，长期食用编码。使用find（）来获得的第一个字母，并期待在该列或行的第一个包括在内。

and I want to find 'arts' . If 'stra' was also a valid word I want that to be found as well. (vertical, horizontal, diagonal and reverse). I came up with a few algorithms but thy don't seem efficient and consume long coding. First one included using find() to get the first letter and look at that column or rows.

推荐答案

这里有一种方法：

%// Example word grid
C = [
    'a' 'h' 'c' 'k' 'r'
    'x' 'r' 'j' 'i' 'p'
    'b' 'v' 't' 'l' 'q'
    'a' 'y' 'q' 's' 'o'];

%// Your search term
target = 'arts';

%// Optionally, do some obvious checks here. 
%//  - length of the search string may exceeds the grid's dimensions
%//  - there are no matches for the first letter
%//  - and similar

%// Form single cellstring containing all search directions
allDirections = [
    %{
    // horizontal, horizontal-reversed
    %}
    cellstr([C ; C(:,end:-1:1)])
    %{
    // vertical, vertical-reversed
    %}
    cellstr([C'; C(:,end:-1:1)']) 
    %{
    // Diagonal, top-left to bottom-right, and reversed
    %}
    arrayfun(@(ii){diag(C,ii)'}, -size(C,1)+2:size(C,2)-2)';
    arrayfun(@(ii){diag(C(end:-1:1,end:-1:1),ii)'}, -size(C,1)+2:size(C,2)-2)';
    %{
    // Diagonal, top-right to bottom-left, and reversed
    %}
    arrayfun(@(ii){diag(C(:,end:-1:1),ii)'}, -size(C,1)+2:size(C,2)-2)';
    arrayfun(@(ii){diag(C(end:-1:1,:),ii)'}, -size(C,1)+2:size(C,2)-2)';
];

%// And now just find the string
strfind(allDirections , target)

通过

当然，你可以改善（内存）的效率 执行 strfind 上的所有单独路线 在做2× strfind 在同一个方向，但与目标倒 等。

doing the strfind on all the directions separately doing 2 × strfind on the same direction, but with the target inverted etc.

但是，除了这些相对次要的优化，我不认为你可以在实践中做到MATLAB中的更好的。

But aside from these relatively minor optimizations, I don't think you can do much better in MATLAB in practice.

一个理论上更高效的递归，分支和绑定类型的搜索大致是这样的：

A theoretically more efficient recursive, branch-and-bound type search roughly goes like this:

找到的第一个字母出现的所有 在消除所有不能满足目标的长度那些出现的基于网格的尺寸 搜索全部命中的社区是否出现的第二个字母 在消除基于长事件，等等。 find all occurrences of the first letter eliminate all of those occurrences that cannot satisfy the length of the target based on the dimensions of the grid Search the neighborhoods of all hits for occurrences of the second letter Eliminate occurrences based on length, etc.

（不要忘了在过滤的方向的第二个字母后，作为命中的第二个字母修复搜索方向）

(Don't forget to filter on direction after the second letter, as the hits for the second letter fixes the search directions)

据我所看到的，这将需要大量的少读和比较，比我的版本。但是，我的猜测是，使用固定程序（像我一样）将是更快和更复杂的比使用（嵌套）循环。但我可能是错的。

As far as I can see, this would need a lot less reads and comparisons than my version. However, my guess would be that using canned routines (as I did) is going to be faster and less complicated than using (nested) loops. But I could be wrong.

尝试。个人资料。学习。微笑。指正:)

Try. Profile. Learn. Smile. Correct me :)