행님들 도와주샘 초보

[1122(121.145)]

볼록 다각형은 n각형일때 n-3개의 선분으로 n-2개의 삼각형으로 분할이 가능한데, n각형의 좌표가 주어질 때 삼각형으로 분할하는데 필요한 선분의 길이가 가장 짧은 것을 구하는 방법이 뭐가 있을까요

[졸자(fkdlcb77)]

선분 길이의 합이 가장 짧은걸 구하는 문제인가료?

[익명(39.7)]

그래프를 만들어바

[익명(39.7)]

경로탐색알고리즘중에 다엑스트라알고리즘으로 최단거리 구하는거 응용해서..

[졸자(fkdlcb77)]

그냥 n면체의 이웃이웃해 있는 꼭지점 중 가장 거리가 짧은거 구한 다음에 그걸 잘라내서 삼각형 만들고, 또 그렇게 잘라넨 n-1면체의 꼭지점 중 이웃이웃해 있는 꼭지점 중 가장 거리가 짧은걸 또 구해서 잘라서 삼각형 만들고... 반복하면... 근사값밖에 안되려나.

[졸자(fkdlcb77)]

아니 저대로 하면 될꺼 같기도 한데

[codesafer(codesafer)]

ㄴ
https://ko.wikipedia.org/wiki/탐욕_알고리즘