PDA

View Full Version : [Q] Algorithm !!!



Savage
13-12-2002, 00:50
give the system of two-way roads.Determine if it is possible, after building three additional new roads, from the chosen city to reach each of the remaining cities, travelling distance not more than T units( unit = a road directly from one city to the other )

mình dùng bool adjacency matrix representation A ( a[i,j] = {0,1} )
nếu a[i,j]=1 thì có nghĩa là từ thành phố i tới thành phố j tồn tại một đừong đi trực tiếp- distance=1 unit - ( không quan tâm đến trọng số nhé ).
bây giờ ta bình phương A lên ( lưu ý đay là matrix bool ) , kếu quả nếu a(n)[i,j] = 1 thì suy ra tồn tại một đường đi có độ dài max = 2 unit từ i tới j ...( cái này chứng minh được ) , and so fourth ta làm tương tự đến khi có Matrix A mũ T thì suy ra nếu a(T)[i,j]=1 thì tồn tại ít nhất một đừong đi có độ dài T từ i tới j....
bây giờ tình matrix D = tổng của các A(n) trong đó n chạy từ 1 tới T - A(n) nghĩa là matrix mũ n của A
như vậy nếu bây giờ D[I,j] = 1 thì có nghĩa là sẽ tồn tại một đường đi có độ dài lớn nhất là T từ I tới j
-OK ! đó là lý thuyết nhé , còn bài này thì sao ???
bây giờ ta tính D của bài này , sau đó xem xét phần tử nào mà = 0 thì sẽ là cái ta quan tâm . ta sẽ phải làm thế nào để tất cả các số 0 này trở thành số 1 ???
đến đây thì lại là vấn đề của Algebra rồi , các đại ca thử suy nghĩ xem làm thế nào mà chỉ cần thêm 3 cái a[I,j] =1 ta nhận đựợc tất cả D bằng 1 hết… ( tất nhiên khẳ năng có thể là không có nghiệm nào , nhưng đây ta giả sử là có nghiệm ..) thì thuật toán tiếp theo thế nào nhỉ các đại ca Algebra ??

Có bác nào có thuật toán mà không dùng đến cái bool adjacency matrix thì post lên nhé !

ntrhieu
10-01-2003, 01:44
Chào bạn,
Tin này đăng lâu rồi, nhưng tớ thấy bài này cũng thú vị nên cũng nghĩ thử. Nhưng bài này, chẳng phải là các cạnh nối vào bao giờ cũng bắt đầu từ đỉnh xuất phát nối đến 1 đỉnh khác sao ?
Tớ chỉ đưa ra informal proof thôi, nhưng chuyển thành formal proof ko khó mấy:
Giả sử cạnh thêm vào là (i,j), gọi d[x] là đường đi ngắn nhất từ đỉnh xúat phát s đến x trên đồ thị ban đầu
Nếu d[i] >= d[j], thí tất cả đường đi qua cạnh (i,j) của 1 solution đều từ i-> j, ko phải từ j->i, vì nếu ko thì ko phải ngắn nhất. Vậy, nếu thay cạnh (i,j) bằng cạnh (s,j) thì lời giải sẽ tốt hơn.
d[i] <= d[j] thì tương tụ.

Vậy, mọi cạnh thêm vào đều nối với S.

Như thế, thuật toán đơn giản nhất, the các bước sau:
1. Dùng Floy-Marshall all-pair shortest paths.
2. với mội bộ 3 đỉnh (i,j,k), kiểm tra xem tập hợp tất cả những đỉnh đến được từ i, j, hoặc k với độ dài <= T-1 có chứa hết các đỉnh của đồ thị hay ko. Nếu được -> solution.
3. Nếu ko tìm được bộ (i,j,k) ở bước 2 -> no solution.
độ phức tạp O(n^4) có thể chưa được nhanh. Nếu bạn ý nào hay hơn thì cho tớ biết.
Cách đại số tuyến tính cũng chưa chắc đã tốt hơn

Savage
10-01-2003, 02:41
Bài viết được gửi bởi ntrhieu
Chào bạn,
Tin này đăng lâu rồi, nhưng tớ thấy bài này cũng thú vị nên cũng nghĩ thử. Nhưng bài này, chẳng phải là các cạnh nối vào bao giờ cũng bắt đầu từ đỉnh xuất phát nối đến 1 đỉnh khác sao ?
Tớ chỉ đưa ra informal proof thôi, nhưng chuyển thành formal proof ko khó mấy:
Giả sử cạnh thêm vào là (i,j), gọi d[x] là đường đi ngắn nhất từ đỉnh xúat phát s đến x trên đồ thị ban đầu
Nếu d[i] >= d[j], thí tất cả đường đi qua cạnh (i,j) của 1 solution đều từ i-> j, ko phải từ j->i, vì nếu ko thì ko phải ngắn nhất. Vậy, nếu thay cạnh (i,j) bằng cạnh (s,j) thì lời giải sẽ tốt hơn.
d[i] <= d[j] thì tương tụ.

Vậy, mọi cạnh thêm vào đều nối với S.

Như thế, thuật toán đơn giản nhất, the các bước sau:
1. Dùng Floy-Marshall all-pair shortest paths.
2. với mội bộ 3 đỉnh (i,j,k), kiểm tra xem tập hợp tất cả những đỉnh đến được từ i, j, hoặc k với độ dài <= T-1 có chứa hết các đỉnh của đồ thị hay ko. Nếu được -> solution.
3. Nếu ko tìm được bộ (i,j,k) ở bước 2 -> no solution.
độ phức tạp O(n^4) có thể chưa được nhanh. Nếu bạn ý nào hay hơn thì cho tớ biết.
Cách đại số tuyến tính cũng chưa chắc đã tốt hơn


ok , cám ơn bạn...bài này tớ đã giả rồi....và đúng như cách đó , dùng thuật toán Floyd , và thử lần lượt từng bộ 3 định một .... kết quả OK , nhưng mà chậm quá mức ----> cảm giác là không optimal lắm .