Chắc sẽ có nhiều người click vào topic này vì cái tiêu đề hơi ngộ.
Đúng là hơi ngộ thật. Nhưng thiết nghĩ, nó thực tế, các bạn à. Là vầy:
Giả sử, một ngày đẹp trời nào đó, bạn nổi hứng thích đi xe bus. Nếu có "bài toán" này trong tay, bạn chỉ việc mở ra, nhập vào trạm mà bạn sẽ đón xe bus mà gần nhà bạn nhất, nhập tiếp trạm mà gần nơi bạn muốn đến nhất, thế là Excel sẽ chỉ cho bạn phải đón xe số mấy, và lỡ như mà phải đón từ 2 chiếc bus trở lên, thì Excel cũng sẽ chỉ cho bạn tới trạm nào nhảy xuống, sang qua xe số mấy nữa... sao cho số lần đón xe là ít nhất. Đồng thời sẽ cho bạn biết luôn sẽ phải thủ trong túi bao nhiêu đặng mà mua vé xe bus.
Nghe thì hay chứ hỉ! Nhưng mần làm sao bi chừ? BNTT tui chỉ được cái là "nghĩ ra" giỏi thôi, chứ thực hiện thì... hơi bị cù lần tí. Nên đem lên đây, rủ các bạn chung tay góp sức cho "Bài toán tìm xe bus ở Tp.HCM" này.
Để mở hàng (phải làm chứ, vẽ chuyện ra mà không có gì ai mà chấp nhận được), BNTT tui đã sưu tầm được tất cả các tuyến xe bus có trong thành phố HCM, mỗi file là của một tuyến xe, trong đó có ghi rất cụ thể các trạm xe bus mà nó đi ngang qua, đồng thời cũng cho biết những tuyến xe nào sẽ đi ngang qua trạm đó.
Phải bắt đầu từ đâu, nói thật tui cũng chưa nghĩ ra. Có lẽ là phải gom tất cả 113 tuyến xe bus này vào trong một file duy nhất, rồi... Thôi, chúng ta cùng chung sức nhé!
Cái này của bác sao giống GPS quá! Chỉ thiếu cái bảng đồ lộ trình nữa là OK rồi. Có thể đem đi bán phần mềm được đó. Hiiii Mà là 1 file hay 113 file vậy? Bác có thể tổng hợp số liệu theo mã số tuyến không? Như vậy sẽ dễ viết code hơn. Nhìn vào đống này chắc đui luôn quá!!!! Th ân.
Đó mới chỉ là những file dữ liệu thô. Có tất cả 113 file (được nén lại thành 1 file *.rar để gửi lên) ứng với 113 tuyến xe bus hiện tại.
Chắc chắn là phải làm tổng hợp lại rồi, vào trong 1 file duy nhất thôi. Nhưng mình đang còn chưa biết phải tổng hợp như thế nào. Đang đợi sư nương online rồi tư vấn cho vài chiêu nhưng chiều giờ chưa thấy.
Vấn đề này thì tôi cũng đã thử nghĩ đến, khi mà phải tìm kiếm tuyến xe buýt ở Hà Nội.
Quan trọng là cách bố trí dữ liệu của chúng ta trong Excel.
Mã tuyến xe buýt|Các tuyến đường xe buýt đi qua|Chi tiết
TX1|Thủ Đức, Võ Văn Ngân, Bình Triệu, Hàng xanh, Bến thành|Thủ Đức > Võ Văn Ngân> Bình Triệu>
Khi tìm kiếm chúng ta sẽ nhập vào:
1. Địa điểm xuất phát
2. Địa điểm đến
Khi chương trình tìm kiến Địa điểm xuất phát và Địa điểm đến đều có trong chuỗi ở cột thứ hai, thì sẽ đưa các thông tin khác của các tuyến xe buýt tìm được ra cho người dùng.
Đó là bài toán đơn giản. Còn nếu khó hơn thì ngoài thông tin của tuyến xe buýt thì còn cần:
_ Tuyến xe buýt nào là tuyến chạy ngắn nhất.
_ Chiều dài đoạn đường tương ứng cho các tuyến xe buýt được tìm thấy.
Vv...
Để có thêm những thông tin này thì dữ liệu chúng ta cần phải cụ thể hơn.
Thuật toán tìm đường có nhiều loại lắm, bạn nói cụ thể hơn trường hợp bạn muốn đi, mà nói chung thì đây là một thuật toán khá khó và không dể hình dung khi xem code, nếu tìm hiểu lý thuyết thì sẽ dể dàng hơn. Thuật toán tìm điển hình có thể nói đến Dijkstra, A*
Tìm đường đi ngắn nhất từ một nút tới tất cả các node còn lại. - Thuật toán Dijkstra :
1) Gán tập giá trị set = trống,
2) Kiểm tra khoảng cách từ nut s tới các nut còn lại (khoảng cách(s, s) = 0, khoảng cách (s, t) = x)
3) Lặp lại cho đến khi tất cả các nút được đưa vào tập set
4) Tìm ra một nút d với khoảng cách tới s là ngắn nhất
5) Đưa d vào tập set
6) Cập nhật khoảng cách từ s tới tất cả các nút khác sử dụng:
7) Nếu distance(s, m) > distance(s, d) + dist(d, m)
8/ thì distance(s, m) = distance(s, d) + dist (d, m)
Thuật toán trên thể hiện trên java
Mã:
//
// This file contains the Java code from Program 16.15 of
// "Data Structures and Algorithms
// with Object-Oriented Design Patterns in Java"
// by Bruno R. Preiss.
//
// Copyright (c) 1998 by Bruno R. Preiss, P.Eng. All rights reserved.
//
// http://www.pads.uwaterloo.ca/Bruno.Preiss/books/opus5/programs/pgm16_15.txt
//
public class Algorithms
{
public static Digraph DijkstrasAlgorithm (Digraph g, int s)
{
int n = g.getNumberOfVertices ();
Entry[] table = new Entry [n];
for (int v = 0; v < n; ++v)
table [v] = new Entry ();
table [s].distance = 0;
PriorityQueue queue =
new BinaryHeap (g.getNumberOfEdges());
queue.enqueue (
new Association (new Int (0), g.getVertex (s)));
while (!queue.isEmpty ())
{
Association assoc = (Association) queue.dequeueMin();
Vertex v0 = (Vertex) assoc.getValue ();
int n0 = v0.getNumber ();
if (!table [n0].known)
{
table [n0].known = true;
Enumeration p = v0.getEmanatingEdges ();
while (p.hasMoreElements ())
{
Edge edge = (Edge) p.nextElement ();
Vertex v1 = edge.getMate (v0);
int n1 = v1.getNumber ();
Int wt = (Int) edge.getWeight ();
int d = table [n0].distance + wt.intValue ();
if (table [n1].distance > d)
{ table [n1].distance = d;
table [n1].predecessor = n0;
queue.enqueue (
new Association (new Int (d), v1));
}
}
}
}
Digraph result = new DigraphAsLists (n);
for (int v = 0; v < n; ++v)
result.addVertex (v, new Int (table [v].distance));
for (int v = 0; v < n; ++v)
if (v != s)
result.addEdge (v, table [v].predecessor);
return result;
}
}
Đây là 1 bài về tìm đường bên gamedev.vn bạn có thể tham khảo: A* là chiến lược tìm kiếm được dùng rất nhiều ở các Game, kiến thức thức về A* có thể nói là một kiến thức thuộc loại MUST HAVE với bất kì ai lập trình AI cho Game.
Sách vở viết về A* bạn có thể tìm dễ dàng ở nhà sách. Đồng thời nếu bạn muốn tìm hiểu thì có thể đọc cái này
CÁC GIẢI THUẬT TÌM KIẾM HEURISTIC
Không gian tìm kiếm là một đồ thị trạng thái
Tìm hành trình ngắn nhất: xác định bởi việc cực tiểu hóa giá thành bằng giải thuật AT
Tìm kiếm với tri thức bổ sung: hướng tìm kiếm được xác định bằng tri thức bổ sung sau mỗi bước đi bằng giải thuật AKT
Giải thuật AT (Algorthm of Tree)
Trong không gian tìm kiếm, mỗi đỉnh n tương ứng với môt số g(n) giá thành đi từ đỉnh ban đầu đến đỉnh n.
Đỉnh đóng là những đỉnh đã được xét
Đỉnh mở là những đỉnh sẽ được xét
Gọi OPEN là tập chứa những đỉnh mở
Đỉnh đầu tiên x0 có g(0) = 0, đưa x0 vào OPEN
Lặp lại cho đến khi tới đích hoặc tập OPEN=NULL
Chọn đỉnh đến là đỉnh có g nhỏ nhất, gọi nó là đỉnh xmax ta có OPEN = OPEN - xmax
Nếu xmax là đỉnh đích thì kết thúc
Ngược lại, với mọi xi kề xmax
Tính g(xi) = g(xmax) + cost(xmax,xi)
Chọn xi là đỉnh đến có g(xi) nhỏ nhất
Thêm xi vào OPEN
Giải thuật AKT (Algorthm of Knowledgeable Tree)
Gọi là thuật toán tìm kiếm với tri thức bổ sung. Tri thức bổ sung là gì ? Giả sử bạn cần đến Hà Nội, mà bạn có 2 con đường cùng có thể đi đến đó. Một là đến Hải Phòng, sau đó sẽ tới Hà Nội. Hai là đến Vinh, sau đó sẽ ra Hà Nội. Vấn đề là bạn chọn đường nào ? Bạn có một tri thức bổ sung là đường từ Hải Phòng ra Hà Nội sẽ ngắn hơn đường từ Vinh ra Hà Nội, nên bạn chọn đường ra Hải Phòng.
Ở ví dụ trên đây, rõ ràng tri thức “đường từ Hải Phòng ra Hà Nội sẽ ngắn hơn đường từ Vinh ra Hà Nội” là một tri thức phỏng đoán rút tỉa từ kinh nghiệm (nếu bạn là người nước ngoài chưa đến Việt Nam bao giờ chẳng hạn bạn sẽ không có tri thức này)
Thuật toán AKT cũng vậy. Dựa vào các tri thức kinh nghiệm bổ sung, xây dựng cá hàm ước lượng, để cùng giá thành quyết định đường đi cho chính xác
Trong không gian tìm kiếm, mỗi đỉnh n tương ứng với môt số g(n) giá thành đi từ đỉnh ban đầu đến đỉnh n và một giá trị h(n) biểu hiện sự ước lượng của chúng ta giá thành để đi từ n đến đích.
Như vậy tổng chi phí của một đỉnh sẽ là f(n) = g(n) + h(n)
Chọn đỉnh đến là đỉnh có f nhỏ nhất, gọi nó là đỉnh xmax ta có OPEN = OPEN - xmax
Nếu xmax là đỉnh đích thì kết thúc
Ngược lại, với mọi xi kề xmax
Tính g(xi) = g(xmax) + cost(xmax,xi)
Tính h(xi) và tính f(xi) = g(xi) + h(xi)
Chọn xi là đỉnh đến có f(xi) nhỏ nhất
Thêm xi vào OPEN
Giải thuật A*
Đây là giải thuật cải tiến giải thuật AKT
Đỉnh đóng là những đỉnh đã được xét
A* sử dụng thêm tập CLOSE để lưu những đỉnh đã được xét
Khi xét đến một nút nào đó, ngoài f, g, h thì A* còn quan tâm đến
Danh sách các nút dẫn đến nút xi gọi là Cha(xi)
Danh sách các nút kế tiếp nút xi
Ví dụ 1 đồ thị như sau (gửi kèm bên dưới)
Khoảng cách tính theo đường chim bay từ 1 đỉnh bất kì đến đỉnh B như sau:
A 366 B 0 C 160 D 242
E 161 F 178 G 77 H 151
I 226 L 244 M 241 N 234
O 380 P 98 R 193 S 253
T 329 U 80 V 199 Z 374
Bây giờ ta thử tìm đường đi ngắn nhất từ A đến B B1:
OPEN = {A}
CLOSE = {}
A(g=0,h=0,f=0) B2:
OPEN = {}
CLOSE = {A}
A(g=0,h=366,f=366)
Từ A ta có 3 điểm có thể đi được là S,T,Z. Ta đi tính g,h,f của 3 điểm này
h(S) = 253
g(S) = g(A) + cost(A,S) = 0 + 140 = 140
f(S) = g(S) + h(S) = 140 + 253 = 393
Cha(S) = A
h(T) = 329
g(T) = g(A) + cost(A,T) = 0 + 118 = 118
f(T) = g(T) + h(T) = 118 + 329 = 447
Cha(T) = A
h(Z) = 374
g(Z) = g(A) + cost(A,Z) = 0 + 75 = 75
f(Z) = g(Z) + h(Z) = 374 + 75 = 449
Cha(Z) = A
OPEN = {S,T,Z}
CLOSE = {A}
Chọn xmax = S, loại xmax khỏi OPEN
OPEN = {T,Z}
CLOSE = {A,S} B3:
Từ S ta có 4 điểm có thể đi được là A,F,O,R. Ta đi tính g,h,f của 4 điểm này
A(h=366,g=280,f=646,cha=S)
g(A) mới = 280 > g(A) cũ = 0 nên không cần cập nhật lại giá trị của g và f của A trong CLOSE
(Nếu g(A) mới < g(A) cũ thì cần cập nhật lại giá trị của g và f của A trong CLOSE)
F(h=178,g=239,f=417,cha=S)
O(h=380,g=291,f=671,cha=S)
R(193,220,413,cha=S)
OPEN = {T,Z,F,O,R}
CLOSE = {A(0,0,0),S}
Tương tự như vậy ta được đường đi ngắn nhất A→S→R→P→B
Dựa vào thông tin cha(xi) đã lưu trữ cho xi ta lần ngược để tìm đường đi tối ưu và luôn nhớ cập nhật lại g,f nếu giá trị mới nhỏ hơn giá trị cũ.
Vậy thì để bắt đầu chúng ta cần phải tổng hợp dữ liệu từ các file của BNTT. Vậy ai có thể bắt tay vào tham gia nào ?
Vbavn
Cảm ơn anh Vbavn. Em có thể tổng hợp được. Nhưng tổng hợp như thế nào? Cần có những trường dữ liệu nào? Nếu em tổng hợp theo ý em, thì lại phải mất công sửa lại.
Anh có thể cho em một cái sườn không? Ví dụ, một cái bảng, chỉ cần tiêu đề cột thôi? Rồi em sẽ tổng hợp dữ liệu theo cái sườn này.
Minh muon viet mot web site ve lo trinh xe bus. Nhưng quả thực mình không biết bắt đầu từ đâu. Ở đây bài toán của mình muốn dựa trên một số framwork có sẳn của google để viết.:d Bạn nào có ý kiến j hay giúp mình với. Vì đây là ý tưởng cho đồ án tốt nghiệp của mình.
Giả sử mỗi địa điềm là 1 đỉnh của đồ thị
Khi áp dụng vào thực thế ta phải thêm 1 hàm đề Ánh xạ số sang địa điểm.
Biều diển Ma trận trên file text "Chart.txt" như sau:
5
0 3 100 7 100
100 0 100 2 100
5 11 0 100 3
100 100 1 0 12
100 100 100 6 0
--------------------------
Số 100 là Vô Cùng
Số 5 là số đỉnh đồ thị. kết quả cuối cùng :
Q là ma trận thể hiện đường đi ngắn nhất giữa các cặp đinh.Còn D là Ma trận trọng số(Độ dài ).
Code của thuật toán Floy như sau...
Mình trình bày = C++ Language
Mã:
#include<conio.h>
#include<stdio.h>
#include<iostream.h>
#include<fstream.h>
#include<iomanip.h>
#define MAX 100
typedef struct tagMatrix
{
int Q[MAX][MAX];
int D[MAX][MAX];
}
Matrix;
Matrix mt[MAX];int n;
int rchart(char* fn,int& n) //Doc do^` thi. tu*` file(do.c ma tra^n. du*o*`ng di
{
ifstream in;
in.open(fn);
in>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
in >> mt[0].D[i][j];
in.close();
return 1;
}
int create(char* fn,int n)
{
FILE* f=fopen(fn,"wt");
if(!f) return 0;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
if(mt[0].D[i][j]!=0 && mt[0].D[i][j]!=MAX)
mt[0].Q[i][j]=j;// neu ton tai duong di thi check
else
mt[0].Q[i][j]=0;//gan tat ca duong di con la =0
fprintf(f,"%3d",mt[0].Q[i][j]);
}
return 1;
}
void view(int T[MAX][MAX])
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(T[i][j]==MAX)
cout<<setw(5)<<"$";
else
cout<<setw(5)<<T[i][j];
}
cout<<endl<<endl;
}
}
void Floy()
{
int k=1;
while(k<(n+1))
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
int a=mt[k-1].D[i][k]+mt[k-1].D[k][j];
if(a<mt[k-1].D[i][j])
{
mt[k].D[i][j]=a;
mt[k].Q[i][j]=mt[k-1].Q[i][k];
}
else
{
mt[k].D[i][j]=mt[k-1].D[i][j];
mt[k].Q[i][j]=mt[k-1].Q[i][j];
}
}
}
k=k+1;
}
}
void main()
{
int x[MAX];
rchart("chart.txt",n);//view(mt[0].D); //ma tran trong so
create("weightchart.txt",n);//view(mt[0].Q);//ma tran duong di
//cout<<MAX;
Floy();
for(int i=0;i<=n;i++)
{
cout<<"D["<<i<<"]:"<<endl<<endl;
view(mt[i].D);
cout<<"Q["<<i<<"]:"<<endl<<endl;
view(mt[i].Q);
}
}
Project:
File" Floy.cpp" chứa CODE trên
File "Chart.txt" chứa ma trận
Còn một hàm nữa mình chưa haòn thành.Vì bây giờ chuyễn sang học C# và Java.Đợi Nắm vững làm quen với 2 ngôn ngữ này rồi mình làm nốt luôn:
Nó có 2 ưu điểm:
1.Hướng đối tượng,loại này viết sướng hơn cấu trúc.
2.Có hỗ trợ đồ họa mạnh mẽ,thích hợp cho việc tạo ra 1 phần mềm thân thiện với người sử dụng.
Hàm còn lại là Nhập vào 2 địa điểm: Đầu và Cuối,rồi chỉ ra đường đi ngắn nhất,từ 2 ma trận D và Q
