Bài toán quãng đường ngắn nhất phương pháp tối ưu

Mới nhất Xem nhiều International

Giáo dụcTin tức

{{#is_first}}

{{#thumbnail_url}} {{/thumbnail_url}}

{{/is_first}} {{^is_first}}

{{/is_first}}

Bạn hãy thử giúp ông Tuấn tìm quãng đường ngắn nhất để rào kín khu vườn hình chữ nhật. 

Đề bài:

Nhà ông Tuấn có một mảnh vườn là hình chữ nhật ABCD với kích thước như hình vẽ. Ông Tuấn muốn rào kín khu vườn gồm các đường bao quanh và hai đường chéo của hình chữ nhật ABCD.

Hỏi nếu bắt đầu đi từ điểm A để rào xong khu vườn theo yêu cầu trên rồi kết thúc tại điểm A thì ông Tuấn phải đi quãng đường ngắn nhất là bao nhiêu mét?

Quảng cáo

Tag

Mục Lục

• 1. Thuật toán SHORTEST PATH là gì?
• 2. Ý tưởng và Mô tả thuật toán Dijkstra để tìm đường đi ngắn nhất
• 3. Triển khai thuật toán tìm đường đi ngắn nhất trong Java

Trong thế giới thực, có rất nhiều bài toán được mô phỏng và giải bằng các chương trình máy tính. Và một trong những bài toán phổ biến mà bất kỳ lập trình viên nào cũng phải học đó là: Tìm đường đi ngắn nhất [Shortest path].

1. Thuật toán SHORTEST PATH là gì?

Thuật toán Shortest Path - Tìm đường đi ngắn nhất

Nhắc đến giải thuật duyệt đồ thị, chắc ai học công nghệ thông tin cũng biết đến 2 thuật toán cơ bản: Depth-First Search [DFS] , Breadth-First Search [BFS].

Về mặt ý nghĩa, cả 2 thuật toán đều thực hiện trên đồ thị không có trọng số.

Thuật toán DFS cho ta tìm đường đi đến đỉnh ta muốn [có thể chưa ngắn nhất].

Còn thuật toán BFS cũng tìm đường đi đến đỉnh ta muốn nhưng là đường ngắn nhất có thể.

Trong đồ thị có trọng số, vấn đề sẽ khó hơn, nó nảy sinh ra 1 bài toán, đó là bài toán tìm đường đi ngắn nhất giữa 2 đỉnh.

Nó là bài toán rất quen thuộc với những người bắt đầu học Graph.

Để giải quyết bài toán này, đến giờ có nhiều thuật toán và các biến thể. Trong bài viết này mình sẽ chắc lọc và lựa chọn sử dụng Moore – Dijkstra.

Thuật toán Dijkstra cho phép tìm đường đi ngắn nhất từ một đỉnh s đến các đỉnh còn lại của đồ thị và chiều dài [trọng số] tương ứng.

Phương pháp của thuật toán là xác định tuần tự đỉnh có chiều dài đến s theo thứ tự tăng dần.

Thuật toán được xây dựng trên cơ sở gán cho mỗi đỉnh các nhãn tạm thời.

Nhãn tạm thời của các đỉnh cho biết cận trên của chiều dài đường đi ngắn nhất từ s đến đỉnh đó.

Nhãn của các đỉnh sẽ biến đổi trong các bước lặp, mà ở mỗi bước lặp sẽ có một nhãn tạm thời trở thành chính thức.

Nếu nhãn của một đỉnh nào đó trở thành chính thức thì đó cũng chính là chiều dài ngắn nhất của đường đi từ s đến đỉnh đó.

2. Ý tưởng và Mô tả thuật toán Dijkstra để tìm đường đi ngắn nhất

Trong phần này, chúng ta sẽ phân tích từng bước Thuật toán Dijkstra. Ở đây ta sẽ sử dụng đồ thị bên dưới để làm ví dụ để giúp bạn hiểu rõ hơn về thuật toán này.

Như bạn đã biết, thuật toán của Dijkstra là một thuật toán Greedy[Thuật toán tham lam]

Điều này có nghĩa là chúng ta sẽ đi một con đường ngắn hơn từ đỉnh này đến đỉnh kia. Thuật toán hoàn tất khi chúng ta truy cập tất cả các đỉnh của đồ thị.

Tuy nhiên, hãy cẩn thận - đôi khi khi chúng ta tìm thấy một đỉnh mới, có thể có các đường đi ngắn hơn qua nó từ một đỉnh đã truy cập đến một đỉnh đã được truy cập khác.

Chúng ta có thể xem bên dưới các bước để hoàn thành thuật toán Dijkstra.

Chúng ta có thể bắt đầu với nút A và chúng ta có 2 con đường.

• Đầu tiên là từ A đến B với độ dài 5

• Và từ A đến C với độ dài 3.

Vì vậy, chúng ta có thể viết trong danh sách kế bên với các đỉnh đã truy cập là 2 đỉnh mới [B, C] và trọng số để đến đó.

Sau đó, như đã nói trước đó - chúng ta sẽ chọn con đường từ A ->C.

Khi truy cập vào đỉnh C, chúng ta có thể thấy rằng có 3 đường đi khác nhau:

• Con đường đầu tiên là C đến B

• Con đường thứ hai là C đến D

• Con đường thứ ba là C đến E

Vì vậy, hãy ghi vào danh sách hai đỉnh mới và chọn con đường ngắn nhất là C đến B.

Bây giờ tại B, chúng ta có 3 đường:

• B đến D

• B đến E

• Và B quay lại C

Chúng ta chọn con đường ngắn nhất là B đến D và chúng ta cập nhật vào danh sách trọng số mới của các đường đi từ A đến các đỉnh khác.

Bây giờ như chúng ta có thể thấy không có đường đi mới nào từ D đến E.

Trong trường hợp đó, chúng ta quay lại đỉnh trước đó để kiểm tra đường đi ngắn nhất.

Bây giờ có một đường với độ dài 4 đi đến E và một đường đi đến C.

Trong trường hợp này, chúng ta chọn bất kỳ đường nào chúng ta thích.

Cuối cùng, chúng ta có thể thấy rằng bất kỳ phương án nào chúng ta đi trên đường từ A đến E đều có trọng số như nhau vì các đường đi ngắn nhất được ghi trong danh sách.

Cuối cùng, chúng ta có thể thấy tất cả các đường đi mà chúng ta đã sử dụng.

3. Triển khai thuật toán tìm đường đi ngắn nhất trong Java

Để triển khai thuật toán tìm đường đi ngắn nhất Dijkstra, trước hết - chúng ta phải tạo các cạnh và đỉnh của biểu đồ:

FileVert.java

packagedijkstra.algo;

importjava.util.ArrayList;

importjava.util.List;

publicclassVertimplementsComparable{

privatebooleanvisited;

privateStringname;

privateListList;

privatedoubledist=Double.MAX_VALUE;

privateVertpr;

publicVert[Stringname]{

this.name=name;

this.List=newArrayList[];

}

publicListgetList[]{

returnList;

}

publicStringgetName[]{

returnname;

}

publicvoidsetName[Stringname]{

this.name=name;

}

publicvoidsetList[ListList]{

this.List=List;

}

publicvoidaddNeighbour[Edgeedge]{

this.List.add[edge];

}

publicbooleanVisited[]{

returnvisited;

}

publicvoidsetVisited[booleanvisited]{

this.visited=visited;

}

publicVertgetPr[]{

returnpr;

}

publicvoidsetPr[Vertpr]{

this.pr=pr;

}

publicdoublegetDist[]{

returndist;

}

publicvoidsetDist[doubledist]{

this.dist=dist;

}

@Override

publicStringtoString[]{

returnthis.name;

}

@Override

publicintcompareTo[VertotherV]{

returnDouble.compare[this.dist,otherV.getDist[]];

}

}

File Edge.java

packagedijkstra.algo;

publicclassEdge{

privatedoubleweight;

privateVertstartVert;

privateVerttargetVert;

publicEdge[doubleweight,VertstartVert,VerttargetVert]{

this.weight=weight;

this.startVert=startVert;

this.targetVert=targetVert;

}

publicdoublegetWeight[]{

returnweight;

}

publicvoidsetWeight[doubleweight]{

this.weight=weight;

}

publicVertgetStartVert[]{

returnstartVert;

}

publicvoidsetStartVert[VertstartVert]{

this.startVert=startVert;

}

publicVertgetTargetVert[]{

returntargetVert;

}

publicvoidsetTargetVert[VerttargetVert]{

this.targetVert=targetVert;

}

}

FilePathFinder.java

packagedijkstra.algo;

importjava.util.ArrayList;

importjava.util.Collections;

importjava.util.List;

importjava.util.PriorityQueue;

publicclassPathFinder{

publicvoidShortestP[VertsourceV]{

sourceV.setDist[0];

PriorityQueuepriorityQueue=newPriorityQueue[];

priorityQueue.add[sourceV];

sourceV.setVisited[true];

while[!priorityQueue.isEmpty[]]{

VertactualVertex=priorityQueue.poll[];

for[Edgeedge:actualVertex.getList[]]{

Vertv=edge.getTargetVert[];

if[!v.Visited[]]{

doublenewDistance=actualVertex.getDist[]
+edge.getWeight[];

if[newDistance Đừng quên, nếu bạn muốn chinh phục ngôn ngữ Java, đặc biệt là Java Web thì đừng bỏ qua KHÓA HỌC JAVA [Full Stack] của NIIT - ICT Hà Nội nhé.

> Hoặc, nếu bạn chưa có nền tảng về lập trình mà muốn học đầy đủ hơn thì KHÓA HỌC LẬP TRÌNH VIÊN FULL STACK sẽ giúp bạn trở thành lập trình viên vững vàng trong vòng 12 tháng.

---

HỌC VIỆN ĐÀO TẠO CNTT NIIT - ICT HÀ NỘI

Học Lập trình chất lượng cao [Since 2002]. Học làm Lập trình viên. Hành động ngay!

Đc: Tầng 3, 25T2, N05, Nguyễn Thị Thập, Cầu Giấy, Hà Nội

SĐT: 02435574074 - 0914939543

Email:

Website://niithanoi.edu.vn

Fanpage: //facebook.com/NIIT.ICT/

#niit #niithanoi #niiticthanoi #hoclaptrinh #khoahoclaptrinh #hoclaptrinhjava #hoclaptrinhphp #java #php #python