주기를 포함하는 지정된 지시되지 않은 가중치 그래프에서 위상 정렬을 수행 할 방법을 찾고 있습니다. 결과에는 정점의 순서뿐만 아니라 지정된 순서에 위배되는 모서리 세트가 포함되어야합니다. 이 모서리는 최소화되어야한다.최소 수의 위반 된 에지가있는 순환 그래프의 위상적인 종류
입력 그래프가 잠재적으로 크기 때문에 지수 시간 알고리즘을 사용할 수 없습니다. 다항식 시간에 최적해를 계산하는 것이 불가능하다면 주어진 문제에 대해 어떤 경험적 방법이 합리적일까요?
Eades, Lin 및 Smyth는 A fast and effective heuristic for the feedback arc set problem을 제안했다. 원본 기사는 유료화 벽 뒤에 있지만 무료 사본은 here에서 얻을 수 있습니다.
들어오는 호가없는 정점을 선택하고, 그래프에서 정점을 뺀 다음 순서에 정점을 붙임으로써 정점 순서를 만드는 알고리즘이 있습니다. (알고리즘을 재귀 적으로 설명 하겠지만, 그렇게 구현하지 않아도됩니다.) Eades-Lin-Smyth 알고리즘은 나가는 호가없는 정점을 찾고 에을 추가합니다. 물론 모든 정점에 들어오고 나가는 호가있을 수 있습니다. 이 경우 수신 및 송신의 차이가 가장 큰 정점을 선택하십시오. 의심 할 여지없이 실험을위한 여지가 있습니다.
증명 가능한 최악의 경우 동작을 나타내는 알고리즘은 선형 프로그래밍 및 그래프 컷을 기반으로합니다. 이것들은 깔끔하지만 보장은 이상적입니다 (log^2 n 또는 log n log log n 번은 필요한만큼 많은 호가됩니다). 그리고 나는 효율적인 구현이 상당히 프로젝트 일 것이라고 생각합니다.
이 질문은 지금도 여러모로 많은 의견을 듣고 있습니다. 필자는 그 논문을 가까이서 보았습니다. 마지막 단락에서 다윗이 언급 한 근사 알고리즘에 관심이 있다면, 그는 "나누기 - 및 - 확산 통계를 통한 근사 알고리즘 ", Even, Naor, Rao, Schieber, ACM 저널, Vol. 47, No. 4, 2000 년 7 월, 585-616 페이지, 가중치가있는 자 그래프의 경우에도 로그 로그 로그 근사를 수행합니다. –
선형 프로그래밍을 기반으로하는 가중치가없는 최소 피드백 집합 문제 (제거 할 모서리 수를 최소화)에 대한 초기 log^2 n 근사값은 "다차원 최대 흐름 최소 컷 정리 및 그 용도에서 찾을 수 있습니다. Designing Approximation Algorithms ", Leighton, Rao, ACM 저널, Vol. 46, No. 6, November 1999, pp. 787-832. –
[의견 호 설정] (http://en.wikipedia.org/wiki/Feedback_arc_set)이 아닙니까? 잔여 DAG를 토폴로지별로 정렬하여 주문을받을 수 있습니다. –
또한 최소 솔루션 (제거 된 각 아크가 DAG에서주기를 완료 함) 또는 최소 솔루션 (가능한 한 제거 된 아크가 거의 없음)을 원하십니까? –
@DavidEisenstat 실제로 하나의 호가 더 많거나 적은 경우 실제로는별로 신경 쓰지 않고 간단히 처리해야합니다. 일부 알고리즘이 런타임을 두 번 수행하고 적은 호가 적은 솔루션 만 찾으면 경제적이지 않습니다. 문제는 피드백 아크 셋 (feedback arc set) 인 것 같지만,이 경우 엔 NP가 어렵 기 때문에 근사치가 필요합니다. – orsg