본문 바로가기

추천 검색어

실시간 인기 검색어

학술논문

이차계획법에 기반한 소파 이동 문제의 상한선 개선

이용수 0

영문명
Improving Upper Bound for the Moving Sofa Problem Based on Quadratic Programming
발행기관
한국과학영재교육학회
저자명
윤예준(Yejoon Yoon) 한준희(Junhee Han) 윤상현(Sanghyun Yoon)
간행물 정보
『과학영재교육』제16권 제1호, 131~143쪽, 전체 13쪽
주제분류
사회과학 > 교육학
파일형태
PDF
발행일자
2024.04.30
4,360

구매일시로부터 72시간 이내에 다운로드 가능합니다.
이 학술논문 정보는 (주)교보문고와 각 발행기관 사이에 저작물 이용 계약이 체결된 것으로, 교보문고를 통해 제공되고 있습니다.

1:1 문의
논문 표지

국문 초록

소파 이동(moving sofa) 문제는 직각의 모서리를 끼고 있는 폭이 1인 복도를 통과할 수 있는 최대 단면적 소파를 찾는 이산기하 분야의 문제로, 1966년 Moser에 의해 제시된 이후 아직 미해결 문제로 남아 있다. 현재까지 알려진 최대 단면적의 최대 하한은 1992년 Gerver에 의해 발견된 2.2195...이고 최소 상한은 2018년 Kallus & Romik에 의해 증명된 2.37이다. 최소 상한 2.37이 다소 느슨한 것으로 보이는 반면에 최대 하한 2.2195...을 향상할 여지가 작다는 실험적 근거가 제시되었는데, 본 연구에서는 이 점에 주목하여 상한을 Gerver의 최대 하한에 좀 더 근접하도록 낮추었다. 이를 위해 기하학적 분기 한정법(geometric branch-andbound)과 이차계획법(quadratic programming)에 기반한 최적화 알고리즘을 구성하고, 알고리즘의 효율적 탐색을 위해 다양한 기하학적 성질을 증명하였다. 약한 기하학적 가정하에서, 제안한 최적화 알고리즘을 이용하여 개선된 상한 2.3361을 Kallus & Romik에 비해 훨씬 짧은 계산시간으로 얻었다.

영문 초록

The moving sofa problem is a problem in discrete geometry that involves finding a shape with the maximum area that can pass through a right-angled corner in a hallway with unit width, and has remained an open problem since it was posed by Moser in 1966. The largest lower bound on the maximum area known to date is 2.2195..., found by Gerver in 1992, and the smallest upper bound is 2.37, proved by Kallus and Romik in 2018. While the minimum upper bound of 2.37 appears to be somewhat loose, experimental evidence suggests that there is little room for improvement in the largest lower bound of 2.2195.... In this study, we aim to lower the upper bound to be closer to Gerver’s maximum lower bound. For this purpose, we construct an optimization algorithm based on geometric branch-and-bound and quadratic programming, and prove various geometric properties for efficient search of the algorithm. Under a reasonable geometric assumption, the proposed optimization algorithm obtains an improved upper bound of 2.3361 with much shorter computation time than Kallus and Romik.

목차

Ⅰ. 서론
Ⅱ. 연구 방법
Ⅲ. 결론 및 제언
참고문헌

키워드

해당간행물 수록 논문

참고문헌

교보eBook 첫 방문을 환영 합니다!

신규가입 혜택 지급이 완료 되었습니다.

바로 사용 가능한 교보e캐시 1,000원 (유효기간 7일)
지금 바로 교보eBook의 다양한 콘텐츠를 이용해 보세요!

교보e캐시 1,000원
TOP
인용하기
APA

윤예준(Yejoon Yoon),한준희(Junhee Han),윤상현(Sanghyun Yoon). (2024).이차계획법에 기반한 소파 이동 문제의 상한선 개선. 과학영재교육, 16 (1), 131-143

MLA

윤예준(Yejoon Yoon),한준희(Junhee Han),윤상현(Sanghyun Yoon). "이차계획법에 기반한 소파 이동 문제의 상한선 개선." 과학영재교육, 16.1(2024): 131-143

결제완료
e캐시 원 결제 계속 하시겠습니까?
교보 e캐시 간편 결제