Tìm hiểu các giải thuật tìm đường đi ngắn nhất bằng lý thuyết và thực tế, rồi mô phỏng trên môi trường đồ họa của windows
MỞ ĐẦU
Trong thực tế ta thường sữ dụng đến mạng lưới điện thoại, giao thông (đặc biệt là đường hàng không), mạng máy tính . Chúng giữ một vị trí rất quan trọng trong cuộc sống. Việc nghiên cứu và phát triễn kỹ thuật luôn được chú trọng, nhằm giải quyết các công việctrong những lĩnh vực này một cách linh hoạt, ví dụ như giãm chi phí it1 tốn kém thời gianvà còn nhiều hiệu quả. Để giải quyết những tổn hao đó, việc nghiên cứu phải dựa trên ngành toán học đó là lý thuyết đồ thị (GRAPH THEORY ) hay nói một cách chung lý thuyết đồ thị là một công cụ toán học xây dựng mô hình cho các vấn đề trên.
Như ta đả biết một mạng điện thoại, mạng máy tính hay một mạng thông tin nói chung thường có một cấu trúc chung đó là các điểm liên hệ với nhau. Để mô hình sự liên hệ này, trong toán học lý thuyết đồ thị sẽ biễu diển bởi một đồ thị, trong đó đỉnh của đồ thị là điểm thông tin, cạnh của đồ thị là sự liên hệ củaác điểm thông tin, số được gán trên cạnh của đồ thị và biễu diễn khoãng cách hay chi phí các nút thông tin.
Để hiểu được các qui tắc giãm được thời gian và chi phí trên các ứng dụng thực tế cũng như lý thuyết thì đề tài này là “tìm hiểu các giải thuật tìm đườngđi ngắn nhất bằng lý thuyết và thực tế, rồi mô phõng trên môi trường đồ họa của windows”.
Nội dung đưa ra những giải thuật tìm đường đi ngắn nhất giữa hai đỉnh nguồn (X) và đỉnh đích (Y) nào đó và dùng các giải thuật đó để mô phõng trên môi trường đồ họa windows.
Bài toán tìm đường đi ngắn nhất là một bài toán lớn và được ứng dụng trong nhiều lĩnh vực, đặc biệt là tìm đường đi trong hệ thống giao thông. Đã có nhiều giải thuật tuần tự cũng như song song được đưa ra để giải quyết vấn đề này. Bên cạnh đó còn có giải thuật tìm đường tĩnh và tìm đường động cũng được đưa ra giải quyết vấn đề này.
Bài toán tìm đường đi có nhiều dạng, chẳng hạn như tìm đường đi của đồ thị có hướng, vô hướng, trọng số của đồ thị có thể là khoảng cách giữa hai node hay chi phí để đi từ node này đến node kia.
Trong đề tài này em sử dụng phần mềm VISUALL C++, để hiện thực các giải thuật: Dijsktra, Bellman Ford, Shorttest Path Routing, Floyd. Để từ đó đánh giá xem việc tìm đường bằng lý thuyết được thực tiển không.
Đề tài này gồm hai phần:
PHẦN I:
Tìm hiểu các giải thuật tìm đường tỉnh .
PHẦN II:
Mô phỏng các giải thuật trên môi trừơng đồ hoạ windows.
4 trang |
Chia sẻ: lvcdongnoi | Lượt xem: 2755 | Lượt tải: 1
Bạn đang xem nội dung tài liệu Tìm hiểu các giải thuật tìm đường đi ngắn nhất bằng lý thuyết và thực tế, rồi mô phỏng trên môi trường đồ họa của windows, để tải tài liệu về máy bạn click vào nút DOWNLOAD ở trên
Chöông 1:
MÔÛ ÑAÀU
Trong thöïc teá ta thöôøng söõ duïng ñeán maïng löôùi ñieän thoaïi, giao thoâng (ñaëc bieät laø ñöôøng haøng khoâng), maïng maùy tính…. Chuùng giöõ moät vò trí raát quan troïng trong cuoäc soáng. Vieäc nghieân cöùu vaø phaùt trieãn kyõ thuaät luoân ñöôïc chuù troïng, nhaèm giaûi quyeát caùc coâng vieäctrong nhöõng lónh vöïc naøy moät caùch linh hoaït, ví duï nhö giaõm chi phí it1 toán keùm thôøi gianvaø coøn nhieàu hieäu quaû. Ñeå giaûi quyeát nhöõng toån hao ñoù, vieäc nghieân cöùu phaûi döïa treân ngaønh toaùn hoïc ñoù laø lyù thuyeát ñoà thò (GRAPH THEORY ) hay noùi moät caùch chung lyù thuyeát ñoà thò laø moät coâng cuï toaùn hoïc xaây döïng moâ hình cho caùc vaán ñeà treân.
Nhö ta ñaû bieát moät maïng ñieän thoaïi, maïng maùy tính hay moät maïng thoâng tin noùi chung thöôøng coù moät caáu truùc chung ñoù laø caùc ñieåm lieân heä vôùi nhau. Ñeå moâ hình söï lieân heä naøy, trong toaùn hoïc lyù thuyeát ñoà thò seõ bieãu dieån bôûi moät ñoà thò, trong ñoù ñænh cuûa ñoà thò laø ñieåm thoâng tin, caïnh cuûa ñoà thò laø söï lieân heä cuûaaùc ñieåm thoâng tin, soá ñöôïc gaùn treân caïnh cuûa ñoà thò vaø bieãu dieãn khoaõng caùch hay chi phí caùc nuùt thoâng tin.
Ñeå hieåu ñöôïc caùc qui taéc giaõm ñöôïc thôøi gian vaø chi phí treân caùc öùng duïng thöïc teá cuõng nhö lyù thuyeát thì ñeà taøi naøy laø “tìm hieåu caùc giaûi thuaät tìm ñöôøngñi ngaén nhaátbaèng lyù thuyeát vaø thöïc teá, roài moâ phoõng treân moâi tröôøng ñoà hoïa cuûa windows”.
Noäi dung ñöa ra nhöõng giaûi thuaät tìm ñöôøng ñi ngaén nhaát giöõa hai ñænh nguoàn (X) vaø ñænh ñích (Y) naøo ñoù vaø duøng caùc giaûi thuaät ñoù ñeå moâ phoõng treân moâi tröôøng ñoà hoïa windows.
I/ Giôùi thieäu veà GRAPH (ñoà thò) :
Ñònh nghóa :
Ñoà thò laø taäp hôïp caùc ñænh, caùc caïnh vaø söï lieân heä giöõa hai taäp hôïp naøy coù traät töï.
Kí hieäu ñoà thò G(V,E).
E: Taäp hôïp caùc caïnh.
V: Taäp hôïp caùc ñænh.
L: Laø quan heä giöõa E vaø V.
Ví duï:
Cho ñoà thò G(V,E,I) nhö sau:
V={A,B,C,D}
E={e,f,g,h}
I={(AeB), (AfD), (BhD), (BgC)}
Ñoà thò ñöôïc bieåu dieãn nhö sau:
C
A
D
e
f
h
g
phaân loaïi ñoà thò:
a/ Ñoà thò voâ höôùng vaø ñoà thò höõu höôùng:
Ñoà thò voâ höôùng : Khoâng phaân bieät caïnh noái töø ñænh A ñeán ñænh B vaø töø ñænh B ñeán ñænh A. Nghóa ñoä daøi chieàu AB baèng chieàu ngöôïc laïi BA.
Ví duï ñoà thò nhö hình veõ:
C
A
D
e
f
h
g
B
Ñoà thò höõu höôùng: Phaân bieät caïnh noái töø ñænh A ñeán ñænh B vaø töø ñænh B ñeán ñænh A laø khaùc nhau.
C
A
D
e
f
h
g
B
b/ Ñoà thò coù troïng soá:
Laø ñoà thò moãi caïnh ñöôïc gaùn moät soá.
c/ Ñoà thò ñaày ñuû:
Laø ñoà thò coù moïi caëp ñænh ñeàu coù ñuùng moät caïnh noái chuùng.
d/ Ñoà thò lieân thoâng:
Laø ñoà thò maø moïi caëp ñænh ñeàu coù ñöôøng noái.
e/ Ñöôøng ñi:
Ñöôøng ñi giöõa hai ñænh laø moät chuoãi caïnh noái tieáp nhau noái hai ñænh ñoù.
f/ Chu trình:
Laø moät ñöôøng ñi kheùp kín.
3. Caây:
caây laø ñoà thò lieân thoâng khoâng coù chu trình.
Moïi caëp ñænh trong caây coù duy nhaát moät ñöôøng noái.
Ñoà thò lieân thoâng coù v ñænh vaø coù v – 1 caïnh laø moät caây.
Caây phuû cuûa moät ñoà thò lieân thoâng laø ñoà thò con coù cuøng soá ñænh vôùi ñoà thò chöùa noù vaø laø moät caây.
Bieåu dieãn cuûa ñoà thò:
Cho ñoà thò G(V,E). Coù hai caùch bieåu dieãn ñoà thò trong boä nhôù tuøy theo ñoà thò ñaày hay thöa. Ñoù laø bieåu dieãn baèng ma traän vaø danh saùch.
a/ Danh saùch keà:
Danh saùch keà laø moät danh saùch lieân keát, moãi phaàn töû cuûa danh saùch keà laø moät danh saùch chöùa caùc ñænh maø noù noái tôùi. Caùch bieåu dieãn naøy thích hôïp vôùi ñoà thò thöa.
b/ Ma traän keà:
Goàm moät maûng caáp nxn. Chöùa taát caû caùc ñænh cuõng nhö chieàu daøi cuûa caùc caïnh. Caùch bieåu dieãn, moãi phaàn töû a[i,j]= TRUE (hoaëc 1) töùc coù caïnh noái töø i ñeán j ngöôïc laïi a[i,j] = FALSE (hoaëc 0) neáu khoâng coù caïnh noái töø i ñeán j. Caùch bieåu dieãn naøy thích hôïp cho ñoà thò ñaày.
B
C
A
D
e
f
h
g
Ví duï: cho ñoà thò.
Coù ma traän keà laø:
A B C D
A 0 1 0 1
B 1 0 1 1
C 0 1 0 0
D 1 1 0 0
Choïn caáu truùc döõ lieäu cho ñoà thò:
Töø vieäc phaân tích treân ta nhaän thaáy raèng baøi toaùn cho moät ñoà thò laø moät maïng maùy tính maø caùc ñænh cuûa ñoà thò trôû thaønh caùc maùy tính treân maïng, caùc caïnh treân ñoà thò trôû thaønh ñöôøng truyeàn noái giöõa caùc maùy tính treân maïng, caùc con soá ñöôïc gaùn treân ñoà thò trôû thaønh löu löôïng ñöôøng truyeàn giöõa caùc maùy tính trong maïng. Ngoøai ra ta cuõng thaáy raèng töø moät ñænh baát kyø noái tôùi caùc ñænh coøn laïi laø höõu haïn, soá ñöôøng noái raát ít. Nhöng vì trong ñeà taøi ta chæ moâ phoûng cho moät maïng baèng ñoà thò neân tuøy theo giaûi thuaät maø ta coù theå qui ñònh cho ñoà thò laø ñoà thò höõu höôùng hay voâ höôùng. Vaø ta choïn caáu truùc döõ lieäu cho ñoà thò laø ma traän keà vaø ma traän coù troïng soá.
tim hiieu giai thuath.rar
