-1

4 つの列 1 リンク番号 (今は重要ではありません)、列 2: 開始、列 3: 終了、列 4 (0 より大きい場合) を持つマトリックスがあります -> ノードが接続されます。再帰コードを作成しましたが、出力が正しく表示されません。たとえば、ノード 1 と 18 の間で出力されます。

path=[1 2 6 8 16 18] % which is correct
path=[1 2 6 8 16 7 18] % from 8 there are two paths (16 and 7)- it shouldnt show 16 anymore

% the code is
function findpaths(Matrix,start, destination,pathD)
if(start==destination)
   pathD % have a problem in storing them too (it just outputs now)
   return
end
    % to find all the rows that have start 
    % then it can find all the nodes connected to start 
    % if start is 6 then it return 4 and 9th row where 
    %there are 8 and 5 connected to 6 in those rows
    [row] = find(Matrix(:,2)==start); % to find all the rows that have this node

        for i=1:size(row,1) % adjecent nodes to start
            if Matrix(row(i),4)>0 % condition to see if the nodes are connected
                adj_node = Matrix(row(i),3);  % the adjacent node              
                if ismember(adj_node, pathD)==0
                    pathD;
                    pathD = [pathD adj_node];
                    start = adj_node;
                    findpaths(Matrix,start,destination,pathD);
                end
            end
        end
   end

以下はマトリックスです

1   1   2   1

2   1   3   0

4   2   6   1

16  6   8   1

6   3   4   0

7   3   12  0

21  8   9   0

10  4   11  0

15  6   5   0

22  8   16  0.5

20  8   7   0.5

37  12  13  0

32  11  10  0

25  9   10  0

49  16  17  0

18  7   18  0.5

28  10  15  0

50  16  18  0.5

34  11  14  0

53  17  19  0

39  13  24  0

46  15  22  0

56  18  20  0

42  14  23  0

76  24  23  0

62  20  21  0

69  22  21  0
4

1 に答える 1

0

ほとんどのアルゴリズム、少なくとも私が見つけたものは、BFS または DFS を実装して、アクセスしたノードを出力します。主な問題は、matlab でキュー データ構造を作成することです。利用可能な便利な Queue 実装が見つからなかったので、構造体を使用しました (あまり効率的な方法ではないと確信していますが、次の形式でデータを matlab に格納する必要があります。たとえば、次のようになります。

[['1', '4', '8'], ['1', '2', '5', '9'], ['1', '2', '5', '10'], ['1', '4', '7', '11']]

the Pseudo code is:
function [nodes,links] = bfs4(GRAPH, start, destination)% def BFS(graph,start,end,q):

nodes=struct;
links=struct;
path = struct;

temp_path = start;


last_node=[];
% q.enqueue(temp_path)
path(1).data = temp_path;


    while size(fieldnames(path),1)~=0
        tmp_path = path(1).data;
        if length(path) == 1
            path=struct;
        else
            path = path(2:end);
        end
        last_node = tmp_path(end);

    %         Storing the nodes in Two Forms (NODEs) and (LINKs)
        if last_node == destination
             tmp_path;

             if size(fieldnames(nodes),1)==0
             nodes(end).data=tmp_path
             else
                nodes(end+1).data=tmp_path
             end
%             taking the links 
         link=[];
            for i=1:(length(tmp_path)-1)
                link(i) = GRAPH(GRAPH(:,2)==tmp_path(i) & GRAPH(:,3)==tmp_path(i+1));
            end
            if size(fieldnames(links),1)==0
                links(end).data=link;
            else
                links(end+1).data=link;
            end
        end

        [row] = find(GRAPH(:,2)==last_node);
        for i=1:size(row,1)
     %              be careful -- the condition to be remove GRAPH(row(i),10)>0
             if   GRAPH(row(i),10)>0 && ismember(GRAPH(row(i),3),tmp_path)==0  
                   new_path=[];
                   new_path = [tmp_path GRAPH(row(i),3)];
                   if size(fieldnames(path),1)==0
                       path(end).data = new_path;
                   else
                       path(end+1).data = new_path;
                   end

             end
        end

    end % while
end % function
于 2013-11-15T01:33:34.613 に答える