The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

商人过河问题的Matlab实现(转)

function foot=chouxiang 

  
%%%%%%%%%%%%%%%%%%%%%%    程序开始需要知道商人数,仆人数,船的最大容量
n
=input('输入商人数目:');
nn
=input('输入仆人数目:');
nnn
=input('输入船的最大容量:');
  
if nn>n
n
=input('输入商人数目:');
nn
=input('输入仆人数目:');
nnn
=input('输入船的最大容量:'); 
  end 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%    决策生成
   jc
=1;    % 决策向量存放在矩阵“d”中,jc为插入新元素的行标初始为1
 
for i=0:nnn                     
      
      
for j=0:nnn                      
        
if (i+j<=nnn)&(i+j>0)     % 满足条件  D={(u,v)|1<=u+v<=nnn,u,v=0,1,2} 
          d(jc,
1:3)=[i,j 1];   %生成一个决策向量后立刻将他扩充为三维(再末尾加“1”)
          d(jc
+1,1:3)=[-i,-j,-1];      %  同时生成他的负向量
             jc
=jc+2;         %  由于一气生成两个决策向量,jc指标需要往下移动两个单位
         end
      end
         j
=0;                                    
     
end
 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%     状态数组生成

  kx
=1;              % 状态数组存放在矩阵“A”中,生成方法同决策生成
for  i=n:-1:0
   
    
for j=nn:-1:0
       
       
        
if  ((i>=j)&((n-i)>=(nn-j)))|((i==0)|(i==n))  

           
%   (i>=j)&((n-i)>=(nn-j)))|((i==0)|(i==n))为可以存在的状态的约束条件
           
            A(kx,
1:3)=[i,j,1];                          % 生成状态数组集合D`
            A(kx
+1,1:3)=[i,j,0];
           
            kx
=kx+2;
        end
    end
     j
=nn;
end;
       
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  将状态数组生成抽象矩阵     
   

k
=(1/2)*size(A,1);                                      
  CX
=zeros(2*k,2*k);
a
=size(d,1);
           
    
    
  
for i=1:2*k                               
        
for j=1:a
            
               c
=A(i,:)+d(j,:) ;                 
               x
=find((A(:,1)==c(1))&(A(:,2)==c(2))&(A(:,3)==c(3))) ;
               
               v(i,x)
=1;          % x为空不会改变v的值
              
        end                                             
  end
  
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% dijstra方法
x
=1; y=size(A,1);
m
=size(v,1);
T
=zeros(m,1);    
T
=T.^-1;
lmd
=T;            
P
=T;               
S
=zeros(m,1);            
S(x)
=1;            
P(x)
=0; lmd(x)=0;
k
=x;

while(1)
  a
=find(S==0);
  aa
=find(S==1);
     
if size(aa,1)==m   
           
break;
     end
   
for j=1:size(a,1)
          pp
=a(j,1); 
        
if  v(k,pp)~=0 
              
if T(pp)>(P(k)+v(k,pp))
               T(pp)
=(P(k)+v(k,pp));
               lmd(pp)
=k;
              end   
        end
   end       
   mi
=min(T(a));
   
if mi==inf          
         
break;
   
else
         d
=find(T==mi);
         d
=d(1);
         P(d)
=mi; 
         T(d)
=inf;       
         k
=d;
         S(d)
=1;   
   end
end
 


if lmd(y)==inf
   foot
='can not reach';
   
return;
end

foot(
1)=y;
g
=2; h=y;
while(1)        
    
if h==x
      
break;
    end
       foot(g)
=lmd(h);
       g
=g+1;
       h
=lmd(h);
end   
  
foot
=A(foot,:);
foot(:,
3)=[];


这个代码比我上回写的C++代码短很多。。。。。。看来还是Matlab强大丫 一定要尽快学会才行 :-)

posted on 2009-03-21 01:09 abilitytao 阅读(3501) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理