[레포트] kn1133423 AnAlgorithmOFMinimumCostHamilt
페이지 정보
작성일 23-03-26 01:08
본문
Download : kn1133423_AnAlgorithmOFMinimumCostHamilt.hwp
[레포트] kn1133423 AnAlgorithmOFMinimumCostHamilt
Download : kn1133423_AnAlgorithmOFMinimumCostHamilt.hwp( 53 )
설명
An Algorithm OF Minimum Cost Hamiltonia...
An Algorithm OF Minimum Cost Hamiltonia...
An Algorithm OF Minimum Cost Hamiltonian Circle 1. 전 제 Cost를 갖는 edge들에 대한 state space tree의 graph가 hamiltonian cycle이라면, 그 추가된 edge들에 대한 cost를 node로 하는 graph 또한 hamiltonian cycle이다. ㈁ Edge가 추가된 후 Graph가 hamiltonian cycle인지를 체크한다. ㈂ Hamiltonian cycle이면 edge들의 cost의 합을 저장한다. 이 저장된 값을 bounding 값으로 설정하고, 새로운 edge들의 cost가 이보다 큰지를 확인하면서(backtracking) 추가한다. 3. Algorithm Graph G; struct EDGE added_edge[N]; int CostSum = 0; Graph에 추가된 edge들의 cost의 합 struct EDGE Hemil_Cycle; Hemiltonian cycle에 대한 타입설정 int n; edge들의 수 int m; vertices들의 ...
레포트 > 기타
레포트 kn1133423 AnAlgorithmOFMinimumCostHamilt
순서
다. 더 이상의 edge의 추가가 없으면 exit한다. 만약, 새로운 hemiltonian cycle가 생성된다면 새로운 hemiltonian cycle가 가지고 있는 cost의 합 을 새로운 bounding의 값을 재설정한다. ㈃ ㈁을 반복한다. 1)2. 기본 戰略 ㈀ 주어진 Graph에 대상으로하여 가장 낮은 cost를 갖는 edge2)를 추가시킨다. ㈄ 모든 edge들이 visited되었을 때, 저장된 graph가 hamiltonian cycle이 되고, 종료한다.
