Earticle

초록

영어

This paper researched a study to find a combination of acquisition scores for 9 dart throws, which is the minimum number of dart tactile throws in 501 point dart games. The maximum score that can be obtained by throwing once in a dart game is 60 points, which can end the perfect dart game with 60 points eight times according to 60x8+21x1=501, and if you earn 21 points once, you can finish the game with 9 throws. This is called 9-dart finish. As such, only 18 and 14 studies on the combination of scores that can obtain 501 points with 9 throws are known, and no studies have been conducted applying the exhaustive search algorithm. This paper proposed a division branch-and-bound algorithm as a method of simplifying the O(2n) exponential time performance complexity of the typical branch-and-bound method of a exhaustive search method, to polynomial time complexity. The proposed method limited the level to 8, jumped to a quotient level of 501/60, and backtracked to explore only possible score combinations in the previous level. The possible score combinations of the nine perfect games found with the proposed algorithm were 90(101 cases).

한국어

본 논문은 501 다트게임의 최소 다트 촉 투척 횟수인 9회에 대한 획득점수 조합을 찾는 연구를 수행하였다. 다트게임에서 한 번 투척으로 획득할 수 있는 최대 점수는 60점으로 60x8+21x1=501에 의거 60점을 8회, 21점을 1회 획득하면 9회 투척으로 퍼펙트 다트게임을 종료할 수 있다. 이를 9-다트 종료라 한다. 이와 같이 9회 투척으로 501점을 획득 가능한 점수의 조합에 관한 연구는 18개와 14개만 알려져 있으며, 전수탐색 알고리즘을 적용한 연구는 수행되지 않고 있다. 본 논문은 전형적인 전수탐색법인 분기한정법의 O(2n) 지수시간 수행 복잡도를 다항시간 복잡도로 단순화 시키는 방법으로 나눗셈 분기한정 알고리즘을 제안하였다. 제안된 방법은 레벨을 8로 한정시키고, 501/60의 몫 레벨로 점프하고 역추적으로 이전 단계에서의 가능한 점수 조합만을 탐색하는 방법을 적용하였다. 제안된 알고리즘으로 찾은 9회의 퍼펙트게임의 가능한 점수 조합은 90개(101개 경우)를 얻었다.

목차

요약
Abstract
Ⅰ. 서론
Ⅱ. 다트 게임 방법과 501 9-다트 게임 종료 경우 수 관련연구
Ⅲ. 나눗셈 분기한정 알고리즘
Ⅳ. 적용 및 결과 분석
Ⅴ. 결론
References

키워드

저자

• 이상운 [ Sang-Un Lee | 정회원, 강릉원주대학교 과학기술대학 멀티미디어공학과 ] Corresponding author

참고문헌

발행기관

간행물

표지보기 관심저널 등록

• 간행물명

  한국인터넷방송통신학회 논문지 [The Journal of the Institute of Internet, Broadcasting and Communication]

• 간기

  격월간

• pISSN

  2289-0238

• eISSN

  2289-0246

• 수록기간

  2001~2025

• 십진분류

  KDC 326 DDC 380