i cant get the code to give an answer. it just runs in an inf loop i believe

Question

christopher andersen 2014-4-19

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/126384-i-cant-get-the-code-to-give-an-answer-it-just-runs-in-an-inf-loop-i-believe

评论： Walter Roberson 2014-4-20

% dijkstra code
clc
clear
pause on
% [DIST, PATH] = dijkstrateam(source,dest)
key=('abcdefghijklmnop');
source=14
dest=1
%coord of points (x,y)
a=[132,344];
b=[159,72];
c=[296,72];
d=[296,554];
e=[159,554];
f=[384,76];
g=[567,76];
h=[567,318];
i=[524,371];
j=[524,504];
k=[388,466];
l=[589,298];
m=[508,318];
n=[488,371];
o=[388,504];
p=[384,144];  c
pos=0;
frompos=0;
load('carray.mat')
pointarray=[a;b;c;d;e;f;g;h;i;j;k;l;m;n;o;p];
disarray=zeros(16);
totarray=[1:16]
for hhh=1:16
totarray(hhh,1:16)=inf
end
satisfied=0
%set distance to array to inf
for hhh=1:16
disarray(hhh,1:16)=inf
end
%create closed list
closed=[1:16]
for hhh=1:16
closed(1,hhh)=0
end
% [0,1,0,0,1,0,0,0,0,0,0,0,0,0,0,0;1,0,1,0,1,0,0,0,0,0,0,0,1,1,1,0;0,1,0,1,0,1,0,0,1,0,1,0,1,1,1,1;0,0,1,0,1,1,0,1,0,0,1,1,1,1,1,1;1,1,0,1,0,0,0,0,0,1,0,0,0,0,1,0;0,0,1,1,0,0,1,0,0,0,0,0,0,0,0,1;0,0,1,0,0,1,0,1,1,1,0,1,0,0,0,1;0,0,0,1,0,0,1,1,1,1,1,1,1,1,0,0;0,0,1,0,0,0,1,1,0,1,0,1,1,1,0,1;0,0,0,1,1,0,1,1,1,0,0,1,0,0,1,0;0,0,1,1,0,0,0,1,0,0,0,1,1,1,1,1;0,0,0,1,0,0,1,1,1,1,0,0,0,1,0,0;0,0,1,1,0,0,0,1,1,0,1,0,0,1,0,1;0,0,1,1,0,0,0,1,1,0,1,1,1,0,0,1;0,0,1,1,1,0,0,0,0,1,1,0,0,0,0,0;0,0,1,1,0,1,0,0,1,0,1,0,1,1,1,0;];
for kk=1:16
    frompos=frompos+1;
      for k =1:16
          pos =pos+1;
          % r= array(11)
          % s=array(pos:1)
          z=(pointarray(frompos,1)-pointarray(pos,1)).^2;
          y=(pointarray(frompos,2)-pointarray(pos,2)).^2;
          x=sqrt(z+y);
          if carray(frompos,pos)==1
          disarray(frompos,pos)=x;
          end
      end
          if pos==16
             pos=0;
          end
  end
%find the amount of nodes
nodes=length(disarray);
% %open list
% open=(1:nodes-1)
% %place source in closed list
% closed(1)=source
%put all other nodes in open list
for vv =1:nodes     %CREATE OPEN ARRAY     
    open(vv)=vv
end
for go = 1:(nodes)   %PLACE ALL NONE SOURCE NODES IN OPEN AND SOURCE IN CLOSED
    if open(go)~= source
    else
        close(1)=open(go)
        open(go)=0
    end
end 
pos=source
for counter=1:nodes
 row=pos   
temparray=disarray(row,1:end)  %pull source node from distance array
%  for mmm= 1:nodes
%      if temparray(mmm)~=inf          %dont think this is needed
%          holdarray(mmm)=temparray(mmm)
%      end    
      for compcount =1:nodes              %add distances to node to current distance
          rowToNewNode= temparray(1,compcount)%distance from current node to other nodes 
          DistToRowNode=totarray(1,pos)       %distance to current node from source node
          if  totarray(1,compcount) > (rowToNewNode +DistToRowNode)         %if distance is shorter than current replace
              totarray(1,compcount)=(rowToNewNode+DistToRowNode)
          end
      end
   satisfied =0
      while satisfied == 0
            sortarray=sort(temparray)
            [rr,cc]=find(temparray==sortarray(1))  %find the closest node
            dd=find(close == cc)  %
            if cc ~= dd           %
               satisfied = 1
               close(counter) = cc     %place new node in the close list
            else
               temparray(cc)=inf       %if already in the close list change to inf and look at the next shortest distance
            if find(temparray ~= inf) == false  %if all nodes are done then stop
               break   
            end
            end
      end
  end

4 个评论
显示 2更早的评论隐藏 2更早的评论

Geoff Hayes 2014-4-20

Hi Christopher,

Where do you think that the code is getting stuck in an infinite loop? Have you put in some fprintfs to see at which points the code passes through and at which point it gets caught?

I noticed that the code has a while loop near the end which is typically the kind of loop that exhibits the infinite looping behaviour that you suggest. As the while loop conditions on satisfied==0, then if it gets set to one (as in the if condition block) then there should be no problem in exiting the while loop. I'm not sure about the else condition though...

The break (in the else body) is only called if the if condition is true i.e. find(temparray~=inf)==false. And this will be true so long as temparray has at least one element that is not inf with find returning its non-zero index (or a vector of indices) which will never be equal to false (which is zero). If temparray has all elements set to inf, then an empty matrix is returned. This is not equal to false/0 so the equality is not met and the while loop continues infinitely.

Geoff

christopher andersen 2014-4-20

what i have done was to put pauses and slowly work step by step to see if it is doing what i want it to do. i think it is but maybe it is a problem with what i have coded and it wont do what i am trying to do. i am not really sure is my problem or where to go next

Geoff Hayes 2014-4-20

Have you been able to identify where the code is getting stuck? What is the problem to be solved by the above code?

请先登录，再进行评论。

请先登录，再回答此问题。

Answer 1

Walter Roberson 2014-4-20

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/126384-i-cant-get-the-code-to-give-an-answer-it-just-runs-in-an-inf-loop-i-believe#answer_133926

在 MATLAB Online 中打开

That does not appear to be straight Dijkstra code. The reason for marking with "inf" is not obvious. It appears to me that you are perhaps trying to prevent backtracking to where you just came from, but instead you are preventing the search from ever returning to the same column even if in a different row.

Dijkstra's algorithm is usually most easily represented using matrix multiplication. When T is the transition matrix, T^n represents where you can get to in n steps. If you are looking to get from node A to node B,

Tn = T^n;
if Tn(A,B) > 0
   %there is a route that is n steps long
end

you would do this from n = 1 to n = number of nodes -- but stopping if Tn ever goes all 0.

2 个评论
显示无隐藏无

christopher andersen 2014-4-20

编辑：Walter Roberson 2014-4-20

在 MATLAB Online 中打开

Pseudo-Code
Initialize CONN, c, and ng. 
Place source
 in C, g(s)=0;
Place all n ≠ ng in O and set g(n)=∞ for all n ≠ ng
Set nc= ng
While O ≠ Ø
Find all nodes n in Star(nc) using CONN
If g(nc)+c(nc,n)<g(n) and n is in O
Then g(n) =g(nc)+c(nc,n)
P(n)=nc
Set nc=n such that g(n) is minimal among n in O
Place nc in C
Remove nc from O
End loop
Determine ns
Find path from ns to ng by following P(ns) back to ng