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 2. Đường đi Hamilton

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 2. Đường đi Hamilton

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

Ứng dụng đường đi Hamilton


Một người khách du lịch muốn đi thăm n thành phố được đánh số từ 1 đến n, mỗi thành phố người khách chỉ muốn đi qua chúng một lần. Mạng lưới giao thông giữa n thành phố là hai chiều và được cho bởi ma trận A[i,j] trong đó A[i,j] =1 nếu có đường đi giữa thành phố i và thành phố j, A[i,j] = 0 trong trường hợp ngược lại.
Hãy viết chương trình thiết lập cho người khách một lộ trình (có thể tồn tại nhiều lộ trình) hay thông báo không tồn tại lộ trình theo yêu cầu của khách.
Dữ liệu vào: cho trong file Bai6.inp
- Dòng đầu ghi số n là số đỉnh của một đồ thị (0- Dòng 2 ghi đỉnh mà người khách du lịch xuất phát.
- Dòng i+2 (0 < i<=100) 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: In ra màn hình đường đi của người khách (nếu có).

Ví dụ:
Bai6.inp
5
1
0 1 0 0 0
1 0 1 1 1
0 1 0 1 0
0 1 1 0 1
0 1 0 1 0
Kết quả:1->2->3->4->5

Bai6.inp
6
1
0 1 1 0 0 0
1 0 1 0 1 0
1 1 0 0 0 1
0 0 0 0 1 0
0 1 0 1 0 0
0 0 1 0 0 0
Kết quả: KHONG TON TAI DUONG DI

Bai6.inp
5
2
0 1 0 1 1
1 0 1 0 1
0 1 0 1 0
1 0 1 0 1
1 1 0 1 0
Kết quả: 2->1->5->4->3

HƯỚNG DẪN THUẬT TOÁN
Sử dụng kỹ thuật tìm kiếm theo chiều sâu.
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.
- Điều kiện dừng : nếu mọi đỉnh đều được đi qua hay số đỉnh tìm kiếm được bằng số đỉnh n của đồ thị.
- Điều kiện đệ quy: khi không thoả mãn điều kiện dừng.
CHƯƠNG TRÌNH MẪU

Code:
#include <stdio.h>
#include <conio.h>
#include <iostream.h>
#define FileIn "Bai6.inp"
int Dem = 0;      //Dếm số đường đi
int*L;         //Lưu lại đường đi
char*DanhDau;   //Dánh dấu đỉnh đã đi
int **A,n,D;
/*Dọc file dữ liệu bài toán*/
void Doc_File() {
   FILE*f = fopen(FileIn,"rb");
   fscanf(f,"%d%d",&n,&D);      //Đọc n và đỉnh xuất phát lưu trong biến D
   cout<<"Ma Tran Lien Ket Tuong Ung.\n"<<D<<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--;
}
/*Khởi tạo dữ liệu ban đầu cho bài toán*/
void KhoiTao() {
   DanhDau = new char [n];
   L = new int [n];
   for (int i = 0; i<n; i++) {   
      DanhDau[i] = 0;   //Khởi tạo mọi đỉnh chưa được đánh dấu
      L[i] = 0;
   }
   DanhDau[D] = 1;      //Đánh dấu đỉnh xuất phát
   L[0] = D;
}
/*In đường đi của bài toán ra màn hình*/
void InDuongDi(int Dinh) {
   Dem++;
   cout<<endl<<D+1;
   for (int i = 1; i<Dinh; i++)
      cout<<" -> "<<L[i]+1;
}
/*Tìm kiếm đường đi*/
void TimKiem(int Dinh) {
   if(Dinh == n && Dem == 0) InDuongDi(Dinh);
   else {
      for(int i = 0; i<n; i++)
      if( A[L[Dinh-1]][i]>0 && DanhDau[i] == 0 && Dem==0){
         L[Dinh] = i;
         DanhDau[i] = 1;   //Đánh dấu đỉnh tìm được
         TimKiem(Dinh+1);   //Tiếm kiếm đỉnh kế tiếp
         L[Dinh] = 0;
         DanhDau[i] = 0;   //Phục hồi đỉnh đánh dấu
      }
   }
}
/*Chương trình chính*/
void main() {
   clrscr();
   Doc_File();
   KhoiTao();
   cout<<"Duong Di Nguoi Khach";
   TimKiem(1);      //Tìm kiếm từ đỉnh thứ 2 của đồ thị
   if(Dem==0)
      cout<<" Khong Co";
   delete*A,DanhDau,L;
   getch();
}

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