kruskal, prim 알고리즘
페이지 정보
작성일 20-05-01 00:11
본문
Download : kruskal, prim 알고리즘.hwp
한번 내려진 결정은 뒤에 번복이 불가능하므로 각각의 결정이 가능한 해를 도출해 낼 수 있는지 확인해야한다. 이 알고리즘은 T에 포함될 간선을 비용의 크기 순으로 선택해 나간다. 해는 다음의 제한 조건을 만족시켜야 한다. 가능한 해란 문제에 의해 명시된 제한 조건 내에서 성립하는 해를 말한다. 이 갈망법은 광범위한 프로그래밍 문제에 적용될 수 있따 전형적으로 각 단계에서 항목의 선택은 최저 비용 또는 최고 이윤을 기준으로 판단한다. 이미 T에 포함된 간선들과 사이클을 형성하지 않는 간선만을 T에 추가한다. 연결 무방향 그래프에서 최소신장트리를 구하기 위해서는 세 가지의 상이한 알고리즘을 사용할 수 있따 이 세가지 알고리즘은 모두 갈망법이라고 하는 설계 전략(strategy)을 사용하고 있따 이 세가지 알고리즘은 kruskal알고리즘, prim알고리즘, sollin알고리즘이다. 최소 비용 신장 트리를 구성하기 위해서는 최저 비용을 기준으로 판단한다. 갈망법에서는 최적의 해를 단계적으로 구한다.
REPORT
(#9 kruskal, prim 알고리즘)
교과목
데이터구조
교수님
학 과
컴퓨터工學과
제출일자
학번
이름
1. 문제 인식
최소 비용 신장트리로 kruskal, prim 알고리즘을 구현하여라.
2. 문제 접근 방법 및 分析
(1)최소신장트리
최소신장트리란 최저의 비용을 갖는 신장트리이다.
(3) 사이클을 생성하는 간선을 사용해서는 안 된다
(2)kruskal 알고리즘
kruskal알고리즘은 한번에 하나씩 T에 간선을 추가해 가면서 최소비용신장트리 T를 구축한다.
(2) 정확하게 n-1개의 간선만을 사용해야 한다. 최소 비용 신장트리를 구성하기 위해서는 최저비용을 기준으로 사용한다. 각 단계에서는 몇 개의 판단기준에 따라 최상의 결정을 내린다. G는 연결되어 있고 N`0개의 정점을 가지므로…(생략(省略))
kruskal, prim 알고리즘 , kruskal, prim 알고리즘공학기술레포트 , kruskal prim 알고리즘
순서
레포트/공학기술
Download : kruskal, prim 알고리즘.hwp( 45 )
설명
kruskal,prim,알고리즘,공학기술,레포트
kruskal, prim 알고리즘
kruskal, prim 알고리즘
다.
(1) 그래프 내에 있는 간선들만을 사용해야 한다. 가능한 해란 문제에 의해 명시된 제한 조건 내에서 성립하는 해를 말한다.
