연속되는 요소가 서로 이어 지도록 목록의 요소를 재정렬 하시겠습니까?

Question

크기가 n 인 항목 l의 목록이 주어지고 i2이 i1이면 성공하는 술어 succeeds(i1,i2)이 주어지면 l의 모든 항목 i에 대해 succeeds(i,i.next)이 true를 반환하도록 l의 요소를 다시 정렬하는 가장 좋은 알고리즘은 무엇입니까?

Answer 1

각 요소 다음에 하나의 요소 만 성공할 수있는 경우이 문제는 2 차 시간에 해결할 수 있습니다.

실제로 데이터에서 연결된 목록을 만들어 배열로 반환하는 것을 모방합니다. 병목 현상은 각 요소 (요소를 따르는 요소)를 찾는 것입니다.

의사 코드 : 각 요소를 성공할 수있는 요소의 수에는 제한이없는 경우

specialSort(array,n) 
    create an array a of size n 
    for each i from 0 to n: 
     find j such that succeeds(array[i],array[j]) == true //this may require linear search, so it is O(n) 
     if there is such j: 
      a[i] = j 
     else: 
      a[i] = -1 
    end for 
    find i such that for any j: a[j] != i 
    create empty result array of size n 
    j = 0; 
    while (i != -1): 
     result[j++] = array[i] 
     i = a[i] 
    end while 
    return result 

, 당신에게 준 @templatrtypedef 대답은 정확하고 문제는 해밀턴을 찾는 것과 같습니다 통로.

편집 : 그런 다음, 각 요소에 대해 두 개 이상의 후속하지만 관계 succeed()이있을 수있는 경우도 [NO "루프"] 정렬되지 않도록
참고 :이 문제는 잘 정렬 된 관계에 대한 solveable입니다 이 문제로부터 각각 DAG을 만들 수 있습니다. 각 요소는 정점이며, succeed(a,b) == true과 같은 모든 쌍의 가장자리가 있습니다. topological orderring을 사용하고 그것을 반환하십시오.
병목 목이 가장자리를 찾고 있기 때문에 이것은 또한 2 차 시간입니다.

Answer 2

성공 관계가 될 수있는 것에 대한 제한이 없다면 (즉, 전이, 반사, 대칭 등일 필요는 없습니다),이 문제는 NP- NP- 하드 Hamiltonian path problem. 감소는 실제로 매우 간단합니다 : 그래프 G가 주어지면 그래프에서 노드의 배열을 success 관계로 생성합니다. 그러면 원래 그래프에서 u에서 v까지의 가장자리가있는 경우 v가 성공합니다. 이 설정을 통해 배열 요소 (노드)를 성공 관계 (노드를 연결하는 가장자리)로 정렬하는 방법을 찾는 것은 각 노드를 정확히 한 번 방문하기 때문에 원래 그래프에서 해밀턴 경로를 찾는 것과 같습니다. 결과적으로 P = NP가 아니면 효율적인 알고리즘을 찾을 수 없습니다.

부정적인 결과로 불편을 끼쳐 드려 죄송합니다.