|
|
||
|
Ðiều Chỉnh | Xếp Bài |
#1
|
||||
|
||||
Hướng dẫn em bài tập cấu trúc dữ liệu và giải thuật ni cấy !!!
viết chương trình minh họa mô tả giải thuật và các giải thích khác
1. đường đi ngắn nhất trong đồ thị không trọng số được cho bởi ma trận kề. Chương trình minh họa |
#2
|
||||
|
||||
Cái này sử dụng thuật toán gì em, tìm kiếm theo chiều rộng hay sâu... có tới mấy thuật toán lận đó.
|
#3
|
||||
|
||||
nếu tim kiém thi bọn e chỉ được học tìm kiếm tuyến tính và tim kiếm nhị phân .thầy ko giới hạn sử dụng thuật toán .mà em cụng chưa biết sử dụng cây chi
em vẫn chưa tím được mối liên hệ giữa ma trận kề và đồ thị ko trọng số . [ Tự động gộp bài ] bây giờ làm răng mà viết chương trình để chạy được!!!!anh hay viết trên turbo c hay vsc++ thay đổi nội dung bởi: nguyen_mai193, 11-06-2009 lúc 10:30 AM. Lý do: Gộp bài viết gần nhau |
#4
|
|||
|
|||
ai đó bít thì giúp bạn ni cấy tề!
cứ im im rứa là ko đc |
#5
|
||||
|
||||
Nếu em đọc tài liệu thì em sẽ hiểu ma trận kề biểu diễn như thế nào thôi.
Chẳng hạn có mt A(n*n) thì A[i][j]=1 khi giữa v[i] và v[j] có đường nối với nhau ( Trong đó v[] là ma trận đỉnh ) và A[i][j]=0 khi không có đường nối giữa chúng Để tìm đường đi ngắn nhất với đồ thị vô hướng thì bạn sử dụng thuật toán Dijkstra Nếu bạn đã rõ thuật toán thì dùng ngôn ngữ gì cũng được, nếu biết C# thì dùng C# sẽ nhanh, tiện hơn nhiều so với BORLANDC http://spktit.net/showthread.php?t=828 Đây là toàn bộ đồ án lớp mình làm năm nhất (viết bằng BORLANDC ) Chuyển đổi giữa các cách biểu diễn đồ thị http://www.mediafire.com/?smn1tlgwj2h Chương trình biểu diễn các đồ thị đơn giản: http://www.mediafire.com/?euyjmmgd9w1 Chu trình Hamilton: http://www.mediafire.com/?mmijjmm2vwm Duyệt đồ thị theo chiều rộng http://www.mediafire.com/?dojlbiwgjl1 Mô phỏng duyệt đồ thị theo DFS http://www.mediafire.com/?ejhjhono4ey Đồ thị liên thông: http://www.mediafire.com/?n1f70iuy4kj Mô phỏng chu trình Euler http://www.mediafire.com/?adn1omzv94n Xử lý ma trận kề từ file http://www.mediafire.com/?jfnm4311jwn Mô phỏng thuật toán Prim http://www.mediafire.com/?htnjxxkbnot DIJKSTRA http://www.mediafire.com/?9z3nnjnfxzs hoặc: http://www.mediafire.com/?qysh9mzlgsz (cái này bro hơn ) Đồ thị có trọng số : http://www.mediafire.com/?fmcokdlsml4 |
#6
|
||||
|
||||
.mấy cái này phức tạp hơn bọn em học .bài tập của em lại phải viết chương trình ...... nói chung là giờ em ko biết viết như răng . khi bắt đầu viết chương trình thì mô tả ma trận trước rồi tìm đường đi ngắn nhất ạ . anh có chương trình mô viết ma trận mà đơn giản hơn một tì đc ko.ma trận thì em hiều nhưng ko biết liên kết giữa ma trận và cách tìm đường ngắn nhất
|
#7
|
||||
|
||||
Ở trên đó em, cái đồ án DIJKSTRA đó. Còn việc liên kết giữa ma trận và cách tìm đường ngắn nhất thì em phải đọc thuật toán mới hiểu được.
Còn ma trận, như anh đã nói ở trên, là một cách để "số hóa" đồ thị thôi. Nó cho em biết thông tin như :đồ thị có bao nhiêu đỉnh (chính là cấp của ma trận) mà đỉnh nào được nối với nhau (đã nói ở trên). Trong quá trình em duyệt ma trận thì em xét giá trị của các phần tử để xem đỉnh đang duyệt tới có kề với đỉnh đang xét không. Nói vậy không biết em có hiểu được không (không có khiếu sư phạm ) |
#8
|
||||
|
||||
em thấy mặt cười mà nỏ cười được.em cụng muốn hiểu lắm chứ
bài của em cụng được thầy gọi là đồ án hix nhưng nỏ ai hướng dẫn .nhưng anh ơi em vẫn chưa biết làm răng .làm răng để có chương trình để đến hôm chạy cho thày coi. [ Tự động gộp bài ] em hiểu cây ni hơn 2. Tìm đường đi ngắn nhất bằng thuật toán Dijkstra Thuật toán Dijkstra chỉ áp dụng cho đồ thị có trọng số không âm. Tu tưởng thuật toán cũng dựa trên ý tưởng so sánh d[v] > d[u]+A[u][v] nhưng tối ưu hơn Ford-Bellmann nhờ giảm số vòng lặp lòng nhau trong quá trình xét các đỉnh. void Dijkstra(int *d, int s) { int T[MaxV]; for (int v=0; v<V; v++) { d[v] = A[s][v]; Truoc[v] = s; } d[s] = 0; T[s] = 1; while ( 1 ) { int u = -1; for (int z=0; z<V; z++) if (T[z] != 1 && (u==-1 || d[u] > d[z])) u = z; if (u == -1) break; T[u] = 1; for (int v=0; v<V; v++) if (T[v]!=1 && d[v]>d[u]+A[u][v]) { d[v] = d[u]+A[u][v]; Truoc[v] = u; } } } 3. Tìm đường đi từ đỉnh s đến đỉnh t. { Tìm đường đi dựa vào thông tin được lưu trong mảng Truoc[MaxV] int InDuongDi_sdTruoc(int Truoc[ ], int s, int t) { int STACK[MaxV], topS = 0; STACK[topS++] = t; while (Truoc[ STACK[topS-1] ] != s) STACK[topS++] = Truoc[ STACK[topS-1] ]; STACK[topS++] = s; cout<<"\nDuong di tu "<<s<<" den "<<t<<" la: "; for ( int i=topS-1; i>=0; i-- ) cout<<STACK[ i ] +1<<" "; } { Tìm đường đi dựa vào thông tin trọng số đường đi của các đỉnh được lưu trong mảng d[MaxV], không sử dụng thông tin của mảng trước. Đặc điểm: Nếu đỉnh u là đỉnh trước của v trên đường đi s đến v thì d[v] == d[u]+A[u][v] Dựa vào đặc điểm này để tìm ngược đường đi từ s đến t. int InDuongDi_ksdTruoc(int d[ ], int s, int t) { int STACK[MaxV], topS = 0; STACK[topS++] = t; int v = t; while ( v != s ) { int v = STACK[topS-1]; for (int u = 0; u<V; u++) if (d[v] == d[u]+A[u][v]) break; if ( u == V) break; STACK[topS++] = u; v = u; } cout<<"\nDuong di tu "<<s<<" den "<<t<<" la: "; for ( int i=topS-1; i>=0; i-- ) cout<<STACK[ i ] +1<<" "; } 4. Cài đặt hàm main ( ) Để hoàn thiện chương trình, phải sử dụng lại những hàm thao tác trên đồ thị đã được xây dựng trước: DocMTKe(…..), XuatMTKe(…..). Hãy copy chúng vào source code của chương trình. Định nghĩa hàm main ( ) để tìm đường đi trên đồ thị từ đỉnh s đến đỉnh t của đồ thị. Source code main ( ) int main(int argc, char* argv[]) { DocMTKe("D:\\GRAPH1.TXT", A, V); XuatMTKe(A, V); int s, t; printf("Nhap dinh dau, dinh cuoi cua duong di: "); scanf("%d %d", &s, &t); int d[MaxV]; memset( d, 0, sizeof(d) ); // Ford_Bellman( d, s ); // Chon 1 trong 2, thuat toan nao cung duoc ! Dijkstra( d, s ) ; // InDuongDi_sdTruoc(Truoc, s, t); // Chon 1 trong 2, ham nao cung duoc! InDuongDi_ksdTruoc(d, s, t); getch(); return 0; } thay đổi nội dung bởi: nguyen_mai193, 14-06-2009 lúc 10:35 PM. Lý do: Gộp bài viết gần nhau |
Ðang đọc: 1 (0 thành viên và 1 khách) | |
|
|
Chủ đề liên quan | ||||
Ðề tài | Người Gửi | Chuyên mục | Trả lời | Bài mới |
[Hóa Học] Một bài tập hóa học hữu cơ có đến 12 cách giải! | nickname | Giúp nhau học tập | 1 | 17-05-2009 01:45 PM |
[Hỏi] môn cấu trúc dữ liệu và giải thuật | nhatruc | Công nghệ thông tin - Viễn thông | 11 | 30-03-2009 08:18 AM |
[Khác] Giải bài tập tin học 11 Pascal đây | APOLONG | Thành viên NYT trổ tài | 4 | 13-01-2009 11:58 PM |
[Chuyên ngành] Đến với ngân hàng dữ liệu bài giảng trực tuyến | ngoanhtuan | Thảo luận nghiêm túc | 2 | 29-10-2008 01:23 PM |
Hướng dẫn Gửi Bài Viết lên diễn đàn | Nguyen_Thu | Hướng dẫn sử dụng diễn đàn | 4 | 11-10-2008 02:50 PM |