최적의 경로 기능 속도 향상

Question

전환 비용 매트릭스의 노드에서 다른 모든 노드 (여기에있는 기능 폴더의 DPA 기능 http://uk.mathworks.com/matlabcentral/fileexchange/39034-finding-optimal-path-on-a-terrain)까지 최적의 경로를 찾는 스크립트가 있습니다.

내가 가지고있는 문제는이 함수가 정확히 필요한 것인데 16641 x 16641 행렬 (129 * 129 x 129 * 129) 이상으로 실행해야한다는 것입니다. 나는 현재 그것을 실행하고 있지만 예상대로 나이를 먹고 있습니다 (현재 2 시간 째 실행 중!). 마지막에 전체 기능을 게시 하겠지만 다음 기능을 변경하면 성능이 크게 향상 될지 여부를 밝힐 수 있는지 궁금합니다. 이 과도한 실행 시간을 생성하는 프로세스는 다음과 같습니다.

for fromNode = 1 : m 
     for toNode = 1 : m 
      aij = P(toNode, fromNode); 
      dj = aij + prevStageCostMat(fromNode); 
      if dj < stageCostMat(toNode) 
       stageCostMat(toNode) = dj; 
       predMat(toNode, stage) = fromNode; 
      end   
     end % end toNode 
    end % end fromNode 

여기서 m = 16641입니다. 함수가 모든 노드를 통해 관계없이 올바른 결과를 제공해야합니다 (나는 그 함수가 무엇을하는지 정확하게 이해하고 있습니까?) 또는 계산 속도를 높이는 방법이 있습니까?

주요 기능 페이지 사람이 내가 대단히 감사 (당신은 더 이상 설명이 필요하면 제가 이해 알려 주시기 바랍니다 거라고 나에게 어떤 통찰력을 줄 수 있다면 여기

% Keep in mind that DPA propagates through all the nodes. Basically DPA 
% tries to find optimal path from one nodes to all nodes 

는 전체 기능을 말한다 내가 이것을 혼란스럽게 설명했다면), 고마워!

function [stageCostMat, predMat, converged] = dpa(P, startNode, endNode, maxIteration) 

% This is the function that will perform the DPA. 
% 
% Assume we have n number of nodes. P matrix is the transition cost matrix 
% with dimension of n x n(square matrix). P(toNode, fromNode) shows 
% transition cost from fromNode to toNode. 
% 
% stageCostMat shows the cost at each node for current iteration. 
% stageCostMat(c) = current stage cost matrix at node c. 
% 
% predMat shows parent/predecessor node of each node for every stage. 
% predMat(c, s): parent of node c during stage s. 
% 
% manurung.auralius@gmail.com 
% 17.11.2012 
% ------------------------------------------------------------------------- 

% Is the algortihm converged? 
converged = 0; 

% Cost matrix is a square matrix, m = n 
[m, n] = size(P); 

% Assume we will probably converge after n stages 
stageCostMat = ones(1, m) * inf; 

% Initial cost, no initial cost 
stageCostMat(startNode) = 0; 

% Predecessor matrix to trace back the optimum path, we will record parent of 
% each node on each iteration 
predMat = zeros(m, maxIteration); 

% Stage-by-stage, we move from start node to terminal node 
for stage = 2 : maxIteration  

    % Find connection from any nodes to any nodes, keep the smaller cost 
    prevStageCostMat = stageCostMat; 
    stageCostMat = ones(1, m) * inf; 

    for fromNode = 1 : m 
     for toNode = 1 : m 
      aij = P(toNode, fromNode); 
      dj = aij + prevStageCostMat(fromNode); 
      if dj < stageCostMat(toNode) 
       stageCostMat(toNode) = dj; 
       predMat(toNode, stage) = fromNode; 
      end   
     end % end toNode 
    end % end fromNode 

    % Termination 
%  if (stageCostMat == prevStageCostMat) 
%   converged = 1; 
%   break; 
%  end 

    if (predMat(endNode, stage) == endNode) || (predMat(endNode, stage-1) > 0) && (predMat(endNode, stage) == predMat(endNode, stage-1)) 
     converged = 1; 
     break; 
    end 

end 

predMat = predMat(:, 1:stage); 

Answer 1

조금 더 발전했습니다. toNode는 forNode의 현재 위치에 관한 당신은 toNode 행렬 크기 초과 할 경우 사건을 회피해야한다 :

for fromNode = 1 : m 
    %relativ to fromNode bc its always on the diagonal 
    for toNode = (fromNode-1) : (fromNode+1) 
     %for the first and alse fromNode toNode would be out of the array limits 
     if toNode==0 | toNode==m+1 
      continue 
     end 
     aij = P(toNode, fromNode); 
     dj = aij + prevStageCostMat(fromNode); 
     if dj < stageCostMat(toNode) 
      stageCostMat(toNode) = dj; 
      predMat(toNode, stage) = fromNode; 
     end 
    end % end toNode 
end % end fromNode 

난 당신이 이전 루프에서 솔루션이 경우 데이터에이를 입어을 추천을 설교가 여전히 같은지 확인하십시오. 16641 개 중 3 개만 계산하면되므로 시간이 크게 단축됩니다.