DAG : 그룹화 된 노드의 항목 간 거리 최소화

Question

다른 노드의 항목에 연결되는 항목 목록 인 노드가있는 비순환 식 그래프가 있습니다. 이런 종류의 :

entry  ] 
entry--| ] node 1 
entry | ] 
----- | 
entry<-| ] node 2 
entry | ] 
----- | 
entry | ] node 3 
entry--| ] 

노드 내의 항목 순서는 고정되어 있습니다. 항목은 링크되는 항목에 대한 절대 색인이있는 배열에 저장됩니다. 항목 당 최대 1 개의 링크가 있으며 모든 노드에는 최소한 하나의 링크가 있습니다. (즉, 이것은 고도로 연결된 그래프 임). 그래프에는 약 40,000 개의 노드로 그룹화 된 약 100,000 개의 항목이 들어 있습니다.

내가해야 할 일은 링크의 상대 인덱스를 사용하고 기본 데이터 구조를 압축 할 수 있도록 노드를 재정렬하여 항목 간의 최대 거리를 최소화하는 것입니다.

압축 및 성능이 목표이기 때문에 외부 데이터 (점프 테이블, 목록의 특수 점프 요소)를 추가하는 솔루션은 수용 할 수 없습니다. 엔트리 간의 최대 거리를 최소화하는 노드를 재정렬하기위한 알고리즘이 정말로 필요합니다. 이견있는 사람?

Answer 1

설명하는 문제는 최대 거리를 최소화하는 방법입니다. 나는 NP가 힘들어서 간단한 해결책이 그리 좋지 않을 것이라고 생각한다. 그러나 ILP 문제로 모델링하고이를 해결할 수 있습니다.

그런 다음 M을 목표로 최소화하십시오.

모든 링크 l_i에 대한 제약 조건은 M>= abs(s_i-e_i)입니다. s_i 및 e_i은 링크의 시작 및 끝 항목의 절대 색인을 나타냅니다. n_is_i=n_i+c_i와 같이 s_i 노드의 인덱스에 속하는 c_i가가 (다른 항목 중) 그 노드 내에 고정 된 오프셋에

이러한 항목은 자신이 속한 노드의 점에서 쓸 수있다. e_i도 비슷하게 다시 작성됩니다. 그런 다음 솔버로 n_i을 최적화하도록 설정되었습니다.