词搜索算法的MATLAB [英] word search algorithm matlab
问题描述
我在寻找一个有效的字搜索算法。如果你能帮助我想出它的话会更好。
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 thetarget
inverted - etc.
- 找到的第一个字母出现的所有
- 在消除所有不能满足
目标的长度那些出现的
基于网格的尺寸 - 搜索全部命中的社区是否出现的第二个字母
- 在消除基于长事件,等等。
- 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.
但是,除了这些相对次要的优化,我不认为你可以在实践中做到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:
(不要忘了在过滤的方向的第二个字母后,作为命中的第二个字母修复搜索方向)
(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 :)
这篇关于词搜索算法的MATLAB的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!