Loading [MathJax]/jax/output/HTML-CSS/config.js
한국어
Français
Deutsch
Italiano
Español
English
简体中文
日本語
ko
'TSP: travelling salesman problem' 태그의 글 목록::::수학과 사는 이야기
수학과 사는 이야기
TSP: travelling salesman problem
반응형
해밀톤 경로와 세계 일주
수학이야기/확률통계
2023. 1. 3. 11:34
해밀토니안(Hamiltonian) 1857년 영국의 수학자 해밀톤은 아래와 같은 세계 일주 게임을 소개했다. 정십이면체의 꼭짓점 20개에 세계의 이름난 도시 이름을 붙이고 어느 한 도시를 출발하여 모서리를 따라 다른 도시를 모두 방문하고 출발한 도시로 돌아오시오. 이때 한 번 지나간 도시를 다시 지날 수는 없다. 이산수학 문제는 쉬워 보이지만 막상 풀어보면 쉽지 않은 것들이 많다. 먼저 그래프에서 모든 꼭짓점을 지나는 경로는 '해밀톤 경로(Hamiltonian path)'이고 출발점과 끝점이 같으면 '해밀톤 회로(Hamiltonian circuit)'이다. 해밀턴 회로를 가진 그래프를 '해밀토니안(Hamiltonian)'으로 부른다. 어떤 그래프가 '해밀토니안'인가를 단박에 알아내기는 쉽지 않다. 해밀톤..
이전
1
다음
티스토리툴바
관리메뉴열기
개인정보
티스토리 홈
포럼
로그인
수학과 사는 이야기
구독하기
닫기
단축키
내 블로그
내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W
블로그 게시글
글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C
모든 영역
이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift
+
/
⇧
+
/
* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.