Thuật toán cho việc tìm kiếm những con đường khác nhau từ A đến B trong trọng, đạo diễn, đồ thị cyclic

Question

Giả sử chúng ta có một đạo, trọng và cyclic đồ thị.

Giả sử chúng ta chỉ quan tâm đến những con đường với tổng trọng lượng dưới MAX_WEIGHT

là gì thích hợp nhất (hoặc bất kỳ) thuật toán để tìm số các đường dẫn riêng biệt giữa hai nút A và B có tổng trọng lượng dưới MAX_WEIGHT?

P.S: Nó không phải là bài tập về nhà của tôi. Chỉ là dự án cá nhân, phi thương mại.

Answer 1

Nếu số nút và MAX_WEIGHT là không quá lớn (và tất cả trọng lượng là các số nguyên), bạn có thể sử dụng lập trình năng động

unsigned long long int num_of_paths[MAX_WEIGHT+1][num_nodes]; 

khởi tạo bằng 0, trừ num_of_paths[0][start] = 1;.

for(w = 0; w < MAX_WEIGHT; ++w){ 
    for(n = 0; n < num_nodes; ++n){ 
     if (num_of_paths[w][n] > 0){ 
      /* for each child c of node n 
      * if w + weight(n->c) <= MAX_WEIGHT 
      * num_of_paths[w+weight(n->c)][c] += num_of_paths[w][n]; 
      */ 
     } 
    } 
} 

giải pháp là tổng của num_of_paths[w][target], 0 <= w <= MAX_WEIGHT.

Answer 2

Đệ quy đơn giản. Bạn có nó trong thời gian mũ. Rõ ràng, không cho phép chu kỳ trọng lượng bằng 0.

chức năng Noe (nút N, hạn chế trọng lượng W)

1. không. đường dẫn bằng không nếu tất cả các cạnh đi có khối lượng> W

2. nếu không thì không. của đường dẫn là tổng số đường dẫn thu được bằng tổng (noe (C1, W-W1), số (C2, W-W2), ... noe (Cn, W-Wn)) trong đó C1 ... Cn là các nút được kết nối với N mà W-Wi không âm, trong đó Wi là trọng lượng của cạnh kết nối, được viết bằng ngôn ngữ yêu thích của bạn.

Giải pháp eficient khác nên tồn tại, dọc theo thuật toán Dijkstra, nhưng tôi nghĩ điều này là đủ cho bài tập ở nhà.

Answer 3

Vấn đề của bạn là trường hợp tổng quát hơn của K-Disjoint Path In directed planar graphs, với không cố định K.

K đường rời nhau vấn đề cho đồ thị phẳng đạo là như thế này:

cho: một đồ thị phẳng có hướng G = (V ; E) và cặp k (r ; s); ....; (r _k; s _k) của đỉnh G;

tìm: k theo chiều dọc theo chiều dọc-phân tách các đường dẫn hướng P ; ...; P _k trong G, trong đó P _i chạy từ r _i đến s _i (i = 1; ....; k).

Trong k rời nhau đường dẫn mà bạn có thể vẽ arc từ tất cả s _i đến B, và cũng arc từ A đến tất cả r _i bằng cách này bạn tạo đồ thị G' từ G.

Bây giờ nếu bạn có thể giải quyết vấn đề của bạn trong G 'trong P bạn có thể giải quyết đường dẫn k-disjoint trong G, Vì vậy, P = NP.Nhưng nếu bạn đọc giấy liên kết, nó sẽ đưa ra một số ý tưởng cho đồ thị chung (giải quyết đường dẫn k-disjoint với cố định k) và bạn có thể sử dụng nó để có một số xấp xỉ gần đúng.

Ngoài ra còn có thuật toán phức tạp hơn giải quyết vấn đề này trong P (đối với k cố định) trong biểu đồ chung. nhưng trong tất cả nó không phải dễ dàng (đó là bởi Seymour).

Vì vậy, lựa chọn tốt nhất của bạn hiện tại là sử dụng thuật toán brute force.

Chỉnh sửa: Vì MAXWEIGHT độc lập với kích thước đầu vào của bạn (kích thước biểu đồ của bạn) Nó không ảnh hưởng đến vấn đề này, Vì nó là NP-Hard cho đồ thị không bị giới hạn, bạn vẫn có thể kết luận nó là NP-Hard .