Lập trình: Thuật toán tìm chu trình có trọng số nhỏ nhất?

English | Vietnamese

Rules

Main Forum

Portal

Member Listing

Statistics

Search

Reading Room
[Register]

Login [ | https ]

Forum Index

Thảo luận hệ điều hành Windows

Lập trình: Thuật toán tìm chu trình có trọng số nhỏ nhất?

[Programming] Lập trình: Thuật toán tìm chu trình có trọng số nhỏ nhất?	15/12/2009 09:53:25 (+0700) \| #1 \| 200721

longkt90
Member

Joined: 27/08/2009 20:44:22
Messages: 61
Offline

Bài này em mấy tuần rồi không ra, nếu làm theo cặp ghép cực đại có trọng số cực tiểu thì sai (vd trong TH đồ thị có chu trình chỉ có 2 đỉnh). Còn nếu dùng DFS hay BFS thì chắc chắn là stack over flow (max = 100 đỉnh).
Cuối tuần này em phải hoàn thành nên đành đi hỏi vậy. smilie

Đơn đồ thị có hướng G, trọng số nguyên dương, được cho bởi ma trận kề, trong đó nếu cung (i, j) không tồn tại thì trọng số của cung sẽ ký hiệu bằng 0.
Yêu cầu tìm trong đồ thị một số chu trình sao cho mỗi đỉnh của đồ thị thuộc đúng một chu trình và tổng trọng số của tất cả các chu trình là nhỏ nhất.

Lưu ý: Mỗi chu trình phải có ít nhất 2 đỉnh.

Input: Dòng đầu tiên ghi số n là số đỉnh của đồ thị. (n < 100).Tiếp theo là ma trận n*n, trong đó số ở dòng i và cột j chỉ trọng số D của cung đi từ i đến j. Dij < 20000.

5
0 18 14 16 17
16 0 9 4 20
16 12 0 12 8
16 6 16 0 9
10 16 15 4 0

Outout: Dòng đầu ghi số S là tổng trọng số của các chu trình. Dòng thứ hai ghi số k là số lượng chu trình tìm được. Trong k dòng tiếp theo, mỗi dòng ghi ra một chu trình tìm được, trong đó đỉnh kết thúc của chu trình cũng chính là đỉnh xuất phát của chu trình đó.

42
2
1 3 5 1
2 4 2

ps: Ông thầy em có nói là dùng luồng trong mạng chắc chắn ra, nhưng em yếu phần này, mày mò miết mà không thấy áp dụng được chút nào về luồng.

[Programming] Lập trình: Thuật toán tìm chu trình có trọng số nhỏ nhất?	16/12/2009 06:58:09 (+0700) \| #2 \| 200852

longkt90
Member

Joined: 27/08/2009 20:44:22
Messages: 61
Offline

Trời, ko có bác nào đưa ra dùm em một ý tưởng à?
Bài này nộp lấy điểm TH cuối kì, chắc em bỏ. hic. ko có ý tưởng nào hết.

[Programming] Lập trình: Thuật toán tìm chu trình có trọng số nhỏ nhất?	16/12/2009 07:20:16 (+0700) \| #3 \| 200853

lamer
Elite Member

Joined: 26/02/2008 13:28:49
Messages: 215
Offline

Mình đọc đề 3 lần rồi mà vẫn chưa hiểu mục đích là làm cái gì.

Tìm chu trình có trọng số nhỏ nhất, hay tìm tất cả chu trình trong đồ thị.

Ví dụ như nếu có hai chu trình xuất phát từ đỉnh 2 kết thúc tại đỉnh 2 và có trọng số là 5, và 8. Thì sẽ xuất ra chu trình có trọng số 5, 8 hay cả hai chu trình đó?

[Programming] Lập trình: Thuật toán tìm chu trình có trọng số nhỏ nhất?	16/12/2009 08:21:30 (+0700) \| #4 \| 200857

toidihoc
Member

Joined: 14/12/2009 00:59:54
Messages: 12
Offline

longkt90 wrote:

Đơn đồ thị có hướng G, trọng số nguyên dương, được cho bởi ma trận kề, trong đó nếu cung (i, j) không tồn tại thì trọng số của cung sẽ ký hiệu bằng 0.
Yêu cầu tìm trong đồ thị một số chu trình sao cho mỗi đỉnh của đồ thị thuộc đúng một chu trình và tổng trọng số của tất cả các chu trình là nhỏ nhất.

Lưu ý: Mỗi chu trình phải có ít nhất 2 đỉnh.

Đây là câu hỏi rồi đúng không longkt90, chà lâu rồi không đụng nên giờ cũng quên đi nhiều rồi. Bạn nào còn nhớ hoặc mới học thì may ra, đây là lý thuyết đồ thị của hồi học đại học thì phải smilie

MLIML

[Programming] Lập trình: Thuật toán tìm chu trình có trọng số nhỏ nhất?	16/12/2009 09:48:27 (+0700) \| #5 \| 200881

longkt90
Member

Joined: 27/08/2009 20:44:22
Messages: 61
Offline

[đã sửa]

[Programming] Lập trình: Thuật toán tìm chu trình có trọng số nhỏ nhất?	16/12/2009 09:50:26 (+0700) \| #6 \| 200882

longkt90
Member

Joined: 27/08/2009 20:44:22
Messages: 61
Offline

lamer wrote:

Mình đọc đề 3 lần rồi mà vẫn chưa hiểu mục đích là làm cái gì.

Tìm chu trình có trọng số nhỏ nhất, hay tìm tất cả chu trình trong đồ thị.

Ví dụ như nếu có hai chu trình xuất phát từ đỉnh 2 kết thúc tại đỉnh 2 và có trọng số là 5, và 8. Thì sẽ xuất ra chu trình có trọng số 5, 8 hay cả hai chu trình đó?

Dạ tìm 1 số chu trình (ít nhất 1 cái) sao cho tất cả các đỉnh của đồ thị đều được chọn duy nhất một lần và tổng trọng số của các chu trình này nhỏ nhất. Còn trường hợp anh đưa ra thì còn tùy ạ. Nếu chu trình xuất phát từ đỉnh 2 cộng với 1 số chu trình nữa sao cho mỗi đỉnh thuộc duy nhất 1 chu trình thì và tổng trọng số nhỏ nhất chọn chu trình đó. Nếu 2 chu trình anh đưa ra đều thỏa mãn thì chọn cái có tróng số nhỏ hơn vì có thêm yêu cầu tổng trọng số nhỏ nhất.

toidihoc wrote:

Đây là câu hỏi rồi đúng không longkt90, chà lâu rồi không đụng nên giờ cũng quên đi nhiều rồi. Bạn nào còn nhớ hoặc mới học thì may ra, đây là lý thuyết đồ thị của hồi học đại học thì phải.

Chính xác là bài tập môn lí thuyết đồ thị đó anh. Em mới học năm 2. Về đồ thị mới được học prim, kruskal, floy, bellman - ford, dijkstra, định lí 4 màu. Chương luồng trong mạng ông thầy kêu tự đọc.

ps: mấy a quan tâm thế này em cám ơn lắm lắm

[Programming] Lập trình: Thuật toán tìm chu trình có trọng số nhỏ nhất?	16/12/2009 09:51:55 (+0700) \| #7 \| 200883

longkt90
Member

Joined: 27/08/2009 20:44:22
Messages: 61
Offline

trời, net bị khùng, sao thành 2 bản rồi. xin lỗi vì đã spam

[Programming] Lập trình: Thuật toán tìm chu trình có trọng số nhỏ nhất?	16/12/2009 17:33:25 (+0700) \| #8 \| 200934

_sharp_
Member

Joined: 24/05/2009 19:24:50
Messages: 33
Location: Onepiece
Offline

longkt90 wrote:

Yêu cầu tìm trong đồ thị một số chu trình sao cho mỗi đỉnh của đồ thị thuộc đúng một chu trình và tổng trọng số của tất cả các chu trình là nhỏ nhất.

Lưu ý: Mỗi chu trình phải có ít nhất 2 đỉnh.
[/i][/color]

Outout: Dòng đầu ghi số S là tổng trọng số của các chu trình. Dòng thứ hai ghi số k là số lượng chu trình tìm được. Trong k dòng tiếp theo, mỗi dòng ghi ra một chu trình tìm được, trong đó đỉnh kết thúc của chu trình cũng chính là đỉnh xuất phát của chu trình đó.

kô hiểu sao yêu cầu là tìm " một số " mà output lại là " số lượng chu trình tìm dc ".
nếu mình hiểu " số lượng chu trình tìm dc " = tất cả các chu trình tìm dc thì bài toán chia thành 2 bài toán con :
1. liệt kê tất cả cây khung của đồ thị.
2. dùng thuật toán dijkstra với từng cây khung, với input là từng đỉnh của cây khung, đỉnh xuất phát là đỉnh kết thúc.

[Programming] Lập trình: Thuật toán tìm chu trình có trọng số nhỏ nhất?	16/12/2009 18:04:02 (+0700) \| #9 \| 200937

longkt90
Member

Joined: 27/08/2009 20:44:22
Messages: 61
Offline

_sharp_ wrote:

kô hiểu sao yêu cầu là tìm " một số " mà output lại là " số lượng chu trình tìm dc ".

Tìm một số chu trình thỏa mãn điều kiện có tổng trọng số nhỏ nhất và chứa tất cả các đỉnh (mỗi đỉnh chỉ thuộc về một chu trình).

Ví dụ như trong đồ thị có tất cả 5 đỉnh 1, 2, 3,4,5 bạn tìm được 2 bộ chu trình thỏa đk như sau:

bộ có một chu trình: 1 -> 2 -> 3 -> 4-> 5 có tổng trọng số 20.

và bộ có 2 chu trình 1 -> 2 -> 1 tổng trọng số chu trình này là 5
3 -> 4 -> 5 -> 3 trọng số 14
=> tổng trọng số sẽ là 19.

vì 19 < 20 nên bạn sẽ in ra như sau

19 (tổng trọng số tìm đc)
2 (bộ này có 2 chu trình) sau đó bạn liệt kê các chu trình của bộ này ra
1 -> 2 -> 1
3 -> 4 -> 5 -> 3

_sharp_ wrote:

nếu mình hiểu " số lượng chu trình tìm dc " = tất cả các chu trình tìm dc thì bài toán chia thành 2 bài toán con :
1. liệt kê tất cả cây khung của đồ thị.
2. dùng thuật toán dijkstra với từng cây khung, với input là từng đỉnh của cây khung, đỉnh xuất phát là đỉnh kết thúc.

Như vậy cách làm của bạn sai rồi. Nếu nói trên lí thuyết thì có thể làm như sau:
1. Liệt kê tất cả chu trình.
2. Chọn ra M bộ có Mi chu trình thuộc tập trên, tổng trọng số Si sao cho thỏa đk tất cả các đỉnh thuộc một chu trình.
3. Tìm min trong các Si ở bước 2, in ra Si min, và Mi chu trình tương ứng.

Nhưng cách này có thể chạy trên khoảng 10 đỉnh còn 100 đỉnh thì :d

[Programming] Lập trình: Thuật toán tìm chu trình có trọng số nhỏ nhất?	16/12/2009 19:25:29 (+0700) \| #10 \| 200944

_sharp_
Member

Joined: 24/05/2009 19:24:50
Messages: 33
Location: Onepiece
Offline

longkt90 wrote:

Như vậy cách làm của bạn sai rồi. Nếu nói trên lí thuyết thì có thể làm như sau:
1. Liệt kê tất cả chu trình.
2. Chọn ra M bộ có Mi chu trình thuộc tập trên, tổng trọng số Si sao cho thỏa đk tất cả các đỉnh thuộc một chu trình.
3. Tìm min trong các Si ở bước 2, in ra Si min, và Mi chu trình tương ứng.

ừh. vậy theo mình thì bước 1 + 2 nên gộp làm 1 bước đó là dùng dijkstra.
ví dụ đồ thị có 5 đỉnh 1,2,3,4,5 : dùng 5 lần thuật toán dijktra với :
- đỉnh xuất phát và đỉnh kết thúc là 1
-..................................................2
-....
-..................................................5

như vậy vừa thỏa mãn yêu cầu đỉnh xuất phát là đỉnh kết thúc và có trọng số nhỏ nhất (theo ví dụ trên có 5 trọng số)
từ 5 trọng số đấy chỉ cần tìm ra cặp có tổng trọng số nhỏ nhất là xong.

[Programming] Lập trình: Thuật toán tìm chu trình có trọng số nhỏ nhất?	16/12/2009 19:52:06 (+0700) \| #11 \| 200946

longkt90
Member

Joined: 27/08/2009 20:44:22
Messages: 61
Offline

_sharp_ wrote:

ừh. vậy theo mình thì bước 1 + 2 nên gộp làm 1 bước đó là dùng dijkstra.
ví dụ đồ thị có 5 đỉnh 1,2,3,4,5 : dùng 5 lần thuật toán dijktra với :
- đỉnh xuất phát và đỉnh kết thúc là 1
-..................................................2
-....
-..................................................5

như vậy vừa thỏa mãn yêu cầu đỉnh xuất phát là đỉnh kết thúc và có trọng số nhỏ nhất (theo ví dụ trên có 5 trọng số)
từ 5 trọng số đấy chỉ cần tìm ra cặp có tổng trọng số nhỏ nhất là xong.

Mình không hiểu cách làm của bạn. Theo mình nếu làm như vậy thì khi bạn tìm xong n chu trình thì:

1> các đỉnh sẽ không thỏa mãn chỉ thuộc về 1 chu trình.

2> Mình không có nói sẽ chọn 1 cặp (= 2) mà phải chọn k cặp chưa biết trước.

[Programming] Lập trình: Thuật toán tìm chu trình có trọng số nhỏ nhất?	16/12/2009 20:22:07 (+0700) \| #12 \| 200951

_sharp_
Member

Joined: 24/05/2009 19:24:50
Messages: 33
Location: Onepiece
Offline

longkt90 wrote:

2> Mình không có nói sẽ chọn 1 cặp (= 2) mà phải chọn k cặp chưa biết trước.

cái này mình dùng từ sai. ý mình là có 5 trọng số đấy, tỉm ra 1 bộ có tổng các trọng số nhất. (bộ đấy có thể là 2 hoặc 3,...trọng số).

"mỗi đỉnh của đồ thị thuộc đúng một chu trình" + "Lưu ý: Mỗi chu trình phải có ít nhất 2 đỉnh. " vậy thì đúng là chỉ có liệt kê tất cả các chu trình ra :
ví dụ n = 5;
1->2 , 3->4->5 , chu trình 1 : 1->2->1 ; 3->4->5->3
1->3 , 2->4->5 , chu trình 2 : 1->3->1 ; 2->4->5->2
.....
.....

2. Chọn ra M bộ có Mi chu trình thuộc tập trên, tổng trọng số Si sao cho thỏa đk tất cả các đỉnh thuộc một chu trình.
3. Tìm min trong các Si ở bước 2, in ra Si min, và Mi chu trình tương ứng.

theo mình chọn ra ở đây kô đúng mà bạn fai tính hết tổng trọng số của chu trình 1,chu trình 2,...
rồi mới tìm ra tổng trọng số min.

bài toán này chắc chỉ khúc mắc ở bước liệt kê tất cả chu trình sao cho độ phức tạp nhỏ nhất là dc. mình chưa nghĩ ra dc cách liệt kê sao cho n = 100 T_T

[Programming] Lập trình: Thuật toán tìm chu trình có trọng số nhỏ nhất?	16/12/2009 20:46:06 (+0700) \| #13 \| 200957

longkt90
Member

Joined: 27/08/2009 20:44:22
Messages: 61
Offline

Chọn ra tức là dựa vào đk "tất cả các đỉnh thuộc một chu trình" rồi mình mới tính tổng trọng số, ý mình là dùng đk để loại bớt TH cần tính, nhưng thực ra trong khi tính tổng cũng có thể kết hợp với việc kiểm tra đk.

Mình mới coi qua thuật toán Hungari - tìm cặp ghép cực đại có trọng số cực tiểu, có thể giải được bài này 1 cách nhẹ nhàng (chưa cm đc tính đúng đắn, đang coi tiếp).

[Programming] Lập trình: Thuật toán tìm chu trình có trọng số nhỏ nhất?	17/12/2009 15:16:01 (+0700) \| #14 \| 201090

4hfoo
Elite Member

Joined: 29/01/2007 01:50:20
Messages: 115
Offline

Nếu chu trình có đỉnh bị lặp lại thì chu trình đó có hợp lệ không?
Ví dụ: 1->2->3->2->4->1
(2 bị lặp lại)

[Programming] Lập trình: Thuật toán tìm chu trình có trọng số nhỏ nhất?	17/12/2009 15:41:07 (+0700) \| #15 \| 201092

longkt90
Member

Joined: 27/08/2009 20:44:22
Messages: 61
Offline

Quên không nói, tụi em học có qui ước: nếu không nói gì thêm hiểu là chu trình sơ cấp

Tức là không đc lặp lại

[Programming] Lập trình: Thuật toán tìm chu trình có trọng số nhỏ nhất?	17/12/2009 16:09:05 (+0700) \| #16 \| 201094

_sharp_
Member

Joined: 24/05/2009 19:24:50
Messages: 33
Location: Onepiece
Offline

vậy thì ở bước liệt kê các chu trình lại fai thêm điều kiện T_T

[Programming] Lập trình: Thuật toán tìm chu trình có trọng số nhỏ nhất?	17/12/2009 17:27:48 (+0700) \| #17 \| 201099

4hfoo
Elite Member

Joined: 29/01/2007 01:50:20
Messages: 115
Offline

Theo mình thấy thì vấn đề cũng không đơn giản.
Kiếm hoài trên mạng mà vẫn chưa ra, chỉ thấy toàn cách tính ước lượng (approximation) smilie

, mà có nhiếu bài báo chỉ cho xem trang đầu, xem toàn bộ phải bỏ tiền mua ... smilie

Bạn có thể thử kiếm với từ khóa 'minimum vertex disjoint cycle cover', hoặc tương tự.
Khi nào mình kiếm ra được gì hay sẽ post lên ...

[Programming] Lập trình: Thuật toán tìm chu trình có trọng số nhỏ nhất?	17/12/2009 18:51:05 (+0700) \| #18 \| 201107

_sharp_
Member

Joined: 24/05/2009 19:24:50
Messages: 33
Location: Onepiece
Offline

bạn thử post wa bên http://vnoi.info/ hỏi thử xem

[Programming] Lập trình: Thuật toán tìm chu trình có trọng số nhỏ nhất?	18/12/2009 12:22:21 (+0700) \| #19 \| 201203

4hfoo
Elite Member

Joined: 29/01/2007 01:50:20
Messages: 115
Offline

Sau một hồi lang thang trên mạng thì mình có cách giải sau, bạn xem thử coi sao.

Bài giải chia làm 2 phần [A], [B]. Phần [B] là phần bài giải của bạn yêu cầu.
Phần [A] là bước chuyển tiếp đến phần [B]

[A] Trước tiên, mình trình bày cách kiếm các chu trình không có đỉnh nào trùng nhau,
và thỏa điều kiện các chu trình này sẽ chứa các điểm của đồ thị.

Tóm tắt các bước:
1/ Xây dựng graph mới từ graph cho sắn
2/ Gán trọng số cho các cạnh của graph mới
3/ Chạy thuật toán luồng trên graph mới
4/ Dựa vào kết quả phân luồng, xuất kết quả

Bước 1: Xây dựng graph mới G' từ graph cho sẵn
G
- Vẽ 2 cột điểm, bên trái 1->n, bên phải 1->n
- Với mỗi cạnh i->j trong graph G, nối điểm i (bên trái) tới điêm j bên phải (trong graph mới G')
- Tạo thêm 2 điểm nguồn (S) và đích (T) trong graph mới
- Nối S với điểm 1..n (bên trái)
- Nối các điểm 1..n (bên phải) đến T

Bước 2: Gán trọng số cho các cạnh của graph mới
- Gán các cạnh với giá trị chặn dưới là 0, giá trị chặn trên là 1. (0,1)

Bước 3: Chạy thuật toán luồng trên graph mới
- Chạy thuật toán tìm luồng cực đại trên graph G'

Bước 4:
- Sau khi chạy xong thuật toán luồng, nếu tổng ra từ đỉnh S = n -> tồn tại lời giải
Ngược lại, lời giải không tồn tại.
- Cách tìm lời giải:
Truy ngược lại luồng, nếu có luồng chảy từ i (bên trái) -> j (bên phải) -> ghi nhớ cạnh (i,j)
Sau cùng, từ danh sách các cạnh đã lưu -> suy ra các chu trình.
Ví dụ: các cạnh đã lưu: (3,5), (1,3), (5,1) => chu trình là 1->3->5->1

[B] Cải tiến phần [A], để kiếm các chu trình không có đỉnh nào trùng nhau,
và thỏa điều kiện các chu trình này sẽ chứa các điểm của đồ thị,
và tổng giá trị của các chu trình là bé nhất.

Lời giải phần này tương tự phần A, chỉ khác nhau ở bước 2 và bước 3.
Bước 2:
- Ngoài giá trị chặn trên, chặn dưới là [0,1], thêm trọng số cho cạnh đó,
bằng với trọng số của cạnh đó trong graph cũ G.

Bước 3:
- Thay vì chạy luồng cực đại như [A], chúng ta sẽ chạy thuật toán tìm luồng cực tiểu.
=> Tìm luồng cực tiểu thỏa mãn điều kiện tổng ra từ S bằng với n, và tổng trọng của luồng là nhỏ nhất.

===========

Phần chứng minh thì bạn thử suy nghĩ vậy smilie

Link tham khảo:
1/ Luồng cực đại:
[url]http://en.wikipedia.org/wiki/Maximum_flow
2/ Luồng cực tiểu:
http://en.wikipedia.org/wiki/Minimum_cost_flow_problem
3/ Disjoint vertex cycle cover for directed graph (3. The cycle cover problem)
www.cs.ncl.ac.uk/publications/trs/papers/131.pdf

Thân

[Programming] Lập trình: Thuật toán tìm chu trình có trọng số nhỏ nhất?	21/12/2009 16:32:36 (+0700) \| #20 \| 201513

longkt90
Member

Joined: 27/08/2009 20:44:22
Messages: 61
Offline

Thanks. Mấy ngày nay ko đụng đc máy tính, giờ mới đọc đc

Go to:

Users currently in here
1 Anonymous