Thuật toán truy hồi ngược để giải quyết bài toán phân vùng

Question

Xin chào, tôi đang tìm một số trợ giúp để tìm một thuật toán phân chia một số các số dương thành các phần k sao cho mỗi phần có tổng số (xấp xỉ) cùng một giá trị. giả sử chúng ta có

1,2,3,4,5,6,7,8,9 vi k = 3 thn thuật toán nên phân vùng nó như thế này 1,2,3,4,5 | 6, 7 | 8,9 thứ tự của các phần tử không thể thay đổi ... Tìm thuật toán tham lam dễ dàng nhưng tôi đang tìm kiếm một phiên bản backtracking luôn trả về giải pháp tối ưu ...

Annyone có gợi ý gì không?

Answer 1

Đây là giải pháp không sử dụng bất kỳ cấu trúc dữ liệu động nào như danh sách. Chúng hoàn toàn không cần thiết và trong thực tế làm cho thuật toán chậm hơn nhiều so với cần thiết.

Cho K là số phân vùng ở đây và N là số phần tử trong mảng của bạn.

int start[K]; 

void register() { 
    /* calculate the error between minimum and maximum value partitions */ 
    /* partition boundaries are start[0], start[1], start[2], ... */ 
    /* if lower error than previously stored, remember the best solution */ 
} 

void rec(int s, int k) { 
    if (k == K) register(); 
    for (int i = s; i < N; i++) { 
    start[k] = i; 
    rec(i + 1, k + 1); 
    } 
} 

/* entry */ 
start[0] = 0; 
rec(1, 1); 
/* then output the best solution found at register() */ 

Lưu ý: đây là thuật toán O (n ^K). Đó là số mũ phụ vì đây là số không phải tương đương với vấn đề phân vùng NP-chung chung ở đây bạn đang tìm kiếm các đoạn liền nhau của một mảng tuyến tính thay vì các tập con tùy ý của một tập hợp nhất định.

Answer 2

Bạn có ý nghĩa gì với giải pháp tối ưu? Tôi tin rằng bạn có nghĩa là một trong đó giảm thiểu tổng của mỗi khoảng cách phân vùng để phân vùng tối ưu. Phân vùng tối ưu sẽ là phân vùng mà các phần tử của nó tổng bằng tổng số tiền chia cho số phân vùng.

Nếu bạn không bận tâm về hiệu quả, thì có lẽ cách tiếp cận thô này là đủ tốt cho bạn. Tôi chưa thử nghiệm thuật toán để kiểm tra tính chính xác của nó, vì vậy hãy cẩn thận.

void FindPartitions(int[] numbers, int i, IList<int>[] partitions, int currentPartition, IList<int>[] bestSolution, ref int minDistance) 
{ 
    if (i == numbers.Length) 
    { 
     int sum = numbers.Sum(); 
     int avg = sum/partitions.Length; 
     int currentDistance = 0; 
     foreach (var partition in partitions) 
      currentDistance += Math.Abs(partition.Sum() - avg); 
     if (currentDistance < minDistance) 
     { 
      minDistance = currentDistance; 
      for (int j = 0; j < partitions.Length; j++) 
       bestSolution[j] = new List<int>(partitions[j]); 
     } 
    } 
    else 
    { 
     partitions[currentPartition].Add(numbers[i]); 
     FindPartitions(numbers, i + 1, partitions, currentPartition, bestSolution, ref minDistance); 
     partitions[currentPartition].RemoveAt(partitions[currentPartition].Count - 1); 
     if (currentPartition < partitions.Length - 1) 
      FindPartitions(numbers, i, partitions, currentPartition + 1, bestSolution, ref minDistance); 
    } 
} 

Answer 3

Đây là thuật toán đệ quy trong Javascript. Hàm này trả về tổng số mà mỗi nhân viên sẽ được chỉ định. Cho phép nói bookLoads mảng đầu vào là một mảng của các số dương mà bạn muốn chia một cách công bằng càng tốt vào k-bộ phận (giả sử trong công nhân k)

Đây là một fiddle làm việc: https://jsfiddle.net/missyalyssi/jhtk8vnc/3/

function fairWork(bookLoads, numWorkers = 0) { 
    // recursive version 

    // utilities 
    var bestDifference = Infinity; 
    var bestPartition = {}; 
    var initLoads = {}; 
    var workers = Array.from({length: numWorkers}, (val, idx) => { 
     initLoads[idx] = 0; 
     return idx; 
    }); 
    var bookTotal = bookLoads.reduce((acc, curr) => {return acc + curr}, 0); 
    var average = bookTotal/bookLoads.length; 

    // recursive function 
    function partition(books = bookLoads, workers, loads={}) { 

     // if only one worker give them all the books 
     if (workers.length == 1 && books.length > 0) { 
     var onlyWorker = workers[0]; 
     loads[onlyWorker] += books.reduce((acum, curr, idx, arr) => { 
           return acum + curr; 
          },0); 
     books = []; 
     } 

     // base case 
     if (books.length == 0) { 
     var keys = Object.keys(loads); 
     var total = 0; 
     for (let key = 0; key < keys.length; key++) { 
      // square so that difference shows 
      total += Math.pow(Math.abs(average - loads[keys[key]]), 2); 
     } 
     if (total < bestDifference) { 
      bestDifference = total; 
      bestPartition= loads; 
     } 
     return bestPartition; 
     } 

     var currBookLoad = books[0]; 

     // add book to curr worker 1 
     var newWorker1Loads = Object.assign({}, loads); 
     var worker1 = workers[0]; 
     newWorker1Loads[worker1] = newWorker1Loads[worker1] + currBookLoad || currBookLoad; 
     partition(books.slice(1), workers, newWorker1Loads) 

     // give to next worker 
     var newNextWorkerLoads = Object.assign({}, loads); 
     var worker2 = workers[1]; 
     newNextWorkerLoads[worker2] = newNextWorkerLoads[worker2] + currBookLoad || currBookLoad; 
     partition(books.slice(1), workers.slice(1), newNextWorkerLoads) 

     return bestPartition; 
    } 
    // function call 
    return partition(bookLoads, workers, initLoads) 
} 
fairWork([3,1,2,3], 3) 
//Result will be: Object {0: 3, 1: 3, 2: 3} 
fairWork([1,2,3,4,5,6,7,8,9], 3) 
//Result will be: Object {0: 15, 1: 13, 2: 17}