Em đang có một bài về đồ thị, e chưa nghĩ ra hướng giải, mọi người xem giúp e với ạ. E có n đỉnh (n \leq 17), mảng c[][] lưu khoảng cách giữa 2 đỉnh, c[i][j] là khoảng cách từ đỉnh i \to j. Tìm đường đi có khoảng cách ngắn nhất đi từ đỉnh 1 đến tất cả các đỉnh còn lại rồi về lại đỉnh 1 (có thể đi lại các đỉnh đã từng đi qua). Chạy trong khoảng 1-2s ạ. E xin ý tưởng ạ. Cám ơn mọi người nhiều.
Đồ thị - Tìm đường đi ngắn nhất
Confucius said
If you explain it to me, I will forget later
If you show it to me, I will remember later
If you let me do it, I will understand forever
So I won’t write the code for you, but will give you some suggestions on how to do it yourself:
1 Like
Đề bài có phải yêu cầu tìm ra một chu trình (nếu tồn tại) thoả mãn hai điều kiện:
- Chu trình đi qua tất cả các đỉnh của đồ thị, trong đó một đỉnh có thể được lặp lại nhiều lần.
- Tổng các cạnh trong một chu trình, xuất phát từ đỉnh 1 và kết thúc tại đỉnh 1, đạt giá trị nhỏ nhất.
Không biết mình ghi vậy có phù hợp với yêu cầu đề bài hay không?
2 Likes
hoang đường cạnh trọng số âm mà cho phép đi lại các đỉnh thì ví dụ 1-2 có trọng số âm đi qua đi lại 1 \to 2 \to 1 \to 2 \to \cdots \to 1 \to 2 tới vô cực à 
1 Like
dạ đúng rùi ạ, chu trình cũng bắt đầu từ đỉnh 1 luôn ạ, vì sau cũng về lại đỉnh 1 ạ
huhu e nhầm, tại bài cho điểm âm nên e ghi thế mà e quên mất, e rút gọn bài toán sau khi làm 1 số đoạn rùi ạ. c >= 0 ạ, còn các dữ liệu kia vẫn vậy ạ hjc
thank you, i will try and if i have a problem, could i ask you some question ?
1 Like
vậy thì làm theo cách này, bước 1 chuyển về bài toán TSP bình thường bằng cách tìm đường đi ngắn nhất của các cặp đỉnh A \to B rồi bước 2 xài quy hoạch động mà giải bài TSP đó. Đề cho n=17 thì vừa đúng \text{O}(n^2 2^n)
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?