алгоритм поиска слов matlab

Question

Я ищу эффективный алгоритм поиска слов. Если вы можете помочь мне придумать это, было бы еще лучше

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

и я хочу найти «искусство». Если «stra» также было правильным словом, я хочу, чтобы это тоже было найдено. (вертикальный, горизонтальный, диагональный и обратный). Я придумал несколько алгоритмов, но вы не выглядите эффективными и потребляете длинное кодирование. Во-первых, с помощью find(), чтобы получить первую букву и посмотреть на этот столбец или строки.

Answer 1

Вот один из способов:

%// 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 на в том же направлении, но с target перевернутым
• и т.д.

Но помимо этих относительно небольших оптимизаций, я не думаю, что вы можете сделать намного лучше в MATLAB на практике.

Теоретически более эффективный рекурсивный, ветвей и границ тип поиска примерно выглядит следующим образом:

• найти все вхождения первой буквы
• устранения всех этих явлений, которые не могут удовлетворить длину из target на основе размеров сетки
• Поиск окрестностей всех хитов вхождений второго письма
• искоренению вхождений на основе длины и т.д.

(Не забудьте фильтровать по направлению после второго письма, как хиты для второй буквы фиксирует направление поиска)

Насколько я понимаю, это нужно было бы намного меньше читает и сравнивает, чем моя версия. Тем не менее, я предполагаю, что использование законченных процедур (как и я) будет более быстрым и менее сложным, чем использование (вложенных) циклов. Но я могу ошибаться.

Попробуйте. Профиль. Учить. Улыбка. Исправьте меня :)