Lý thuyết đồ thị nghe có vẻ là một chủ đề trừu tượng và đáng sợ đối với bạn, vậy tại sao bạn nên dành thời gian đọc một bài báo về nó? Tuy nhiên, mặc dù nghe có vẻ không áp dụng được lắm, nhưng thực tế có rất nhiều ứng dụng hữu ích và quan trọng của lý thuyết đồ thị! Trong bài viết này, tôi sẽ cố gắng giải thích ngắn gọn một số ứng dụng này là gì. Khi làm như vậy, tôi sẽ cố gắng hết sức để thuyết phục bạn rằng việc có ít nhất một số kiến thức cơ bản về chủ đề này có thể hữu ích trong việc giải quyết một số vấn đề thú vị mà bạn có thể gặp phải.
Đang xem: Lý thuyết Đồ thị là gì và tại sao bạn nên quan tâm? lý thuyết Đồ thị
Trong bài viết này, tôi sẽ thông qua một ví dụ cụ thể cho thấy cách một nhiệm vụ lập kế hoạch / tối ưu hóa tuyến đường có thể được hình thành và giải quyết bằng cách sử dụng lý thuyết đồ thị. Cụ thể hơn, tôi sẽ xem xét một nhà kho lớn bao gồm 1000 mặt hàng khác nhau ở nhiều địa điểm / điểm nhận hàng khác nhau. Thách thức ở đây là, được đưa ra một danh sách các mặt hàng, bạn nên đi theo con đường nào qua nhà kho để lấy tất cả các mặt hàng, nhưng đồng thời giảm thiểu tổng quãng đường di chuyển? Đối với những bạn đã quen thuộc với những vấn đề kiểu này, điều này khá giống với vấn đề người bán hàng lưu động nổi tiếng . (Một vấn đề nổi tiếng trong tối ưu hóa tổ hợp , quan trọng trong khoa học máy tính lý thuyết và nghiên cứu hoạt động ).
Như bạn có thể đã nhận ra, mục tiêu của bài viết này không phải là giới thiệu toàn diện về lý thuyết đồ thị (đây sẽ là một nhiệm vụ khá to lớn). Thông qua một ví dụ trong thế giới thực, tôi sẽ cố gắng thuyết phục bạn rằng biết ít nhất một số điều cơ bản về lý thuyết đồ thị có thể chứng minh là rất hữu ích!
Tôi sẽ bắt đầu với phần giới thiệu lịch sử ngắn gọn về lĩnh vực lý thuyết đồ thị, đồng thời nêu bật tầm quan trọng và phạm vi ứng dụng hữu ích rộng rãi trong nhiều lĩnh vực rộng lớn khác nhau. Sau phần giới thiệu tổng quát hơn này, sau đó tôi sẽ chuyển trọng tâm sang ví dụ tối ưu hóa kho được thảo luận ở trên.
Lịch sử của lý thuyết đồ thị
Ý tưởng cơ bản về đồ thị lần đầu tiên được đưa ra vào thế kỷ 18 bởi nhà toán học Thụy Sĩ Leonhard Euler , một trong những nhà toán học lỗi lạc nhất của thế kỷ 18 (thực sự là mọi thời đại). Công trình của ông về ” Bảy cây cầu của bài toán Königsberg “, thường được trích dẫn là nguồn gốc của lý thuyết đồ thị .
Thành phố Königsberg ở Phổ (nay là Kaliningrad, Nga) nằm ở hai bên sông Pregel, và bao gồm hai hòn đảo lớn – Kneiphof và Lomse – được kết nối với nhau, hoặc với hai phần đất liền của thành phố, bởi bảy cây cầu (như minh họa trong hình dưới đây bên trái). Vấn đề là nghĩ ra một chuyến đi bộ xuyên thành phố sẽ băng qua mỗi cây cầu đó một lần và chỉ một lần.
Euler, nhận ra rằng các ràng buộc liên quan là bốn phần đất và bảy cây cầu, đã vẽ ra hình ảnh trực quan đầu tiên được biết đến của một biểu đồ hiện đại. Một biểu đồ hiện đại, như được thấy trong hình dưới cùng bên phải, được biểu thị bằng một tập hợp các điểm, được gọi là v ertices hoặc nút, được nối với nhau bởi một tập hợp các đường được gọi là các cạnh.
Tín dụng: Wikipedia
Sự trừu tượng hóa này từ một vấn đề cụ thể liên quan đến một thành phố và những cây cầu, v.v. đến một biểu đồ làm cho bài toán có thể xử lý được về mặt toán học, vì biểu diễn trừu tượng này chỉ bao gồm thông tin quan trọng để giải quyết vấn đề. Euler thực sự đã chứng minh rằng vấn đề cụ thể này không có giải pháp. Tuy nhiên, khó khăn mà ông phải đối mặt là việc phát triển một kỹ thuật phân tích phù hợp , và các thử nghiệm tiếp theo đã thiết lập khẳng định này một cách nghiêm ngặt về mặt toán học. Kể từ đó, nhánh toán học được gọi là lý thuyết đồ thị nằm im trong nhiều thập kỷ. Tuy nhiên, trong thời hiện đại, các ứng dụng của nó cuối cùng cũng bùng nổ.
Giới thiệu về lý thuyết đồ thị
Như đã đề cập trước đây, tôi không có mục đích giới thiệu toàn diện về lý thuyết đồ thị. Phần sau vẫn chứa một số điều cơ bản khi nói đến các loại biểu đồ khác nhau, v.v., có liên quan đến ví dụ mà chúng ta sẽ thảo luận sau về tối ưu hóa đường dẫn.
Lý thuyết Đồ thị cuối cùng là nghiên cứu các mối quan hệ . Với một tập hợp các nút & kết nối, có thể tóm tắt mọi thứ từ bố cục thành phố đến dữ liệu máy tính, lý thuyết đồ thị cung cấp một công cụ hữu ích để định lượng và đơn giản hóa nhiều phần chuyển động của hệ thống động. Nghiên cứu đồ thị thông qua một khuôn khổ cung cấp câu trả lời cho nhiều vấn đề sắp xếp, kết nối mạng, tối ưu hóa, đối sánh và vận hành.
Đồ thị có thể được sử dụng để mô hình hóa nhiều loại quan hệ và quá trình trong các hệ thống vật lý, sinh học, xã hội và thông tin, và có nhiều ứng dụng hữu ích như vd.
Tìm kiếm cộng đồng trong mạng, chẳng hạn như mạng xã hội (đề xuất kết bạn / kết nối) hoặc trong những ngày gần đây để biết COVID19 có thể lây lan trong cộng đồng thông qua địa chỉ liên hệ. Xếp hạng / sắp xếp các siêu liên kết trong công cụ tìm kiếm. Bản đồ GPS / Google để tìm đường ngắn nhất về nhà. Nghiên cứu các phân tử và nguyên tử trong hóa học. xét nghiệm DNA Bảo mật mạng máy tính ….. và nhiều thứ khác nữa….
Một ví dụ đơn giản về biểu đồ có 6 nút
Một mạng xã hội phức tạp hơn một chút. Tín dụng: Martin Grandjean Wikimedia
Các loại đồ thị
Có nhiều loại biểu diễn đồ thị khác nhau và chúng tôi phải đảm bảo rằng chúng tôi hiểu loại biểu đồ mà chúng tôi đang làm việc khi giải quyết một vấn đề có lập trình bao gồm biểu đồ.
Đồ thị vô hướng
Trong biểu đồ trên, mỗi nút có thể đại diện cho các thành phố khác nhau và các cạnh hiển thị đường hai chiều.
Đồ thị có hướng (DiGraphs)
Tín dụng: WIkiMedia
Giống như ví dụ trước, nếu chúng ta coi các nút là thành phố, chúng ta có hướng từ thành phố 1 đến thành phố 2. Điều đó có nghĩa là, bạn có thể lái xe từ thành phố 1 đến thành phố 2 nhưng không quay lại thành phố 1, vì không có hướng quay lại thành phố 1 từ 2. Nhưng nếu chúng ta xem xét kỹ đồ thị, chúng ta có thể thấy các thành phố có hai hướng. Ví dụ, thành phố 3 và 4 có hướng về cả hai phía.
Đồ thị có trọng số
Đồ thị có trọng số có thể là đồ thị có hướng hoặc đồ thị vô hướng. Biểu đồ chúng ta có trong ví dụ này là một đồ thị có trọng số vô hướng. Chi phí (hoặc khoảng cách) từ xanh đến nút màu cam (và ngược lại) là 3. Giống như ví dụ trước của chúng tôi, nếu bạn muốn đi lại giữa hai thành phố, nói rằng thành phố xanh và màu cam, chúng ta sẽ phải lái xe 3 dặm. Các chỉ số này được tự xác định và có thể thay đổi tùy theo tình huống. Đối với một ví dụ chi tiết hơn, hãy xem xét bạn phải đi đến thành phố màu hồng từ màu xanh lá cây. Nếu bạn nhìn vào biểu đồ thành phố, chúng tôi không thể tìm thấy bất kỳ đường hoặc cạnh trực tiếp nào giữa hai thành phố. Vì vậy, những gì chúng ta có thể làm là đi du lịch qua một thành phố khác. Các tuyến đường hứa hẹn nhất sẽ bắt đầu từ xanh lá cây sang hồng, cam và xanh lam. Nếu trọng số là chi phí giữa các thành phố, chúng tôi sẽ phải chi 11 đô la để đi qua màu xanh lam để đến màu hồng nhưng nếu chúng tôi đi tuyến đường khác qua màu cam, chúng tôi sẽ chỉ phải trả 10 đô la cho chuyến đi.
Có thể có một số trọng số liên quan đến mỗi cạnh, bao gồm khoảng cách, thời gian di chuyển hoặc chi phí tiền tệ. Các đồ thị có trọng số như vậy thường được sử dụng để lập trình GPS và các công cụ tìm kiếm lập kế hoạch du lịch để so sánh thời gian và chi phí chuyến bay.
Lý thuyết đồ thị → Tối ưu hóa tuyến đường
Sau khi (hy vọng) thuyết phục bạn rằng lý thuyết đồ thị rất đáng để biết về điều gì đó, bây giờ đã đến lúc tập trung vào trường hợp ví dụ về lập kế hoạch tuyến đường khi chọn hàng trong kho của chúng tôi.
Thử thách:
Thách thức ở đây là với một “danh sách đón khách” làm đầu vào, chúng ta phải tìm ra con đường ngắn nhất đi qua tất cả các điểm đón, nhưng cũng phải tuân thủ các hạn chế về nơi có thể / được phép lái xe. Các giả định và ràng buộc ở đây là việc băng qua giữa các hành lang trong nhà kho chỉ được phép ở những “điểm ngoặt” được đánh dấu. Ngoài ra, hướng di chuyển phải tuân theo hướng lái xe hợp pháp quy định cho từng hành lang.
Xem thêm: To Take Offence Là Gì, Nghĩa Của Từ To Take Offence (At Sth)
Giải pháp:
Bài toán này có thể được hình thành như một bài toán tối ưu hóa trong lý thuyết đồ thị. Tất cả các điểm lấy hàng trong nhà kho tạo thành một “nút” trong biểu đồ, nơi các cạnh thể hiện các làn / hành lang được phép và khoảng cách giữa các nút. Để giới thiệu vấn đề một cách chính thức hơn, chúng ta hãy bắt đầu từ một ví dụ đơn giản.
Biểu đồ bên dưới thể hiện 2 hành lang với 5 kệ / điểm nhận hàng trên mỗi hành lang. Tất cả các giá ở đây được biểu diễn dưới dạng một nút trong biểu đồ, với địa chỉ nằm trong khoảng từ 1–10. Các mũi tên chỉ hướng lái xe được phép, trong đó các mũi tên đôi cho biết bạn có thể lái xe theo một trong hai cách. Đủ đơn giản, phải không?
Có thể biểu diễn các tuyến đường lái xe được phép dưới dạng biểu đồ, có nghĩa là chúng ta có thể sử dụng các kỹ thuật toán học được biết đến từ lý thuyết đồ thị để tìm “tuyến đường lái xe” tối ưu giữa các nút (tức là các kệ hàng trong kho của chúng tôi).
Đồ thị ví dụ trên có thể được mô tả toán học thông qua một « ma trận kề ». Do đó, ma trận kề bên phải trong hình dưới đây là đại diện cho «biểu đồ kho» của chúng tôi, biểu thị tất cả các tuyến đường được phép lái xe giữa các nút khác nhau.
Ví dụ 1: Bạn được phép đi từ nút 2 → 3, nhưng không được phép đi từ nút 3 → 2. Điều này được biểu thị bằng “1” trong ma trận kề bên phải. Ví dụ 2: Bạn được phép đi từ cả hai nút 8 → 3 và từ 3 → 8, một lần nữa được chỉ ra bởi các “1” `trong ma trận kề (trong trường hợp này là đối xứng khi nói đến hướng di chuyển).
Một nhà kho thực sự tất nhiên lớn hơn và phức tạp hơn ví dụ trên. Tuy nhiên, các nguyên tắc chính của cách biểu diễn bài toán qua đồ thị vẫn được giữ nguyên. Để làm cho vấn đề thực sự đơn giản hơn một chút (và phù hợp trực quan hơn cho bài viết này), tôi đã giảm tổng số kệ / điểm nhận hàng (khoảng 50 kệ thứ 50 được bao gồm, được đánh dấu bằng các ô vuông màu đen trong hình bên dưới). Tất cả các điểm đón đều có địa chỉ (“số nút”) từ 1–74. Các ràng buộc liên quan khác đã được đề cập trước đó, chẳng hạn như hướng dẫn lái xe được phép trong mỗi hành lang, cũng như “điểm quay đầu” được phép và lối tắt giữa các hành lang cũng được chỉ ra trong hình ..
Bước tiếp theo là biểu diễn đồ thị này dưới dạng ma trận kề. Vì chúng tôi ở đây quan tâm đến việc tìm cả tuyến đường tối ưu và tổng khoảng cách, chúng tôi cũng phải bao gồm khoảng cách lái xe giữa các nút khác nhau trong ma trận.
Ma trận này chỉ ra tất cả các ràng buộc liên quan đến cả hướng di chuyển được phép, “lối tắt” nào được phép, bất kỳ hạn chế nào khác cũng như khoảng cách lái xe giữa các nút (được minh họa qua màu). Ví dụ, “lối tắt” giữa các nút 21 và 41 được hiển thị trong biểu diễn đồ thị cũng có thể được xác định rõ ràng trong ma trận kề. Các “vùng trắng” của ma trận đại diện cho các đường dẫn không được phép, được chỉ ra thông qua khoảng cách “vô hạn” giữa các nút đó.
Từ biểu diễn đồ thị đến tối ưu hóa đường dẫn
Chỉ có một biểu diễn trừu tượng của kho hàng của chúng tôi dưới dạng một biểu đồ, tất nhiên không giải quyết được vấn đề thực tế của chúng tôi. Ý tưởng là thông qua biểu diễn đồ thị này, bây giờ chúng ta có thể sử dụng khung toán học và các thuật toán từ lý thuyết đồ thị để giải quyết nó!
Vì tối ưu hóa đồ thị là một lĩnh vực nổi tiếng trong toán học, nên có một số phương pháp và thuật toán có thể giải quyết loại vấn đề này. Trong trường hợp ví dụ này, tôi đã dựa trên giải pháp dựa trên “ thuật toán Floyd-Warshall ”, một thuật toán nổi tiếng để tìm đường đi ngắn nhất trong đồ thị có trọng số . Một lần thực thi thuật toán sẽ tìm độ dài (trọng số tổng) của các đường đi ngắn nhất giữa tất cả các cặp nút. Mặc dù nó không trả về chi tiết của chính các đường dẫn, nhưng có thể tái tạo lại các đường dẫn với các sửa đổi đơn giản đối với thuật toán.
Nếu bạn cung cấp thuật toán này làm đầu vào “danh sách đơn hàng chọn”, nơi bạn xem qua danh sách các mặt hàng bạn muốn chọn, thì bạn sẽ có thể có được tuyến đường tối ưu để giảm thiểu tổng quãng đường lái xe để thu thập tất cả các mặt hàng trong danh sách.
Ví dụ: Chúng ta hãy bắt đầu bằng cách hình dung kết quả cho một danh sách chọn (ngắn) như sau: Bắt đầu từ nút «0», chọn các mặt hàng tại vị trí / nút 15, 45, 58 và 73 (nơi các vị trí này được minh họa trong hình bên dưới ). Thuật toán tìm ra tuyến đường ngắn nhất cho phép giữa các điểm này thông qua tính toán “ma trận khoảng cách”, D , sau đó có thể được sử dụng để xác định tổng khoảng cách lái xe giữa tất cả các vị trí / nút trong danh sách chọn hàng.
Bước 1: D <0> <15> → 90 m Bước 2: D <15> <45> → 52 m Bước 3: D <45> <58> → 34 m Bước 4: D <58> <73> → 92 m
Đã thử nghiệm một số “danh sách chọn” làm đầu vào và xác minh các tuyến đường lái xe được đề xuất và khoảng cách được tính toán, thuật toán đã có thể tìm ra tuyến đường tối ưu trong mọi trường hợp. Thuật toán tôn trọng tất cả các ràng buộc áp đặt, chẳng hạn như hướng di chuyển được phép và sử dụng tất cả các “lối tắt” được phép để giảm thiểu tổng khoảng cách.
Từ tối ưu hóa đường dẫn đến thông tin chi tiết hữu ích
Như thể hiện qua ví dụ trên, chúng tôi đã phát triển một thuật toán tối ưu hóa để tính toán tuyến đường lái xe tối ưu qua tất cả các điểm trên danh sách đơn hàng lấy hàng (đối với phiên bản đơn giản hóa của kho hàng). Bằng cách cung cấp danh sách các đơn hàng chọn làm đầu vào, do đó, người ta có thể tương đối dễ dàng tính toán số liệu thống kê về số dặm điển hình cho mỗi. chọn hàng. Sau đó, những thống kê này cũng có thể được lọc trên nhiều thông tin khác nhau như loại mặt hàng, khách hàng, ngày tháng, v.v. Trong phần sau, tôi đã chọn một vài ví dụ về cách người ta có thể trích xuất các thống kê thú vị từ một công cụ tối ưu hóa đường dẫn như vậy.
Khi làm điều này, đầu tiên tôi tạo 10.000 danh sách đơn hàng lấy hàng trong đó số lượng mặt hàng trên mỗi danh sách dao động từ 1–30 mặt hàng, được đặt tại các điểm lấy hàng ngẫu nhiên trong nhà kho (địa chỉ 3–74 trong hình trên). Bằng cách thực hiện quy trình tối ưu hóa đường dẫn trên tất cả danh sách chọn này, sau đó chúng tôi có thể trích xuất một số thống kê thú vị.
Ví dụ 1: Tính số dặm dưới dạng một hàm của số đơn vị trên mỗi. chọn danh sách đơn hàng. Ở đây, bạn sẽ tự nhiên cho rằng tổng số dặm tăng lên khi bạn phải chọn nhiều đồ hơn. Tuy nhiên, ở một mức độ nào đó, điều này sẽ bắt đầu giảm dần. Điều này là do thực tế là cuối cùng người ta phải dừng lại tất cả các hành lang trong nhà kho để lấy hàng, điều này khiến chúng tôi không thể sử dụng các “lối tắt” thông minh để giảm thiểu tổng quãng đường lái xe. Xu hướng này có thể được minh họa trong hình bên dưới bên trái, minh họa rằng với khoảng hơn 15–20 đơn vị cho mỗi đơn hàng lấy hàng, việc bổ sung thêm các mặt hàng không làm cho tổng số dặm dài hơn (vì bạn phải lái xe qua tất cả các hành lang của nhà kho). Lưu ý rằng các số liệu cho thấy “biểu đồ mật độ” của sự phân bố số dặm điển hình trên mỗi. chọn danh sách đơn hàng
Một thống kê thú vị khác, cho thấy xu hướng tương tự, là phân bổ quãng đường lái xe cho mỗi mục đã chọn trong hình bên phải. Ở đây, chúng tôi thấy rằng đối với danh sách chọn có ít mục, số dặm điển hình cho mỗi. vật phẩm tương đối cao (với một phương sai lớn, tùy thuộc vào mức độ “may mắn” của chúng ta với một số vật phẩm nằm trong cùng một hành lang, v.v.). Tuy nhiên, để chọn danh sách có một số mục, số dặm mỗi. mục đang giảm dần. Do đó, loại thống kê này có thể thú vị khi điều tra kỹ hơn, để tối ưu hóa số lượng mặt hàng mà mỗi danh sách đơn hàng chọn nên chứa để giảm thiểu số dặm cho mỗi mặt hàng đã chọn.
Ví dụ 2: Ở đây tôi đã sử dụng dữ liệu trong thế giới thực cũng chứa thông tin bổ sung dưới dạng ID khách hàng (ở đây chỉ hiển thị cho hai khách hàng). Sau đó, chúng ta có thể xem xét kỹ hơn sự phân bổ theo số dặm mỗi. chọn danh sách đơn hàng cho hai khách hàng. Ví dụ, bạn thường phải lái xe quãng đường dài hơn để chọn hàng của một khách hàng này so với một khách hàng khác? Và, bạn có nên tính thêm chi phí này cho khách hàng đó không?
Hình bên dưới bên trái cho thấy sự phân bổ theo số dặm cho «Khách hàng 1» và «Khách hàng 2». Một trong những điều chúng tôi có thể hiểu từ điều này là đối với khách hàng 2, hầu hết các danh sách đơn hàng lấy hàng đều có khoảng cách lái xe ngắn hơn đáng kể so với khách hàng 1. Điều này cũng có thể được hiển thị bằng cách tính số dặm trung bình cho mỗi. chọn danh sách đơn hàng cho hai khách hàng (hình bên phải).
Ví dụ, loại thông tin này có thể được sử dụng để triển khai các mô hình định giá trong đó giá sản phẩm cho khách hàng cũng dựa trên số dặm mỗi đơn hàng. Đối với những khách hàng mà đơn đặt hàng liên quan đến việc lái xe nhiều hơn (và do đó cũng tốn nhiều thời gian hơn và chi phí cao hơn), bạn có thể cân nhắc lập hóa đơn thêm so với các đơn đặt hàng liên quan đến quãng đường lái xe ngắn.
Xem thêm: Hợp Đồng Tổng Thầu Chìa Khóa Trao Tay Là Gì ? Hợp Đồng Chìa Khóa Trao Tay Là Gì
Tóm lược:
Cuối cùng, tôi hy vọng tôi đã thuyết phục được bạn rằng lý thuyết đồ thị không chỉ là một số khái niệm toán học trừu tượng, mà nó thực sự có rất nhiều ứng dụng hữu ích và thú vị! Hy vọng rằng các ví dụ trên sẽ hữu ích cho một số bạn trong việc giải các bài toán tương tự sau này, hoặc ít nhất là thỏa mãn trí tò mò của các bạn khi nói đến lý thuyết đồ thị và một số ứng dụng của nó.
Các trường hợp được thảo luận trong bài viết chỉ bao gồm một số ví dụ minh họa một số khả năng tồn tại. Nếu bạn đã từng có kinh nghiệm và ý tưởng về chủ đề này, sẽ rất thú vị khi nghe suy nghĩ của bạn trong phần bình luận bên dưới!
Bạn có thấy bài báo này thú vị không? Nếu vậy, bạn cũng có thể thích một số bài viết khác của tôi về các chủ đề như AI, Machine Learning, vật lý, v.v., bạn có thể tìm thấy những bài viết này trong các liên kết bên dưới và trên tiểu sử tác giả phương tiện của tôi: https:///