Tính số đường đi qua biểu đồ

Question

Tôi đang tìm số lượng đường dẫn chiều dài độc đáo x thông qua biểu đồ bắt đầu từ một nút cụ thể.

Tuy nhiên tôi có một hạn chế rằng không có nút nào được truy cập nhiều lần trên bất kỳ đường dẫn nào.

---

Ví dụ lấy đồ thị dưới đây:

Nếu tôi sau khi số 3 đường dài bắt đầu từ 5.

Câu trả lời sẽ được 9.

5 -> 2 -> 1 -> 3 
5 -> 2 -> 4 -> 3 
5 -> 2 -> 4 -> 7 
5 -> 4 -> 2 -> 1 
5 -> 4 -> 3 -> 1 
5 -> 4 -> 7 -> 6 
5 -> 6 -> 7 -> 4 
5 -> 7 -> 4 -> 2 
5 -> 7 -> 4 -> 3 

Lưu ý Tôi chỉ được phối hợp với câu trả lời (9) không phải là đường dẫn cụ thể.

---

Tôi đã cố gắng sử dụng một adjacency matrix với sức mạnh của x để cung cấp cho số lượng đường dẫn, nhưng tôi không thể làm việc ra làm thế nào để giải thích cho sự hạn chế nút độc đáo.

Tôi cũng đã thử sử dụng số depth-first search nhưng số lượng nút và kích thước của x làm cho điều này không khả thi.

---

EDIT: Confused DFS with BFS (Cảm ơn bạn Nụ cười Nylon & Nikita Rybak).

Answer 1

Đây là NP-Hard.

Giảm từ đường dẫn Hamilton.

Cho một đồ thị có Hamiltonian Đường dẫn tồn tại chúng ta cần phải kiểm tra ...

Chạy thuật toán của bạn cho mỗi đỉnh, với chiều dài con đường n-1. Bất kỳ sự trở lại khác không tương ứng với đường Hamilton và ngược lại. Vì vậy, về cơ bản, nếu bạn tìm thấy một thuật toán thời gian đa thức để giải quyết vấn đề của bạn, sau đó bạn có một thuật toán thời gian đa thức để giải quyết vấn đề Hamilton Path, có hiệu quả chứng minh P = NP!

Lưu ý: Điều này giả sử x là đầu vào.

Nếu bạn x cố định (tức là số lượng đỉnh trong biểu đồ), thì bạn có các thuật toán thời gian O (n^x), nằm trong P, nhưng vẫn không thực tế với kích thước trung bình x.

Answer 2

Vấn đề này là vấn đề đếm trong #P (số giải pháp) thay vì vấn đề quyết định trong NP (có hoặc không).

Moron's reduction vẫn hoạt động để chứng minh sự cố là #P-Complete vì Đường dẫn Hamilton cũng # P-complete.