#action Blog 블로그 더하기
##Blog
{{{#!blog hyacinth 2021-03-26T18:22:43 그래프 그리기
그래프 그리기 재밌다. [wiki:Python/인접%20행렬%20시각화 Python/인접 행렬 시각화]

파이썬은 데이터 시각화 툴이 너무 잘 되어 있어서 재미있다.
attachment:img_up2/Figure_3.png
마지막 그림은 WikipediaKo:해밀턴_경로  중 하나이다. 그리고만 끝내기 심심해서 모든 해밀턴 경로의 경우의 수를 찾아봤다. DFS를 조금 변형해서 현재 vertex의 방문 가능한 지점을 쌓아두고 꺼내 쓰면서 DFS를 복귀할 때 방문을 초기화하고 해밀턴 경로가 성립하는 경우를 세면서 찾을 수 있다. NP-완전 문제이기 때문에 그냥 이렇게 완전 탐색(exhaustive search)으로 찾아야 한다. 해밀턴 경로를 찾기 위한 조건은 아직 발견되지 않았다.  5X5 바둑판은 4324개의 해밀턴 경로가 있다. 5X5는 금방 찾는다. 7X7 바둑판은 10년 전 쯤 세는데 매스매티카에서 5시간 걸렸다는 듯 하다[[footnote(O(n!)이나 잘 해봐야 O(2^n*n^2)이다. (...))]]. 내 라이젠 3600, C++ 구현에서 찾았을 때 몇 분 기다리다가 응답이 없어서 세는걸 그만 두었다.
}}}

[[HTML(<center>)]]
http://hyacinth.byus.net/img/flower.jpg
[[HTML(</center>)]]