어떤 공정 이전의 제품 상태값 254개가 있고,

이 공정 이후의 제품 상태값 248개가 있습니다.

생산과정 중 손망실이 있기 때문에 개수 차이는 당연하며,

고약하게도 저 덩어리와 이 덩어리가 같은 덩어리라는 것은 아는데, 그 안에서 개별 제품들이 1:1로 매칭되지는 않습니다.

저는 이 매칭되지 않는 놈들을 매칭해보려고 합니다.

전후공정 모두에서 제법 선형성이 있는 여러 지표들을 이용해서,
각 지표들의 전후공정 모두 "통계적 위치" 를 구하고,
그 위치간 거리가 최소가 되는 거리 쌍을 구하고자 합니다.

즉, 이 문제는 고차원 공간상의 254개와 248개의 점을 1:1 매칭시켜서 그 거리가 최소가 되게 하는 매칭쌍을 구하는 문제 입니다.

이걸 A* 알고리즘으로 접근해 보았습니다.

우선 254 by 248 메트릭스를 만들어서 모든 점 간의 거리를 담고
각 행마다 하나를 고르고, 그걸 고르면 그 행, 렬은 삭제됩니다.

휴리스틱은 남은 메트릭스의 각 행마다의 최소값들의 총합으로 되어 있습니다. 매 행에서 그리디하게 최소값을 선택할 수 있을 리가 없으니까, 이건 도달 불가능한 아이디얼 케이스 입니다. 휴리스틱으로 쓰기에 모자람이 없어 보입니다.

어..... 알고리즘 코딩이 틀리지는 않았습니다. 9 by 9, 10 by 10 에서 옳은 결과가 나옴을 확인했습니다.

근데 실전 데이터에서 밤 새 돌고 있습니다. 사실 이럴지도 모르겠다.... 라고 짐작은 하고 있었는데요,

정답이 있을 것 같지는 않은데, 그냥 아무 조언이나 좀 부탁드립니다. 뭘 시도해 볼까요?