해밀턴 경로는 N개의 정점으로 이뤄진 무방향 그래프에 대해 A1, A2, ..., AN 으로 표현된다.

여기서 A1, A2, .., AN은 1이상 N이하의 정수이며, 여러번 등장하는 숫자가 존재하지 않아야 하며,

2이상 N이하의 Ai에 대해 정점 Ai-1과 Ai 사이에는 간선이 존재하는 경로를 말한다.

이를 풀어서 설명하면, 모든 정점을 정확히 한번씩 방문하고, 경로의 시작은 A1번 정점에서,

종료는 AN에서 하는 경로이며, Ai-1번 정점을 거쳐 그 다음에 Ai번 정점으로 이동할 경우 Ai-1번과 Ai를 잇는 간선을 거쳐 이동하게 된다.

경로의 비용은 거치게되는 간선의 가중치의 합이다.

각 정점에 라벨이 붙어있고(i번 정점의 라벨은 Li라고 한다), 모든 정점쌍에 대해 간선이 주어진 그래프에 대해 1번으로 시작해서 2번으로 종료되는 해밀턴 경로 중

최소를 구하는 프로그램을 작성하라. i번 정점과 j번 정점 사이를 잇는 간선 Eij의 가중치는 다음과 같다.

Eij = length(Li)² + length(Lj)² - length( LCP(Li,Lj) )²

여기서 length는 문자열(혹은 라벨)의 길이를 뜻하고 length(X)² 는 length(X) * length(X)와 같다.

LCP(X,Y)는 문자열 X와 Y사이의 최대 길이의 접두사(unhappy의 un-이나 preheat의 pre-처럼,

다른 단어 앞에 붙어 그 단어의 뜻을 달라지게 하는 글자(들))를 뜻한다.

가령 X = "AABB" 이고, Y = "AABC"일 경우 LCP(X,Y) = "AAB"가 된다.

약간 다른 해밀턴 경로 timer 1s memory - MB

약간 다른 해밀턴 경로 1s - MB