Code thuật giải A* nè các bạn!


Diễn đàn chia sẻ kiến thức, kinh nghiệm về IT và cuộc sống!
 
Trang ChínhGalleryTrợ giúpTìm kiếmThành viênNhómĐăng kýĐăng Nhập
Top posters
Sakura (1124)
 
hotboy (705)
 
Già Làng (373)
 
con_ca_nho90 (289)
 
that_true (154)
 
theanhkkt (143)
 
phamay (137)
 
lovelonelyman (134)
 
o0ovioletstaro0o (128)
 
stevenhung (122)
 
Âm - Dương lịch
Clock
Logo
11TH02 Pro!
Liên kết
Tin tức 60s
Tin công nghệ
Thời sự 24h
Game Moblie

Share | 
 

 Code thuật giải A* nè các bạn!

Xem chủ đề cũ hơn Xem chủ đề mới hơn Go down 
Tác giảThông điệp
Sakura


avatar

Thú CƯng :
Nam Scorpio

Số bài viết : 1124
Điểm : 1688
Được cảm ơn : 35
Ngày sinh : 03/11/1990
Tham gia ngày : 16/03/2010
Tuổi : 26
Đến từ : Bình Dương
Ngề nghiệp : IT Student

Bài gửiTiêu đề: Code thuật giải A* nè các bạn!   19/11/2010, 12:22

Bài này có lẽ là bài khó nhất trong các buổi thực hành của chúng ta. Và sau đây là đoạn code đã được mình trình bày rất gọn gẽ, rõ ràng rồi, sáng ai làm chưa ra thì có thể coi ở đây!

Code:
/*
   Thuat giai A*
   Programming by Edward_Thien
*/

//Include Header Files
#include <iostream>
#include <conio.h>
#include <stdio.h>
#include <iomanip>

//Using namespcase
using namespace std;

//Define consts
const int MAX = 100;

//Declare Data struct
typedef struct DINH
{
   int name;      //Ten
   int f;         //Chi phi g(s) + h(s)
   int g;         //Chi phi tu S --> dinh do
   int prev;      //Luu dinh truoc no
};

typedef struct ARRAY
{
   int n;
   int data[MAX];
};

typedef struct ARRAYDINH
{
   int n;
   DINH data[MAX];
};

typedef struct MATRIX
{
   int n;
   int data[MAX][MAX];
};

//Global variable
int n;            //So dinh
MATRIX DT;         //Do thi khoang cach
ARRAY H;         //Mang chua H
ARRAYDINH O;      //Tap Open
ARRAYDINH C;      //Tap Close

//Prototype
void ReadFile();                              //Doc file
void OutMatrix(MATRIX A);                        //Xuat Matrix
void OutArray(ARRAY A);                           //Xuat Array
void Init();                                 //Khoi tao
int FindMin();                                 //Tim min
void AddToList(DINH n, ARRAYDINH &A);               //Them 1 dinh vao danh sach
void RemoveFromList(int index, ARRAYDINH &A);         //Xoa 1 dinh khoi danh sach
int IsInList(int name, ARRAYDINH A);               //Kiem tra xem dinh do co trong danh sach hay ko?
void Process(int begin);                        //Ham xu ly chinh
void OutResult(int begin);                              //Xuat ket qua

//Main function
int main()
{
   ReadFile();
   OutMatrix(DT);
   cout<<endl;
   OutArray(H);
   cout<<endl;
   Init();
   Process(0);
   OutResult(0);
   _getch();
   return 0;
}

//Define functions
void ReadFile()
{
   FILE *f;
   f = fopen("C:\\Asao.txt", "r");
   if(f == NULL)
   {
      cout<<"Loi mo file";
      return;
   }

   fscanf(f, "%d", &DT.n);
   for(int i = 0; i < DT.n; i++)
   {
      for(int j = 0; j < DT.n; j++)
      {
         fscanf(f, "%d", &DT.data[i][j]);
      }
   }
   H.n = DT.n;
   for(int k = 0; k < H.n; k++)
   {
      fscanf(f, "%d", &H.data[k]);
   }
   fclose(f);
}

void OutMatrix(MATRIX DT)
{
   cout<<DT.n<<endl;
   for(int i = 0; i < DT.n; i++)
   {
      for(int j = 0; j < DT.n; j++)
      {
         if(DT.data[i][j] == 32000)
         {
            cout<<setw(5)<<"--";
         }
         else
         {
            cout<<setw(5)<<DT.data[i][j];
         }
      }
      cout<<endl;
   }
}

void OutArray(ARRAY H)
{
   for(int k = 0; k < H.n; k++)
   {
      cout<<setw(5)<<H.data[k];
   }
}

void Init()
{
   O.n = C.n = 0;
}

int FindMin()
{
   int min = 0;
   for(int i = 1; i < O.n; i++)
   {
      if(O.data[i].f < O.data[min].f)
      {
         min = i;
      }
   }
   return min;
}

void AddToList(DINH n, ARRAYDINH &A)
{
   A.data[A.n++] = n;
}

void RemoveFromList(int index, ARRAYDINH &A)
{
   A.data[index] = A.data[A.n-- - 1];
}

int IsInList(int name, ARRAYDINH A)
{
   for(int i = 0; i < A.n; i++)
   {
      if(A.data[i].name == name)
      {
         return i;
      }
   }
   return -1;
}

void Process(int begin)
{
   DINH S;
   S.name = begin;
   S.g = 0;
   S.f = H.data[begin];
   AddToList(S, O);

   DINH N = S;
   int vitrimin = 0;
   while(S.name != 8)
   {
      int vitri = FindMin();
      S = O.data[vitri];
      for(int i = 0; i < DT.n; i++)
      {
         //Mo cac Q ke voi N, Q khong thuoc C
         if(DT.data[S.name][i] > 0 && IsInList(i, C) == -1)
         {
            vitri = IsInList(i, O);
            //Q thuoc O
            if(vitri >= 0)
            {
               if(S.g + DT.data[S.name][i] < O.data[vitri].g)
               {
                  O.data[vitri].g = S.g + DT.data[S.name][i];
                  O.data[vitri].f = O.data[vitri].g + H.data[i];
                  O.data[vitri].prev = S.name;
               }
            }
            //Q khong thuoc O
            else
            {
               DINH Q;
               Q.name = i;
               Q.g = S.g + DT.data[S.name][i];
               Q.f = Q.g + H.data[i];
               Q.prev = S.name;
               AddToList(Q, O);
            }
         }
      }//Het for
      AddToList(S, C);
      RemoveFromList(vitrimin, O);
      vitrimin = FindMin();
      S = O.data[vitrimin];
   }//Het while
   AddToList(S, C);
}

void OutResult(int begin)
{
   int ten = 8;
   int v = IsInList(ten, C);
   int sum = 0;
   cout<<"\nDuong di la: ";
   cout<<ten;
   while(ten != begin)
   {
      int vitri = IsInList(ten, C);
      ten = C.data[vitri].prev;
      cout<<" <- "<<ten;
   }
   cout<<"\nDo dai duong di: "<<C.data[v].g;
}



/*
   END
*/

Bonus thêm cái đồ thị:
Code:
9
0 5 4 3 0 0 0 0 0
5 0 3 0 7 8 0 0 0
4 3 0 0 0 2 0 0 0
3 0 0 0 0 4 4 0 0
0 7 0 0 0 1 0 0 6
0 8 2 4 1 0 0 0 0
0 0 0 4 0 0 0 7 0
0 0 0 0 0 0 7 0 3
0 0 0 6 0 0 0 3 0
10 8 7 9 5 4 7 1 0

AI khỏi thi thực hành --> khỏe qua! Hehe!

_________________________________________________
Khách viếng thăm muốn liên hệ với mình thì xem thông tin phía dưới nha:
Email: [You must be registered and logged in to see this link.]
Nick Yahoo: Edward_Thien
Về Đầu Trang Go down
Xem lý lịch thành viên
 

Code thuật giải A* nè các bạn!

Xem chủ đề cũ hơn Xem chủ đề mới hơn Về Đầu Trang 
Trang 1 trong tổng số 1 trang

 Similar topics

-
» 0912976289 - Vải địa kỹ thuật, giấy dầu xây dựng, rọ đá, matit chèn khe, lưới B40 mạ kẽm bọc nhựa PVC
» Bán đất KD mặt đường Lê Viết Thuật TP Vinh
» Bán nhà khu dân cư Thuận Giao Bình Dương
» Cần sang nhượng Quầy thuốc, tại Kiều Mai, xã Phú Diễn, huyện Từ Liêm, Hà Nội.
» Cần chuyển nhượng nhà thuốc GPP, tại số 29 Đặng Tiến Đông, quận Đống Đa, Hà Nội.

Permissions in this forum:Bạn không có quyền trả lời bài viết
IT World! :: HỌC TẬP :: HỌC KỲ V :: Cơ Sở Trí Tuệ - Trí Tuệ Nhân Tạo-