우선 순위 함수/알파벳 순서의 극단을 찾으십시오.

Question

E의 알파벳 배열 a1,a2,...aN이 있습니다. |N| >> |E|이라고 가정합니다.

알파벳의 각 기호에 대해 고유 한 정수 우선 순위 = V(sym)을 정의합니다. 단순화를 위해 V{i} := V(symbol(ai))을 정의합시다.

가 어떻게에 대한 우선 순위 기능 V 찾을 수 있습니다 I는 알파벳의 우선 순위/순열을 찾을 필요, 즉

Count(i)->MAX | V{i} < V{i+1} 

을하는 조건 V{i}<V{i+1}을 만족 위치 i의 수, 최대 값입니다.

편집 1 :주의 깊게 읽으십시오. 배열 ai이 주어졌으며 작업은 V 함수를 생성하는 것입니다. 우선 순위 함수로 입력 배열을 정렬하는 것에 대해서는 이 아니라입니다.

편집-2 : 예

E = {a,b,c}; A = 'abcab$'; (여기 $, V는 {$}은 = + 무한대 인공 종료 기호 =) 최적의 우선 순위 기능의

하나는 : V{a}=1,V{b}=2,V{c}=3, 미를 준다 배열 요소 사이의 부호 뒤에는 a<b<c>a<b<$이 표시되어 4 '<'의 합계가 5가됩니다.

Answer 1

요소가 우선 순위를 매길 수 없다면 이는 사소한 일입니다. 그냥 우선 순위별로 정렬하십시오. 그러나 당신은 동등한 우선 순위를 가질 수 있습니다.

우선 우선 순위에 따라 알파벳을 정렬합니다. 그런 다음 가장 긴 상승 하위 시퀀스를 추출합니다. 그것이 당신의 대답의 시작입니다. 남아있는 것에서 가장 긴 상승 서브 시퀀스를 추출합니다. 당신의 대답에 그것을 추가하십시오. 전체 알파벳이 추출 될 때까지 추출 프로세스를 반복하십시오.

나는 이것이 최적의 결과를 제공한다고 믿지만 나는 그것을 증명하려고하지 않았다. 그것이 완벽하게 최적이 아니라면, 여전히 꽤 좋을 것입니다.

이제 문제를 이해할 수 있다고 생각합니다. 문제를 해결할 좋은 알고리즘이 없다고 말할 수 있습니다.

이것을 보시려면 꼭지점이 당신의 요소 인 방향 그래프를 만들고, 그 가장자리가 한 요소가 다른 요소보다 얼마나 빨리 앞서 왔는지를 나타내는하자. 방향성이있는 비순환 그래프를 얻고, 가장자리를 사용하여 부분 집합을 만들고, 전체 선형 순서가 될 때까지 순서 관계를 추가하여 우선 순위 함수를 쉽게 얻을 수 있도록 충분한 가장자리를 제거하여 우선 순위 함수를 만들 수 있습니다. 이 모든 것은 드롭해야 할 모서리를 파악한 후에는 간단합니다. 반대로 지시 그래프와 최우선 순위 함수를 사용하면 어떤 모서리 집합을 놓기로 결정해야하는지 쉽게 판단 할 수 있습니다.

따라서 문제가 얻을 수있는 그래프를 지시 당신이 에서 드롭해야 할 가장자리의 최소한을 파악 전적으로 동일하다 비순환 그래프 감독 . 그러나 http://en.wikipedia.org/wiki/Feedback_arc_set에 의하면 이것은 최소 피드백 아크 세트라고하는 알려진 NP 어려운 문제입니다. begin update 따라서 그래프를 작성할 수있는 좋은 알고리즘이 있다는 것은 거의 없습니다. 최종 업데이트

실용적으로 해결해야 할 경우, 어떤 종류의 욕심 많은 알고리즘을 사용하는 것이 좋습니다. 항상 옳은 것은 아니지만 일반적으로 합리적인 시간에 다소 합리적인 결과를 제공합니다.

업데이트 : 모론은 정확합니다. NP- 하드를 증명하지 못했습니다. 그러나 실제로 문제가 NP 하드라고 믿을만한 경험적으로 좋은 이유가 있습니다. 자세한 내용은 주석을 참조하십시오.

Answer 2

아크 그래프를 오일러 경로로 배열 할 수있는 방향 그래프의 최소 피드백 아크 세트는 간단합니다. 나는 http://www14.informatik.tu-muenchen.de/personen/jacob/Publications/JMMN07.pdf에서 인용 :

우리가 아는 한

, 같은 그래프에서 설정 한 최소 피드백 호의 복잡성 상태가 열려 있습니다. 그러나 뉴먼 표제어, 첸 및 로바 츠 [1 정리 4] 은 일반적인 최소 피드백 아크 설정 문제에 대한 16/9 근사 알고리즘을 초래할 것이다 [이 문제] 대한 다항식 알고리즘 , 현재 가장 잘 알려진 O (log n 로그 로그 n) 알고리즘 [2]에 비해 을 향상시킵니다.

1. Newman, A .: 최대 비순환 부분 그래프 문제와 차수 3 그래프. In : Proceedings of the 4th 국제 워크샵 에 대한 근사 알고리즘 조합 최적화 문제, APPROX. 유향 그래프의 멀티 컷 및 근사 최소 반환 세트 및 G., Naor, J., Sieber, B., Sudan, M. : G., Naor, J., Sudan, M. In : 제 4 회 국제 학술회 논문집 정수 프로그래밍에 대한 설명 및 조합 최적화. (1995) LNCS 는 14-28