2019년 2학기 인공지능 중간시험과제물 공통(상태공간 탐색, A* 알고리즘)
분야
zip(가) 상태공간 탐색으로 이 문제를 풀이하는 방법의 개념을 설명하라.
(나) A* 알고리즘을 이용하여 최단길이 경로를 구하려고 한다. [그림2]를 예측 비용을 구하는데 활용하여 평가함수를 정의하고, 이에 따른 탐색 트리를 보여라. 각 탐색 트리의 각각의 노드에는 확장 순번과 평가함수 값을 표시하라.
(다) A* 알고리즘을 이용하여 최소시간 경로를 구하려고 한다. 예측 비용은 평균시속 17km/h를 가정하여 [그림2]를 바탕으로 정하고, 이에 따라 평가함수를 정의하라. 이에 따른 탐색 트리를 (나)와 동일한 방법으로 보여라.
- 목 차 -
Ⅰ. 상태공간 탐색으로 이 문제를 풀이하는 방법의 개념을 설명하라.
1. 상태 공간 탐색의 개념
2. 에이 스타 알고리즘 문제 풀이를 위한 개념
Ⅱ. A* 알고리즘을 이용하여 최단길이 경로를 구하려고 한다. [그림2]를 예측 비용을 구하는데 활용하여 평가함수를 정의하고, 이에 따른 탐색 트리를 보여라. 각 탐색 트리의 각각의 노드에는 확장 순번과 평가함수 값을 표시하라.
Ⅲ. A* 알고리즘을 이용하여 최소시간 경로를 구하려고 한다. 예측 비용은 평균시속 17km/h를 가정하여 [그림2]를 바탕으로 정하고, 이에 따라 평가함수를 정의하라. 이에 따른 탐색 트리를 (나)와 동일한 방법으로 보여라.
참고문헌
1. 상태 공간 탐색의 개념
상태 공간 탐색은 최적 목표를 달성하기 위한 중간 과정을 하나의 상태로 보고 각각 상태에서 최적의 선택을 하여 최종적으로 최소 비용으로 목표를 달성하는 일련의 연산자를 찾는 과정을 의미한다. 상태 공간 탐색 방식에 다익스트라 알고리즘, 에이스타 알고리즘 등 여러 알고리즘이 있다. 이 글에서 에이 스타 알고리즘을 토대로 방대한 상태 공간을 효율적으로 축소하여 문제를 해결한다.
에이스타 알고리즘은 탐색하지 않은 노드들 중에서 사전에 정해 놓은 함수의 값이 가장 최적인 정점을 선택하는 Best-First-Search 방식을 활용하고 있다. 각각의 노드에 대한 평가함수는 출발 노드에서 노드 k까지 도달하는데 드는 비용과 노드 K에서 목표 노드에 도달하는데 드는 비용의 합으로 나타낸다. 출발 노드에서 이동 가능한 노드들의 평가함수 값을 비교해 최소 비용으로 갈 수 있는 노드를 선택하고 탐색했으나 선택되지 않은 노드는 평가 대상에서 제외하는 탐색 과정을 목표 노드에 도달할 때까지 반복한다. 에이스타 알고리즘이 다른 상태 공간 알고리즘과 다르게 추정잔여거리를 사용하여 탐색을 하기 때문에 여타 알고리즘보다 탐색 단계가 줄어들어 탐색 시간이 현저히 줄어든다.
2. 에이 스타 알고리즘 문제 풀이를 위한 개념
에이스타 알고리즘의 노드에 대한 평가함수를 정의하면 다음과 같다. ‘출발노드로부터 목표 노드까지의 경로비용’을 f(k)이라고 하고 ‘출발노드로부터 노드 k까지의 경로비용’을 g(k)라고 하고 ‘노드 k로부터 목표노드까지의 예측 경로비용’을 h(k)라고 한다.
- 중략 -
- 오늘 본 자료가 없습니다.
- 국제경영학4 2024년 11월 미국대통령 선거에서 미국 민주당후보가 당선된 경우에 있어 한국기업의 글로벌경영의 기회요인과 위협요인을 설명하시오0
- 2024년 1학기 사회문제론 기말과제- 교재 6장 건강 불평등 문제를 비롯해 여러 자료를 참고하여 1) 건강 불평등 문제에 관해 설명하고 2) 건강 불평등의 원인과 관련한 다양한 설명들을 정리한 다음 3) 이러한 설명 중 가장 설득력이 높은 것 하나를 선택해 이에 근거해 대안을 제시하시오
- 교육사4공통) 교육사교재에 소개된 서양의 교육사조 가운데 자신의 교육관과 가장 부합하는 교육사조-루소의 자연주의- 기술하시오0k
- 세계의정치와경제A형 2024년 1학기 기말과제- 전지구적 세계화가 심화되면서 오히려 민주주의가 심각한 위기에 직면하고 있다. 교재 3장과 여러 자료를 참고하여 현재 민주주의의 위기를 묘사하고, 민주주의를 위기에서 구할 수 있는 개인적 또는 집단적 대안에 대해 고민하고 서술하시오
- 2024년 1학기 세계의정치와경제C형 기말과제) 신자유주의화로 인해 오히려 개인의 건강 문제가 심각해지는 사례들이 있다. 교재 14장과 관련한 자료를 참고하여 이러한 상황을 묘사하고, 이를 해결할 수 있는 방안에 대해 고민하고 논하시오
- (2024학년도 1학기, 기말과제물, 국제스포츠의 이해, 공통) 국제스포츠계에서 중요한 역할을 하는 세계도핑방지기구(WADA)와 국제검사기구(ITA), 스포츠중재재판소(CAS)의 역할과 기능에 대해 기술하시오.
- 2024년 1학기 방송통신대 기말과제물 가축생리학)탄수화물, 단백질 그리고 지방의 소화와 흡수에 대하여 설명하시오 비타민과 미네랄의 흡수에 대하여 설명하시오
- 2024년 1학기 세계의정치와경제C형 기말과제) 신자유주의화로 인해 오히려 개인의 건강 문제가 심각해지는 사례들이 있다. 교재 14장과 관련한 자료를 참고하여 이러한 상황을 묘사하고, 이를 해결할 수 있는 방안에 대해 고민하고 논하시오
- (2024학년도 1학기, 기말과제물, 스포츠미디어커뮤니케이션, 공통) 스포츠 내셔널리즘을 설명하고 근대 올림픽경기대회를 중심으로 스포츠 내셔널리즘의 긍정적인 부분과 부정적인 부분을 논의하시오
- [청소년성교육과성상담] 2024년 1학기 기말과제물, 1) 의사소통에서 남녀 차이가 어떻게 나타나는지 관련 이론을 제시하고, 2) 의사소통에서 남녀차이에 대한 자신의 경험 또는 대리적 경험 사례를 바탕으로 효율적인 의사소통을 위한 방안을 제시하고, 3) 청소년성교육과성상담 강의를 통해 배운점과 느낀점을 쓰시오
- (2024학년도 1학기, 기말과제물, 국제스포츠의 이해, 공통) 국제스포츠계에서 중요한 역할을 하는 세계도핑방지기구(WADA)와 국제검사기구(ITA), 스포츠중재재판소(CAS)의 역할과 기능에 대해 기술하시오.
- 2024년 1학기 방송통신대 기말과제물 가축생리학)탄수화물, 단백질 그리고 지방의 소화와 흡수에 대하여 설명하시오 비타민과 미네랄의 흡수에 대하여 설명하시오
- 2024년 1학기 세계의정치와경제C형 기말과제) 신자유주의화로 인해 오히려 개인의 건강 문제가 심각해지는 사례들이 있다. 교재 14장과 관련한 자료를 참고하여 이러한 상황을 묘사하고, 이를 해결할 수 있는 방안에 대해 고민하고 논하시오
- (2024학년도 1학기, 기말과제물, 스포츠미디어커뮤니케이션, 공통) 스포츠 내셔널리즘을 설명하고 근대 올림픽경기대회를 중심으로 스포츠 내셔널리즘의 긍정적인 부분과 부정적인 부분을 논의하시오
- [청소년성교육과성상담] 2024년 1학기 기말과제물, 1) 의사소통에서 남녀 차이가 어떻게 나타나는지 관련 이론을 제시하고, 2) 의사소통에서 남녀차이에 대한 자신의 경험 또는 대리적 경험 사례를 바탕으로 효율적인 의사소통을 위한 방안을 제시하고, 3) 청소년성교육과성상담 강의를 통해 배운점과 느낀점을 쓰시오
해당 정보 및 게시물의 저작권과 기타 법적 책임은 자료 등록자에게 있습니다. 위 정보 및 게시물 내용의 불법적 이용,무단 전재·배포는 금지되어 있습니다. 저작권침해, 명예훼손 등 분쟁요소 발견 시 고객센터에 신고해 주시기 바랍니다.
