주어진 최소 무게로 부분 그래프의 수를 최대화하십시오.

Question

각 노드의 무게가있는 방향이없는 평면 그래프가 있습니다. 각 그래프가 고정 된 최소 가중치 (가중치의 합)에 도달해야한다는 조건을 고려하여 가능한 많은 연결된 분리 된 하위 그래프로 그래프를 분할하고 싶습니다 (EDIT : 또는 하위 그래프의 가능한 최소 평균 가중치에 도달 할 수 있음) 그것의 마디의). 노드의 가중치가 고정 된 최소값보다 큰 경우 단일 노드 만 포함하는 하위 그래프에서도 OK입니다.

create a subgraph out of every node 
while there is an underweight subgraph: 
    select the subgraph S with the lowest weight 
    find a subgraph N that has the lowest weight among the neighbouring subgraphs of S 
    merge S to N 

은 분명히이 최적이 아닌 :

는 내가 지금까지 발견 한 무엇 휴리스틱이다. 누구든지 더 나은 해결책을 얻었습니까? (어쩌면 나는 단지 무지하고 복잡한 문제는 아니지만 그래프 이론을 공부 한 적이 없다 ...)

EDIT (배경 세부 사항) :이 그래프의 노드는 통계 자료가 제공되어야한다. 그러나 개인 데이터 법안과의 충돌을 피하기 위해 단위당 최소 인구 규모가 필요합니다. 내 목표는 가능한 한 적은 정보가 길을 잃지 않도록 집계를 만드는 것입니다. 이웃 관계는 결과 단위가 인접해야하므로 그래프 모서리 역할을합니다.

집합의 대부분 (노드)이 최소 임계 값보다 훨씬 높습니다. 이들 중 약 5-10 %의 예 (최소 크기 50)에 표시되는, 다양한 크기와 임계 값 이하 :

Answer 1

이것이 NP 하드 최적화 문제이다. 예를 들어, Partition problem은 이것을 쉽게 줄일 수 있습니다 (평면성 속성이 문제를 일으키지 않음). 따라서 최적의 솔루션을 계산하는 알고리즘 (귀하의 의견에 최적의 솔루션을 요구하는 것 같습니다)은 "수천 개의 노드"에 대해 실용적이지 않을 수 있습니다.

실제로 최적의 솔루션이 필요하지만 좋은 솔루션이 필요한 경우 금식 검색이나 시뮬레이션 어닐링과 같은 로컬 최적화 방법을 사용합니다.

하위 그래프의 평균 가중치는 전체 그래프의 부분 그래프 수를 나눈 값이므로 중요한 것은 얻을 수있는 최대 하위 그래프 수를 찾는 것입니다. 이 수 N이 N 개의 서브 그래프로 초기 파티셔닝을 형성 한 다음, 예를 들어 (1) 하나의 서브 그래프에서 다른 서브 그래프로 노드를 이동시키고 (2) 인접한 두 서브 그래프 사이에서 두 개의 노드를 교환하여 모든 서브 그래프가 필요한 최소 가중치를 갖는 허용 가능한 해법. 수용할만한 해결책을 찾지 못하면 N을 줄이고 해결책을 찾을 때까지 다시 시작하십시오.

Answer 2

문제는 NP 하드이며 지수 솔루션을 강조합니다. 이 솔루션은 여러 가지 점을 개선하고, 몇 가지를 강조 할 것입니다.

전체 아이디어는 정점의 각 파티션이 몇 개의 가장자리로 연결되어있는 경우 그래프의 올바른 파티션을 만드는 가능한 모서리 세트를 모두 시도해보십시오. 각 파티션의 세트 수를 계산하는 최적의 경우를 찾을 수 있습니다 (최적 조건).

이전 방법에서는 검색을 확장 할 도메인이 없습니다.개별 세트 - 을 : 파티션 표현 - 전원 설정 :이 솔루션은 다음을 사용 하였다 들어 을 -받는 병렬 처리를 추가 가능한 모든 가장자리를 찾기 위해

public Partition Solve(Graph g, int min) 
{ 
    int max = 0; 
    Partition best; 

    // Find all the possible partitions for Edges 
    foreach(var S in PowerSet(g.Edges)) 
    { 
     // Build the Vertexes partition 
     var partition = BuildPartition(S); 

     // Test the min condition foreach component 
     if (IsInvalid(partition, min)) 
      continue; 

     // Continue if we already have something better 
     if (max >= partition.Length) 
      continue; 

     // Update 
     max = partition.Length; 
     best = partition; 
    } 

    return best; 
} 

public Partition BuildPartition(Graph g, IEnumerable<Edge> edges) 
{ 
    // Initially Every Vertex in alone in his partition 
    var partition = new DisjointSet(g.Vertexes); 

    foreach (var edge in edges) 
    { 
     // If the Vertexes of this edge are already in the same partition DO NOTHING 
     if (partition.Find(edge.V1) == partition.Find(edge.V2)) 
      continue; 

     // Join both subsets 
     partition.Union(edge.V1, edge.V2); 
    } 

    return parition; 
} 

public bool IsInvalid(Partition p, int min) 
{ 
    return p.Sets.Any(t => t.Sum(v => v.Weight) < min); 
} 

을 설정하면 다음과 같은 측면에서 솔루션을 향상시킬 수 있습니다 파워 셋과 IsInvalid 조건 - 유효 에지를 생성하는 더 나은 방법을 찾기가 이 설정 - minimun보다 더 많은 무게 정점에 대한 몇 가지 시작 케이스를 가지고

알고리즘의 순서를 (항상 별도의 서브 그래프에있을 것입니다 것은)에 의해 주어진다 파워 세트. - Power Set :이 경우 N 정점 그래프의 경우 최악의 경우 3N-6 에지 다음 O (2^N) 에지가됩니다. - 파티션 빌드 : V + E를 * LogV 다음 O이다 (NLogN) - IsInvalid : O (V)

마지막 해결할은 O (2^N * N * LogN) 사용 수를 계산하는 마지막 수식 of operations

희망이 도움말!

Answer 3

인스턴스의 세부 사항이 모든 것을 변경합니다.

임계 값이 자체적으로 임계 값을 초과하는 경우 중량이 인 정점을 호출하십시오. 두 개의 무거운 꼭지점이있는 부분 그래프는 두 개로 나눌 수 있기 때문에 절대로 이해할 수 없습니다. 따라서, 최적해 내의 부 그래프의 갯수는 무거운 버텍스를 포함하지 않는 부 그래프의 갯수에 더해진다.

결과적으로 무거운 꼭지점을 삭제하고 가능한 한 많은 유효한 부분 그래프를 만드는 데 집중할 수 있습니다. 지도에서 판단한대로 왼쪽에있는 요소는 연결된 요소로 구성되며 각 요소는 소수의 꼭지점을 갖습니다. 유효한 하위 그래프가 연결되어 있어야하므로 이러한 구성 요소는 독립적으로 해결할 수 있습니다. 작은 경우에, 모든 유효한 서브 그래프를 열거 할 수 있고 (Algorithm X을 실행하여 최대 카디널리티 패킹을 발견 할 수있다.