Vấn đề tuyến đường trong biểu đồ: giảm chi phí cạnh trung bình thay vì tổng chi phí

Question

Tôi có biểu đồ có trọng số, không có trọng số âm và tôi muốn tìm đường dẫn từ nút này sang nút khác, cố gắng giảm thiểu chi phí cho một bước . Tôi không cần phải giảm thiểu tổng chi phí của chuyến đi (ví dụ: Dijkstra làm) nhưng chi phí mỗi bước trung bình. Tuy nhiên, tôi có một ràng buộc: K, số lượng nút tối đa trong đường dẫn.

Vì vậy, ví dụ như để đi từ A đến J có lẽ Dijkstra sẽ tìm thấy con đường này (giữa ngoặc trọng lượng)

A (4) D (6) J -> total cost: 10 

và các thuật toán tôi cần, thiết K = 10, sẽ tìm thấy một cái gì đó giống như

A (1) B (2) C (2) D (1) E (3) F (2) G (1) H (3) J -> total cost: 15 

Có bất kỳ thuật toán nổi tiếng nào cho vấn đề này không?

Xin cảm ơn trước.

Eugenio

Chỉnh sửa câu trả lời cho templatetypedef. Một số câu hỏi:

1) Thực tế là có thể xảy ra chu kỳ nhiều lần để giảm tốc độ trung bình không tốt cho vấn đề của tôi: có lẽ tôi đã đề cập đến nó nhưng tôi không muốn truy cập cùng một nút nhiều hơn một lần

2) Có thể khai thác thực tế là tôi không có trọng số âm?

3) Khi bạn nói O (kE) bạn có nghĩa là cho toàn bộ thuật toán hoặc chỉ cho phần bổ sung? Hãy thực hiện việc thực hiện đơn giản này trong C trong đó n = số nút e = số cạnh, d là một vector với khoảng cách, vector pa với tiền thân và cạnh cấu trúc (u, v, w) ghi nhớ các cạnh trong biểu đồ

for (i = 0; i < n; ++i) 
    d[i] = INFINITY; 

    d[s] = 0; 

    for (i = 0; i < n - 1; ++i) 
     for (j = 0; j < e; ++j) 
      if (d[edges[j].u] + edges[j].w < d[edges[j].v]){ 
       d[edges[j].v] = d[edges[j].u] + edges[j].w; 
       p[edges[j].v] = u; 
       } 

Tôi không chắc mình nên sửa đổi mã theo câu trả lời của bạn như thế nào; để đưa vào xem xét mức trung bình thay vì tổng chi phí nên điều này là đủ?

for (i = 0; i < n; ++i) 
     d[i] = INFINITY; 

    d[s] = 0; 

    for (i = 0; i < n - 1; ++i) 
     steps = 0; 
     for (j = 0; j < e; ++j) 
      if ((d[edges[j].u]+ edges[j].w)/(steps+1) < d[edges[j].v]/steps){ 
       d[edges[j].v] = d[edges[j].u] + edges[j].w; 
       p[edges[j].v] = u; 
       steps++; 
      } 

Nhưng dù sao tôi không biết cân nhắc giới hạn K cùng một lúc ... Cảm ơn bạn đã giúp bạn.

Sửa Kể từ khi tôi có thể đủ khả năng một số lỗi Tôi đang suy nghĩ về giải pháp Naif này:

• precompute tất cả các con đường ngắn nhất và ghi nhớ trong Một
• precompute tất cả các đường đi ngắn nhất trên đồ thị biến đổi , nơi tôi cắt các cạnh trên một trọng lượng nhất định và ghi nhớ chúng trong B

Khi tôi cần một con đường, tôi nhìn vào A, ví dụ: từ x đến y, đây là đường dẫn x-> z-> y sau đó cho mỗi bước tôi nhìn vào B, vì vậy đối với x> z Tôi thấy nếu có kết nối trong B, nếu không tôi giữ x> z nếu không Tôi điền vào đường dẫn x> z với đường phụ được cung cấp bởi B, có thể giống như x-> j-> h-> z; sau đó tôi làm tương tự cho z-> y. Mỗi lần tôi cũng sẽ kiểm tra xem tôi có thêm một đường dẫn tuần hoàn hay không.

Có lẽ tôi sẽ nhận được một số đường dẫn kỳ lạ nhưng nó có thể hoạt động trong hầu hết các trường hợp. Nếu tôi mở rộng giải pháp đang thử với các "ngưỡng cắt" khác nhau, có lẽ tôi cũng có thể gần với sự tôn trọng giới hạn K.

Answer 1

Bạn có thể sửa đổi một chút thuật toán Bellman-Ford để tìm đường dẫn tối thiểu bằng cách sử dụng tối đa K cạnh/nút. Nếu số cạnh được cố định hơn bạn phải giảm thiểu tổng chi phí, vì chi phí trung bình sẽ là TotalCost/NumberOfEdges.

Một trong các giải pháp sẽ là lặp lại NumberOfEdges từ 1 đến K, tìm tổng chi phí tối thiểu và chọn TotalCost/NumberOfEdges tối thiểu.

Answer 2

Tôi tin rằng bạn có thể giải quyết vấn đề này bằng cách sử dụng phiên bản sửa đổi của thuật toán Bellman-Ford.

Bellman-Ford dựa trên sự lặp lại chương trình động sau đây cố gắng tìm đường đi ngắn nhất từ ​​một số nút bắt đầu đến mỗi nút khác có chiều dài không lớn hơn m đối với một số m. Là một trường hợp cơ sở, khi bạn xem xét những con đường có độ dài bằng không, các nút có thể truy cập duy nhất là s và các giá trị ban đầu là

BF(s, t, 0) = infinity 
BF(s, s, 0) = 0 

Sau đó, nếu chúng ta biết các giá trị cho một con đường có chiều dài m, chúng ta có thể tìm thấy nó cho con đường có chiều dài m + 1 bằng cách ghi nhận rằng con đường cũ vẫn có thể có giá trị, hoặc chúng tôi muốn mở rộng một số con đường bằng chiều dài một:

BF(s, t, m + 1) = min { 
        BF(s, t, m), 
        BF(s, u, m) + d(u, t) for any node u connected to t 
        } 

thuật toán như một toàn thể hoạt động bằng cách lưu ý rằng bất kỳ con đường ngắn nhất phải có chiều dài không lớn hơn n và sau đó sử dụng lập trình động và lặp lại ở trên để tính toán giá trị của BF (s, t, n) cho tất cả t. Thời gian chạy tổng thể của nó là O (EV), vì có các cạnh E để xem xét ở mỗi bước và tổng V đỉnh.

Hãy xem cách chúng tôi có thể thay đổi thuật toán này để giải quyết vấn đề của bạn. Đầu tiên, để giới hạn điều này với các đường dẫn có độ dài k, chúng ta có thể cắt đứt vòng lặp Bellman-Ford sau khi tìm tất cả các đường đi ngắn nhất có độ dài đến k. Để tìm ra con đường với chi phí trung bình thấp nhất là một chút phức tạp hơn. Tại mỗi điểm, chúng tôi sẽ theo dõi hai đại lượng - chiều dài của đường đi ngắn nhất đạt đến nút t và chiều dài trung bình của đường dẫn đó. Khi xem xét các đường dẫn mới có thể tiếp cận t, các tùy chọn của chúng tôi là giữ đường dẫn trước đó mà chúng tôi đã tìm thấy (có chi phí bằng đường đi ngắn nhất cho đến nay chia cho số lượng nút trong đó) hoặc mở rộng một số đường khác bằng một bước. Chi phí mới của đường dẫn đó sau đó được đưa ra bởi tổng chi phí từ trước cộng với độ dài cạnh chia cho số cạnh trong đường cũ cộng một. Nếu chúng ta lấy giá rẻ nhất và sau đó ghi lại cả chi phí và số cạnh của nó, cuối cùng chúng ta sẽ tính toán đường có chi phí trung bình thấp nhất không lớn hơn k trong thời gian O (kE). Khi khởi tạo, chúng ta sẽ nói rằng đường dẫn từ nút bắt đầu đến chính nó có độ dài 0 và chi phí trung bình 0 (chi phí trung bình không quan trọng, vì bất cứ khi nào chúng ta nhân nó với số cạnh chúng ta nhận được 0). Chúng tôi cũng sẽ nói rằng mỗi nút khác ở khoảng cách vô cùng bằng cách nói rằng chi phí trung bình của một cạnh là vô cùng và số cạnh là một. Bằng cách đó, nếu chúng ta thử tính toán chi phí của một con đường hình thành bằng cách mở rộng con đường, nó sẽ xuất hiện để có chi phí trung bình vô cùng và sẽ không được chọn.

Về mặt toán học, giải pháp trông như thế này. Tại mỗi điểm chúng tôi lưu trữ chi phí cạnh trung bình và tổng số của các cạnh tại mỗi nút:

BF(s, t, 0).edges = 1 
BF(s, t, 0).cost = infinity 

BF(s, s, 0).edges = 0 
BF(s, s, 0).cost = 0 

BF(s, t, m + 1).cost = min { 
    BF(s, t, m).cost, 
    (BF(s, u, m).cost * BF(s, u, m).edges + d(u, t))/(BF(s, u, m).edges + 1) 
} 

BF(s, t, m + 1).edges = { 
    BF(s, t, m).edges   if you chose the first option above. 
    BF(s, u, m).edges + 1  else, where u is as above 
} 

Lưu ý rằng điều này có thể không tìm thấy một con đường đơn giản có độ dài k, vì giảm thiểu chi phí trung bình có thể yêu cầu bạn phải tham gia một chu kỳ với chi phí thấp (dương hoặc âm) nhiều lần để giảm tốc độ trung bình. Ví dụ: nếu biểu đồ có vòng lặp chi phí bằng 0, bạn chỉ nên tiếp tục sử dụng nó nhiều lần nhất có thể.

EDIT: Để trả lời câu hỏi mới của bạn, cách tiếp cận này sẽ không hoạt động nếu bạn không muốn sao chép các nút trên đường dẫn. Như @comestibles đã chỉ ra, phiên bản này của vấn đề là NP-cứng, do đó, trừ khi P = NP bạn không nên mong đợi để tìm bất kỳ thuật toán đa thức thời gian tốt cho vấn đề này.

Đối với thời gian chạy, thuật toán tôi đã mô tả ở trên chạy trong tổng thời gian O (kE). Điều này là bởi vì mỗi lần lặp của tính toán lặp lại có thời gian O (E) và có tổng số k lặp.

Cuối cùng, hãy xem mã được đề xuất của bạn. Tôi đã in lại ở đây:

for (i = 0; i < n - 1; ++i) { 
    steps = 0; 
    for (j = 0; j < e; ++j) { 
     if ((d[edges[j].u]+ edges[j].w)/(steps+1) < d[edges[j].v]/steps){ 
      d[edges[j].v] = d[edges[j].u] + edges[j].w; 
      p[edges[j].v] = u; 
      steps++; 
     } 
    } 
} 

Câu hỏi đầu tiên của bạn là cách tính đến k. Điều này có thể được thực hiện dễ dàng bằng cách viết lại các vòng ngoài để đếm lên đến k, không n - 1. Cung cấp cho chúng tôi mã này:

for (i = 0; i < k; ++i) { 
    steps = 0; 
    for (j = 0; j < e; ++j) { 
     if ((d[edges[j].u]+ edges[j].w)/(steps+1) < d[edges[j].v]/steps){ 
      d[edges[j].v] = d[edges[j].u] + edges[j].w; 
      p[edges[j].v] = u; 
      steps++; 
     } 
    } 
} 

Một vấn đề mà tôi nhận thấy là các sửa đổi Bellman-Ford nhu cầu thuật toán để có từng đường dẫn ứng cử viên tốt nhất lưu trữ số cạnh của nó một cách độc lập, vì đường dẫn tối ưu của mỗi nút có thể đạt được bằng một số cạnh khác nhau. Để khắc phục điều này, tôi khuyên bạn nên lưu trữ một số giá trị là d mảng - số cạnh cần thiết để tiếp cận nút và chi phí trung bình của một nút dọc theo đường dẫn đó. Sau đó, bạn sẽ cập nhật mã của mình bằng cách thay thế biến số steps trong các phương trình này với độ dài đường dẫn được lưu trong bộ nhớ cache.

Hy vọng điều này sẽ hữu ích!

Answer 3

Đối với phiên bản mới của sự cố, có sự giảm xuống từ đường Hamilton (khiến cho sự cố của bạn trở nên khó hiểu). Lấy một thể hiện của đường dẫn Hamilton (tức là, một đồ thị có các cạnh được giả định là có trọng lượng đơn vị), thêm nguồn và đỉnh chìm và các cạnh của trọng số 2 từ nguồn này sang tất cả các giá trị khác và từ bồn rửa chén đến tất cả các thứ khác. Đặt K = | V | + 2 và yêu cầu đường dẫn từ nguồn đến bồn rửa. Có tồn tại một đường dẫn Hamilton nếu và chỉ khi chiều dài cạnh trung bình tối ưu là (| V | + 3)/(| V | + 2).

Hãy cẩn thận để cho chúng tôi biết lý do bạn muốn các đường dẫn này để chúng tôi có thể tư vấn cho bạn về một chiến lược gần đúng hợp lý?