설명

문제는 네트워크에서 최소 스패닝 트리를 찾는 것입니다.
gamslib 문제의 네트워크(sroute)가 예로 사용됩니다.
알고리즘은 다음을 보여주기 위해 모든 노드에서 시작됩니다.
알고리즘은 모든 노드에서 시작할 수 있습니다.

소형 모델 유형 :메가 슬롯

카테고리 : 메가 슬롯 모델 라이브러리

메인 파일 : mst.gms

$title 최소 스패닝 트리(MST,SEQ=94)

$onText
문제는 네트워크에서 최소 스패닝 트리를 찾는 것입니다.
gamslib 문제의 네트워크(sroute)가 예로 사용됩니다.
알고리즘은 다음을 보여주기 위해 모든 노드에서 시작됩니다.
알고리즘은 모든 노드에서 시작할 수 있습니다.

Hillier, FS 및 Lieberman G J, 운영 연구 소개.
홀든 데이, 샌프란시스코, 1967.

키워드: 최소 신장 트리, 그래프 이론
$offText

내가 '도시'로 설정 / 보스톤, 시카고, 달라스
                 캔자스시티, 로스앤젤레스, 멤피스
                 포틀랜드, 솔트레이크, 워시DC/;

별칭(i,ip,ipp);

매개변수 uarc(i,ip) '아크 및 비용'
                     / 보스턴 .chicago 58, kansas-cty .memphis 27
                       보스턴 .wash-dc 25, 캔자스-cty .salt-lake 66
                       시카고 .kansas-cty 29, kansas-cty .wash-dc 62
                       시카고 .멤피스 32, 로스앤젤레스 .포틀랜드 58
                       Chicago .portland 130, losangeles .salt-lake 43
                       시카고 .솔트레이크 85, 멤피스 .wash-dc 53
                       달라스 .kansas-cty 29, 포틀랜드 .salt-lake 48
                       달라스 .losangeles 85, 달라스 .memphis 28
                       달라스 .솔트레이크 75 /;

세트
   a(i) '할당된 노드'
   u(i) '할당되지 않은 노드'
   nan(i) '새로 할당된 노드'
   s '순서' / 1*10 /;

매개변수
   mst(i,ip,ipp) '모든 노드에서 시작하는 최소 스패닝 트리'
   fold(i,ip,ipp) '접힌 최소 스패닝 트리'
   darc(i,ip) '지향된 호'
   dmin '최소 거리';

darc(i,ip) = max(uarc(i,ip),uarc(ip,i));

옵션 darc:0;
다크 표시;

루프(ip,
   난(ip) = 예;
   a(i) = nan(i);
   u(i) = a(i)가 아님;
   루프(s$카드(nan),
      난(nan) = 아니오;
      dmin = smin((a,u)$darc(a,u), darc(a,u));
      루프((a,u)$(darc(a,u) 및 dmin = darc(a,u)),
         mst(a,u,ip) = ord(들);
         최소 = 0;
      );
      nan(u) = sum(a$(mst(a,u,ip) = ord(s)), yes);
      u(nan) = 아니오;
      a(nan) = 그렇습니다;
   );
);

옵션 mst:0:2:1;
표시 mst;

fold(i,ip,ipp)$(ord(i) < ord(ip)) = mst(i,ip,ipp) - mst(ip,i,ipp);

옵션 접기:0:2:1;
디스플레이 접기;