graph - Làm thế nào để tìm được chu trình tối thiểu được chỉ định (tổng trọng lượng tối thiểu)?

Question

Dưới đây là một khoản thuế tiêu thụ đặc biệt:

Cho G là biểu đồ có trọng số theo hướng với n đỉnh và cạnh m, trong đó tất cả các cạnh đều có trọng số dương. Chu trình chỉ đạo là một đường dẫn được hướng dẫn bắt đầu và kết thúc tại cùng một đỉnh và chứa ít nhất một cạnh. Đưa ra thuật toán O (n^3) để tìm chu trình theo hướng G trong tổng trọng lượng tối thiểu. Tín dụng một phần sẽ được đưa ra cho một thuật toán O ((n^2) * m).

---

Đây là thuật toán của tôi.

Tôi thực hiện DFS. Mỗi khi tôi tìm thấy một back edge, tôi biết tôi đã có một chu kỳ chỉ đạo.

Sau đó, tôi sẽ tạm thời lùi lại dọc theo parent array (cho đến khi tôi di chuyển qua tất cả các đỉnh trong chu kỳ) và tính total weights.

Sau đó, tôi so sánh số total weight của chu kỳ này với min. min luôn có tổng trọng số tối thiểu. Sau khi DFS kết thúc, chu trình đạo trình tối thiểu của chúng tôi cũng được tìm thấy.

---

Ok, sau đó về độ phức tạp của thời gian.

Thành thật mà nói, tôi không biết độ phức tạp của thuật toán của mình.

Đối với DFS, traversal lấy O (m + n) (nếu m là số cạnh và n là số đỉnh). Đối với mỗi đỉnh, nó có thể trỏ trở lại một trong những tổ tiên của nó và do đó tạo thành một chu kỳ. Khi một chu trình được tìm thấy, phải mất O (n) để tóm tắt tổng trọng số.

Vì vậy, tôi nghĩ tổng thời gian là O (m + n * n). Nhưng rõ ràng nó là sai, như đã nêu trong excise thời gian tối ưu là O (n^3) và thời gian bình thường là O (m * n^2).

---

bất cứ ai có thể giúp tôi với:

1. là thuật toán của tôi có đúng không?
2. Độ phức tạp về thời gian nếu thuật toán của tôi là chính xác?
3. Có bất kỳ thuật toán nào tốt hơn cho vấn đề này không?

Answer 1

Bạn có thể sử dụng thuật toán Floyd-Warshall đây.

Các thuật toán Floyd-Warshall tìm thấy con đường ngắn nhất giữa tất cả các cặp của các đỉnh.

Thuật toán là sau đó rất đơn giản, hãy đi qua tất cả các cặp (u,v) và tìm cặp giảm thiểu dist(u,v)+dist(v,u), vì cặp này biểu thị trên một chu kỳ từ u đến u với trọng lượng dist(u,v)+dist(v,u). Nếu biểu đồ cũng cho phép các vòng lặp tự (một cạnh (u,u)), bạn cũng sẽ cần phải kiểm tra chúng một mình, vì các chu kỳ đó (và chỉ chúng) không được kiểm tra bởi thuật toán.

mã giả:

run Floyd Warshall on the graph 
min <- infinity 
vertex <- None 
for each pair of vertices u,v 
    if (dist(u,v) + dist(v,u) < min): 
      min <- dist(u,v) + dist(v,u) 
      pair <- (u,v) 
return path(u,v) + path(v,u) 

path(u,v) + path(v,u) thực sự là con đường tìm thấy từ u đến v và sau đó từ v đến u, mà là một chu kỳ.

Thời gian chạy thuật toán là O(n^3), vì floyd-warshall là cổ chai, vì vòng lặp mất O(n^2) thời gian.

Tôi nghĩ rằng tính chính xác ở đây là tầm thường, nhưng hãy cho tôi biết nếu bạn không đồng ý với tôi và tôi sẽ cố gắng giải thích nó tốt hơn.

Answer 2

"Đối với mỗi đỉnh, nó có thể chỉ trở lại một trong những tổ tiên của nó và do đó tạo thành một chu kỳ"

Tôi nghĩ rằng nó có thể chỉ trở lại bất kỳ của tổ tiên của nó có nghĩa là N

Ngoài ra, làm thế nào u sẽ đánh dấu đỉnh khi bạn ra khỏi dfs của nó, bạn có thể đến đó một lần nữa từ đỉnh khác và nó sẽ là một chu kỳ. Vì vậy, đây không phải là (n + m) dfs nữa.

1. Vì vậy ur algo là không đầy đủ
2. tương tự ở đây

3. Trong một dfs, tôi nghĩ rằng đỉnh nên hoặc là vô hình, hoặc kiểm tra, và cho kiểm tra u có thể lưu trữ trọng lượng tối thiểu cho đường dẫn đến đỉnh bắt đầu. Vì vậy, nếu trên một số giai đoạn khác u tìm thấy một cạnh đến đỉnh đó u không phải tìm kiếm con đường này nữa. Dfs này sẽ tìm chu trình đạo trình tối thiểu chứa đỉnh đầu tiên. và đó là O (n^2) (O (n + m) nếu u lưu trữ biểu đồ dưới dạng danh sách)

Vì vậy, nếu làm nó từ bất kỳ đỉnh nào khác sẽ là O (n^3) (O (n *) (n + m))

xin lỗi, cho tiếng anh của tôi và tôi không giỏi ngữ

Answer 3

Thuật toán của tôi có đúng không?

Không. Để tôi đưa ra ví dụ về số lượt truy cập. Hãy tưởng tượng bạn bắt đầu DFS từ u, có hai con đường p1 và p2u-v và 1 con đường p3 từ v trở lại u, p1 ngắn hơn p2.

Giả sử bạn bắt đầu bằng cách lấy đường dẫn p2 đến v và quay lại u theo đường dẫn p3. Một chu kỳ tìm thấy nhưng dường như nó không phải là tối thiểu. Sau đó, bạn tiếp tục khám phá u bằng cách lấy đường dẫn p1, nhưng kể từ khi v được khám phá đầy đủ, DFS kết thúc mà không tìm chu kỳ tối thiểu.