Gia sư Cần Thơ, Dạy Kèm Cần Thơ

VỮNG TIN - TIẾP BƯỚC - THÀNH CÔNG


Bài 3. Đường đi dài nhất từ thành phố D đến thành phố C

Share
avatar
admin
Admin
Admin

Tổng số bài gửi : 1207
Points : 3010
Join date : 11/11/2009
Age : 36
Đến từ : Cần Thơ

Bài 3. Đường đi dài nhất từ thành phố D đến thành phố C

Bài gửi  admin on Sat Dec 19, 2009 12:37 pm

Đường đi dài nhất từ thành phố D đến thành phố C


Có n thành phố biết rằng đường đi giữa các thành phố là đường đi hai chiều. Sơ đồ mạng lưới giao thông của n thành phố cho bởi ma trận A[i,j] trong đó:
- A[i,j] là độ dài đường đi từ thành phố i đến thành phố j.
- A[i,j] = 0 nếu không có đường đi từ thành phố i đến thành phố j.
- A[i,j] = A[j,i]
- A[i,j] nguyên, không âm.
Hãy xác định đường đi dài nhất từ thành phố D đến thành phố C với điều kiện thành phố đã qua không được đi lại.
Dữ liệu vào:đồ thị đã liên thông và cho trong file Bai10.inp
- Dòng đầu ghi số n là số đỉnh của một đồ thị (0< n <100)
- Dòng thứ hai lưu đỉnh D và đỉnh C.
- Dòng i+2 (1<= i <=n) chứa n số A[i,1],A[i,2]…A[i,n] mỗi số cách nhau bởi một khoảng trắng.
Dữ liệu ra: xuất ra màn hình đường đi dài nhất từ đỉnh D đến C và giá trị đường đi ngắn nhẩt tìm được.
INPUT 1
6
1 6
0 1 2 0 0 0
1 0 2 2 3 0
2 2 0 5 4 0
0 2 5 0 3 2
0 3 4 3 0 4
0 0 0 2 4 0

OUTPUT 1
DUONG DI DAI NHAT LA: 16
1->2->4->3->5->6

INPUT 2
6
1 6
0 1 4 0 0 0
1 0 2 6 5 0
4 2 0 7 3 0
0 6 7 0 0 1
0 5 3 0 0 3
0 0 0 1 3 0

OUTPUT 2
DUONG DI DAI NHAT LA: 25
1->3->4->2->5->6

HƯỚNG DẪN CÀI ĐẶT
Sử dụng kỹ thuật cài đặt tìm kiếm theo phương pháp đệ quy, khi tìm được 1 phương án thì lưu lại trạng thái của phương án ban đầu và so sánh với phương án mới tìm được, nếu phương án mới tốt hơn thì chọn phương án mới.

Code:
include <stdio.h>
#include <conio.h>
#include <iostream.h>
#define Filename "Input.inp"
/*Khai báo các biến toàn cục*/
int*L,*L1;      //Luu lai duong da di
char*DanhDau;   //Danh dau dinh da di
int **A,n,D,C,Tong,Tong1,Canh1;
/*Dọc file dữ liệu của bài toán*/
void Doc_File() {
   FILE*f = fopen(Filename,"rb");
   fscanf(f,"%d%d%d",&n,&D,&C);
   cout<<"Ma Tran Lien Ket Tuong Ung.\n"<<D<<" "<<C<<endl;
   *A = new int [n];
   for(int i =0;i<n;i++) {
      A[i] = new int [n];
      for(int j =0;j<n;j++) {
         fscanf(f,"%d",&A[i][j]);
         cout<<A[i][j]<<" ";
      }
      cout<<endl;
   }
   fclose(f);
   D--; C--;
}
/*Khởi tạo ban đầu cho thủ tục tìm kiếm*/
void KhoiTao() {
   DanhDau = new char [n];   
   L = new int [n];      //Lưu đường đi tìm được
   L1 = new int [n];      //Lưu đường đi lớn nhất
   for (int i = 0; i<n; i++) {
      DanhDau[i] = 0;   //Các đỉnh chưa được đánh dấu
      L[i] = 0;
   }
   DanhDau[D] = 1;      //Dánh dấu đỉnh xuẩt phát
   L[0] = D;         //Đường đi đầu tiên qua đỉnh đầu
   Tong = 0;         //Trong số đường đi
   Tong1 = 0;         //Lưu lại trọng số lớn nhất của đường đi
}
/*In đường đi dài nhất tìm được*/
void InDuongDi() {
   cout<<"\nDUONG DI DAI NHAT:"<<Tong1<<endl<<D+1;
   for (int i = 1; i<Canh1; i++)
      cout<<" -> "<<L1[i]+1;
}
/*Xử lý để lấy phương án tổt hơn*/
void XuLy(int Canh) {
   if(Tong>Tong1){
      Tong1 = Tong;      //Lưu lại trọng số tốt hơn
      Canh1 = Canh;      //Lưu lại số cạnh đã đi qua
      for(int i =0; i<Canh; i++)
         L1[i] = L[i];      //Lưu lại đường đi tốt hơn
   }
}
/*Thủ tục tìm kiếm đệ quy*/
void TimKiem(int SoCanh) {
   if(L[SoCanh-1] == C) XuLy(SoCanh);
   else {   for(int i = 0; i<n; i++)
      if( A[L[SoCanh-1]][i]>0 && DanhDau[i] == 0){
         L[SoCanh] = i;
         DanhDau[i] = 1;
         Tong+=A[L[SoCanh-1]][i];
         TimKiem(SoCanh+1);
         L[SoCanh] = 0;
         Tong-=A[L[SoCanh-1]][i];
         DanhDau[i] = 0;
      }
   }
}
void main() {
   Doc_File();
   KhoiTao();
   TimKiem(1);
   if(Tong1==0)   cout<<"\NKHONG CO DUONG DI";
   else   InDuongDi();
   delete*A,DanhDau,L;
   getch();
}


Được sửa bởi Admin ngày Thu May 26, 2011 8:33 am; sửa lần 2.

qvluom
Sơ cấp
Sơ cấp

Tổng số bài gửi : 23
Points : 29
Join date : 26/11/2009

Re: Bài 3. Đường đi dài nhất từ thành phố D đến thành phố C

Bài gửi  qvluom on Tue Dec 22, 2009 8:06 pm

Đây phải nói là một bài toán khó. Rất nhiều người đã nhằm lẫn và vội vàng áp dụng ngay một số giải thuật tìm đường đi ngắn nhất để giải. Tuy nhiên, cho dù là dùng cách nào (lấy nghịch đảo, đối, bù,...) thì tất cả cũng đều sai. Xem ra đệ quy vẫn là một giải pháp an toàn. Very Happy

leanhsonvn
Nhập môn
Nhập môn

Tổng số bài gửi : 2
Points : 2
Join date : 12/02/2011

Xin các đại ca chỉ giáo

Bài gửi  leanhsonvn on Sat Feb 12, 2011 4:34 pm

- Đồ thị đã liên thông và cho trong file Bai 10 là ở đâu vậy ạ?
- Admin có thể nói kỹ hơn về phương pháp làm được không, Mình đang cần bài này và định sử dụng phần mềm matlab nhưng ko biết có được ko? thank you nhiều nhiều
avatar
admin
Admin
Admin

Tổng số bài gửi : 1207
Points : 3010
Join date : 11/11/2009
Age : 36
Đến từ : Cần Thơ

Re: Bài 3. Đường đi dài nhất từ thành phố D đến thành phố C

Bài gửi  admin on Sun Feb 13, 2011 10:29 am

leanhsonvn đã viết:- Đồ thị đã liên thông và cho trong file Bai 10 là ở đâu vậy ạ?
- Admin có thể nói kỹ hơn về phương pháp làm được không, Mình đang cần bài này và định sử dụng phần mềm matlab nhưng ko biết có được ko? thank you nhiều nhiều

Bai10.inp hoặc Input.inp là file dữ liệu đầu vào được mô tả trong bài toán.

leanhsonvn
Nhập môn
Nhập môn

Tổng số bài gửi : 2
Points : 2
Join date : 12/02/2011

Giúp đỡ

Bài gửi  leanhsonvn on Wed Feb 16, 2011 8:03 am

Mình đang muốn làm bài toán này nhưng với trường hợp tìm đường đi không cố định. Tức là không cố định đi từ điểm A đến điểm D mà nó sẽ chạy lần lượt tất cả các phương án: tìm đường đi dài nhất cho tất cả các trường hợp: A đến B, A đến C, A đến D,...., B đến C, B đến D,..... Làm mãi mà vẫn bị treo. Xin admin giúp đỡ, cảm ơn bội phần (mail: leanhsonvn@gmail.com). Đa tạ
avatar
admin
Admin
Admin

Tổng số bài gửi : 1207
Points : 3010
Join date : 11/11/2009
Age : 36
Đến từ : Cần Thơ

Re: Bài 3. Đường đi dài nhất từ thành phố D đến thành phố C

Bài gửi  admin on Wed Feb 16, 2011 8:28 am

leanhsonvn đã viết:Mình đang muốn làm bài toán này nhưng với trường hợp tìm đường đi không cố định. Tức là không cố định đi từ điểm A đến điểm D mà nó sẽ chạy lần lượt tất cả các phương án: tìm đường đi dài nhất cho tất cả các trường hợp: A đến B, A đến C, A đến D,...., B đến C, B đến D,..... Làm mãi mà vẫn bị treo. Xin admin giúp đỡ, cảm ơn bội phần (mail: leanhsonvn@gmail.com). Đa tạ

Mong muốn quả thật là mong muốn. Nếu bạn sử dụng thuật toán vét cạn như trên thì độ phức tạp rất lớn dạng hàm mũ. Vì vậy bạn nên kết hợp với kỹ thuật cắt tỉa và tiến hành khử đệ quy cho phương pháp tìm kiếm trên thì thuật toán sẽ tốt hơn.

tranghihi
Nhập môn
Nhập môn

Tổng số bài gửi : 1
Points : 1
Join date : 04/03/2012

Re: Bài 3. Đường đi dài nhất từ thành phố D đến thành phố C

Bài gửi  tranghihi on Sun Mar 04, 2012 11:09 am

Admin ơi!. Giúp em với đầu vào bài toán của em là đồ thị không có chu trình.Anh có giải thuật nào để kiểm tra đồ thị có chu trình hay không ạ. Chỉ giúp em với. Em cám ơn anh.
avatar
admin
Admin
Admin

Tổng số bài gửi : 1207
Points : 3010
Join date : 11/11/2009
Age : 36
Đến từ : Cần Thơ

Re: Bài 3. Đường đi dài nhất từ thành phố D đến thành phố C

Bài gửi  admin on Fri Mar 09, 2012 8:49 am

tranghihi đã viết:Admin ơi!. Giúp em với đầu vào bài toán của em là đồ thị không có chu trình.Anh có giải thuật nào để kiểm tra đồ thị có chu trình hay không ạ. Chỉ giúp em với. Em cám ơn anh.

Câu hỏi của bạn rất hay. Bạn xem thuật toán kruskal tìm cây phủ tối tiểu. Trên thuật toán đó tác giả đã xử lý vấn đề đồ thị có chu trình hay không. Em vào mục đồ thị xem nhé!


Gia sư Alpha
------------------------------------------------------------------------------------
Điện thoai: 07106 255 599 - 0932 836 026 - 0987 700 288
Website: http://giasualpha.com
Email: giasualpha@gmail.com
------------------------------------------------------------------------------------

luongnhutduy
Nhập môn
Nhập môn

Tổng số bài gửi : 11
Points : 19
Join date : 13/02/2012
Age : 25

tìm mọi đường đi

Bài gửi  luongnhutduy on Sat Apr 14, 2012 8:38 pm

Tại sao anh ko dùng thuật toán FLOYD á, tìm mọi đường đi của đồ thị luôn(nhưng nó là ngắn nhất) mình sữa tí thôi.
thuật toán là như thế này nè:
- từ một đồ thị bất kì, ta được tìm 2 ma trận W0 và P0. Trong đó,
+ W0 là ma trận liên kết giữa các đỉnh.
+ P0 là ma trận chứa đỉnh đứng ngay sau đỉnh Vi trước nó.
* giải thuật:
1. W0=W, P0[i,j]=(Vj khi W[i,j]< vô cùng, ko xác định khi W0[i,j]= vô cùng), với 12. xây dựng Wk và Pk(1- xét đẳng thức Wk-1[i,j]> Wk-1[i,k]+Wk-1[k,j] nếu đúng thì đặt
Wk[i,j]> Wk-1[i,k]+Wk-1[k,j] và Pk[i,j]= Pk-1[i,k].
- nếu sai thì đặt
Wk[i,j]>Wk[i,j] và Pk[i,j]=Pk-1[i,j]
*NOTE: đồ thì có 7 đỉnh thì có 7 ma trận W và 7 ma trận P. Cách cập nhật kq là: con đường đi từ Vi tới Vj có chiều dài là W*[i,j], đỉnh đứng ngay sau Vi trên con đường này là P*[i,j].Làm tay thì rất dài nhưng cái này là code cho máy mà, e nghĩ cũng nhanh. em suy nghĩ hoài mà ko code được, chừng nào em suy nghĩ ra em code lên(NÀO GIỜ CODE TRÊN 1 MA TRẬN HÀ, LẦN NÀY 2 NÊN BỊ BỠ NGỞ). THÂN MẾM ANH VÀ THẦY.
avatar
admin
Admin
Admin

Tổng số bài gửi : 1207
Points : 3010
Join date : 11/11/2009
Age : 36
Đến từ : Cần Thơ

Re: Bài 3. Đường đi dài nhất từ thành phố D đến thành phố C

Bài gửi  admin on Sun Apr 15, 2012 11:47 am

tranghihi đã viết:Admin ơi!. Giúp em với đầu vào bài toán của em là đồ thị không có chu trình.Anh có giải thuật nào để kiểm tra đồ thị có chu trình hay không ạ. Chỉ giúp em với. Em cám ơn anh.

Em thêm kiểm tra đỉnh cuối có đường đi đến đỉnh đầu hay không thì tìm được chu trình của nó.


Gia sư Alpha
------------------------------------------------------------------------------------
Điện thoai: 07106 255 599 - 0932 836 026 - 0987 700 288
Website: http://giasualpha.com
Email: giasualpha@gmail.com
------------------------------------------------------------------------------------

Sponsored content

Re: Bài 3. Đường đi dài nhất từ thành phố D đến thành phố C

Bài gửi  Sponsored content


    Hôm nay: Mon Nov 20, 2017 4:39 pm