Đến nội dung

Hình ảnh

Sử dụng bọt xà phòng để giải bài toán cây Steiner

- - - - -

  • Please log in to reply
Chủ đề này có 5 trả lời

#1
hoangtrong2305

hoangtrong2305

    Trảm phong minh chủ

  • Phó Quản lý Toán Ứng dụ
  • 861 Bài viết

Giả sử bạn là một nhà kiến trúc sư. Vào một ngày nọ, một công ty kinh doanh bất động sản đến nhờ bạn thiết kế đường đi cho khu nhà ở của họ. Khu nhà ở này gồm $4$ tòa nhà $A,B,C,D$ tọa lạc theo dạng hình vuông cạnh $1 \text{km}$ (tức $AB=BC=CD=DA=1 \text{km}$).

stei1_images_phocagallery_Hinh-hoc_thumb

Bên công ty muốn nhờ bạn thiết kế cho họ con đường ngắn nhất kết nối $4$ tòa nhà này lại nhằm thuận tiện cho việc di chuyển qua lại giữa các tòa nhà và tiết kiệm chi phí khi thi công. Theo bạn, bạn sẽ thiết kế như thế nào?

 

Hãy xem qua một số ý tưởng thiết kế con đường sau đây:

 

Thiết kế 1:

stei2_images_phocagallery_Hinh-hoc_thumb

 

Dễ thấy bản thiết kế này rất thuận tiện cho việc di chuyển qua lại giữa các tòa nhà. Tuy nhiên tổng chiều dài khi thi công lại quá lớn. Ta có $AB=BC=CD=DA=1 \text{km}$ và $ABCD$ là hình vuông, sử dụng định lý Pitagoras, ta dễ dàng tính được $$l_{1}=AB+BC+CD+DA+AC+DB=4+2\sqrt{2} \approx 6,82 \text{km}$$

 

Rõ ràng bản thiết kế này chưa tối ưu.

 

Thiết kế 2:

stei3_images_phocagallery_Hinh-hoc_thumb

 

Đây là 1 ý tưởng rất độc đáo. Do $ABCD$ hình vuông nên nó sẽ nội tiếp trong 1 đường tròn. Bản thiết kế này dù điều kiện di chuyển không thuận lợi bằng bản thiết kế 1 nhưng vẫn đảm bảo được tính kết nối cả $4$ tòa nhà.

 

Dễ tính được tổng chiều dài con đường là:

$$l_{2}=\pi \sqrt{2} \approx 4,44 \text{km}$$

Xét về độ dài ta thấy bản thiết kế này tối ưu hơn bản 1. Tuy nhiên, ta hãy xe tiếp 1 bản thiết kế khác.

 

Thiết kế 3:

stei4_images_phocagallery_Hinh-hoc_thumb

 

Thiết kế này chỉ khác bản 1 ở chỗ bỏ đi 2 đường chéo $AC$ và $BD$. Ta được tổng độ dài:

$$l_{3}=AB+BC+CD+DA=4 \text{km}$$

Thiết kế này tiết kiệm được $0,44 \text{km}$ đường so với bản số $2$.

 

Thiết kế 4:

stei5_images_phocagallery_Hinh-hoc_thumb

 

Bản thiết kế này khá giống với bản số $3$, khác một chỗ là nó bỏ đi đoạn $AB$, nhưng vẫn giữ được tính kết nối cả $4$ tòa nhà. Tổng độ dài:

$$l_{4}=AD+DC+CB=3 \text{km}$$

Thiết kế này tiết kiệm được đến $1 \text{km}$ so với bản số $3$

 

Có lẽ nhiều bạn đọc đã nghĩ rằng tổng đoạn đường ngắn nhất mà vẫn đảm bảo sự liên kết giữa 4 tòa nhà chính là đường chéo $AC$ và $BD$. Ta hãy xem bản thiết kế tiếp theo.

 

Thiết kế 5

stei6_images_phocagallery_Hinh-hoc_thumb

 

Ta có $AC=BD=\sqrt{2}$ nên ta được tổng độ dài các đoạn đường này là:

$$l_{5}=AC+BD=2\sqrt{2} \approx 2,82 \text{km}$$

 

Đây cũng chính là bản thiết kế có tổng chiều dài ngắn nhất (tính đến hiện tại) mà vẫn đảm bảo sự kết nối giữa $4$ tòa nhà. Tuy nhiên, đây vẫn chưa phải là bản thiết kế tối ưu.

 

Thật ra để tính chính xác giá trị nhỏ nhất của tổng độ dài ta cần đến vi tích phân hàm nhiều biến, khá khó cho những ai mới bắt đầu làm quen với khái niệm vi tích phân. Lúc này, ta sẽ sử dụng 1 công cụ thoạt nhìn chả liên quan gì mấy đến toán học, hoàn toàn mang tính tự nhiên. Trước khi sử dụng đến “công nghệ” này, ta cần 1 dụng cụ đặc biệt.

 

Dùng 2 miếng kính hình vuông bằng nhau. Lấy 1 tấm kính bất kỳ, ở mỗi góc vuông của tấm kính đó ta gắn 4 que tăm có độ dài bằng nhau, đầu còn lại của que tăm ta gắn vào miếng kính còn lại tạo thành khối vuông sao cho giống như hình dưới đây.

stei7_images_phocagallery_Hinh-hoc_thumbstei8_images_phocagallery_Hinh-hoc_thumb

 

4 que tăm tượng trưng cho 4 tòa nhà. “Công nghệ” mà ta sử dụng đó chính là 1 tô xà phòng mà thôi.

 

stei9_images_phocagallery_Hinh-hoc_thumb

 

Ta sẽ nhúng khối vuông này vào trong tô xà phòng đó, sau đó kéo lên. Khi đó, ta sẽ thu được những màng xà phòng bám trên các que tăm. Về mặt tự nhiên, các màng xà phòng sẽ tự giảm thiểu đi các năng lượng tự do. Hay nói cách khác, màng xà phòng sẽ tự tạo cho mình có được diện tích bề mặt nhỏ nhất (như bong bóng vậy). Vì vậy, nếu ta áp dụng tính chất vật lý này của màng xà phòng vô vấn đề toán học trên, ta sẽ thu được kết quả tối ưu nhất. Hãy thử nhé!


Bài viết đã được chỉnh sửa nội dung bởi hoangtrong2305: 21-10-2014 - 22:53

Toán học là ông vua của mọi ngành khoa học.

Albert Einstein

(1879-1955)

Hình đã gửi


-------------------------------------------------------------------------------------------------------------------


Click xem Đạo hàm, Tích phân ứng dụng được gì?

và khám phá những ứng dụng trong cuộc sống


#2
hoangtrong2305

hoangtrong2305

    Trảm phong minh chủ

  • Phó Quản lý Toán Ứng dụ
  • 861 Bài viết

Sau khi nhúng vô tô xà phòng, ta được hình ảnh các màng xà phòng bám trên các que tăm có dạng hình sau:


stei10_images_phocagallery_Hinh-hoc_thumstei11_images_phocagallery_Hinh-hoc_thum


Chắc hẳn bạn không ngờ đáp án lại là hình dạng này đúng không nào? Tổng chiều dài đoạn đường là $1+\sqrt{3} \approx 2, 73 \text{km}$ đấy. Bạn có thể kiểm chứng đáp án này. Biết rằng trong hình trên, cứ hai đoạn thẳng nào giao nhau thì sẽ tạo với nhau góc $120^{o}$.


stei12_images_phocagallery_Hinh-hoc_thum

Tổng hợp chiều dài qua $6$ bản thiết kế


Bài toán này là 1 dạng của bài toán cây Steiner (hay còn gọi là Bài toán cây Steiner tối thiểu), một vấn đề trong ngành Tối ưu hóa tổ hợp. Bài toán phát biểu như sau:
 

“Cho một tập hợp $V$ gồm các điểm, hãy kết nối chúng bằng một mạng lưới (hay đồ thị) sao cho tổng chiều dài của các cạnh là ngắn nhất.”
Bài toán cây Steiner ứng dụng rất nhiều trong thiết kế mạng lưới. Nhiều phiên bản của bài toán này nằm ở vấn đề $\text{NP – đầy đủ}$ thuộc ngành lý thuyết tính toán phức tạp. Một số trường hợp hạn chế được ứng dụng trong hàm đa thức thời gian, dùng để xử lý độ phức tạp của thuật toán.
 

Bài toán gốc của bài toán này là Bài toán cây Steiner trong không gian Euclide. Khi đó, những điểm trong đồ thị phải là cấp $3$, tức điểm đó là điểm chung của $3$ đoạn thẳng khác nhau và 3 đoạn thẳng này hợp lại tạo thành góc $120^{o}$ (điểm Fermat). Dẽ nhận thấy rằng công cụ xà phòng đã giúp cho ta áp dụng được bài toán này vào thực tế.
 

Mở rộng thêm vấn đề, nếu như tôi có $3$ tòa nhà xếp thành hình tam giác như thì bản thiết kế đường đi tối ưu sẽ thế nào? Lại sử dụng “công nghệ” xà phòng, ta được kết quả:

stei13_images_phocagallery_Hinh-hoc_thum


Giao điểm của 3 đoạn thẳng trên gọi là điểm Steiner (hay điểm Fermat) và cứ 2 cạnh bất kỳ sẽ tạo với nhau góc $120^{o}$. Mở rộng thêm cho trường hợp $4, 5, 6$ điểm, ta có các kết quả:

stei10_images_phocagallery_Hinh-hoc_thumstei14_images_phocagallery_Hinh-hoc_thum

stei15_images_phocagallery_Hinh-hoc_thumstei16_images_phocagallery_Hinh-hoc_thum

stei17_images_phocagallery_Hinh-hoc_thum

Với trường hợp $8$ điểm, ta có kết quả:


stei18_images_phocagallery_Hinh-hoc_thum

$$(1)$$


Bài viết đã được chỉnh sửa nội dung bởi hoangtrong2305: 21-10-2014 - 22:50

Toán học là ông vua của mọi ngành khoa học.

Albert Einstein

(1879-1955)

Hình đã gửi


-------------------------------------------------------------------------------------------------------------------


Click xem Đạo hàm, Tích phân ứng dụng được gì?

và khám phá những ứng dụng trong cuộc sống


#3
hoangtrong2305

hoangtrong2305

    Trảm phong minh chủ

  • Phó Quản lý Toán Ứng dụ
  • 861 Bài viết

Tuy nhiên $(1)$ lại không phải là đáp án tối ưu. Nếu bạn vẽ chu vi qua $8$ điểm này, đáp án mới sẽ nhỏ hơn đáp án ban đầu 1 lượng rất bé.
 


stei19_images_phocagallery_Hinh-hoc_thum

 
Vậy đáp án $(1)$ chỉ là một giá trị tối thiểu địa phương. Bạn có thể mường tượng khái niệm “tối thiểu” như là một số thung lũng, bạn có thể rất hài lòng khi đặt chân đến 1 thung lũng nhưng nó lại không phải nơi có độ sâu sâu nhất. Để đạt đến nơi sâu nhất, bạn phải tác động vào đáy thung lũng 1 năng lượng nào đó (như đào đất hay cho nổ bom chẳng hạn).
 
Để dễ hiểu, ta sẽ áp dụng vào màng xà phòng, sử dụng lại bài toán $4$ tòa nhà. Nhúng vào tô xà phòng theo hướng khác, ta được kết quả khác so với kết quả tối ưu, giống với bản thiết kế 4.
 

stei21_images_phocagallery_Hinh-hoc_thum


Tổng độ dài này chỉ là một giá trị tối thiểu địa phương và nó không phải là độ dài ngắn nhất. Để đạt được giá trị tối ưu, ta tác động vào nó 1 năng lượng, cụ thể là thổi vào màng xà phòng.


stei22_images_phocagallery_Hinh-hoc_thumstei23_images_phocagallery_Hinh-hoc_thum

stei24_images_phocagallery_Hinh-hoc_thumstei25_images_phocagallery_Hinh-hoc_thum

Ở Anh Quốc, người ta đã ứng dụng bài toán này trong việc thiết kế, xây dựng hệ thống đường ray xe lửa.
 


stei26_images_phocagallery_Hinh-hoc_thum

 
Qua bài toán này, các bạn thấy chỉ cần ta tinh ý biết sử dụng thêm những kiến thức từ các môn khoa học khác, ta sẽ giải quyết vấn đề toán học một cách dễ dàng.
Tài liệu sử dụng trong bài viết này:
1. Maths Problem: Connect the towns solution (Motorway Problem) - Tiến sĩ James Grime:
 

 
2. Steiner tree problem: http://en.wikipedia....er_tree_problem
3. The Science of Soap Films and Soap Bubbles - Cyril Isenberg: https://vi.scribd.co...enberg#page=168
4. Soap Films and Soap Bubbles by Dr. Cyril Isenberg MBE:
 


Bài viết đã được chỉnh sửa nội dung bởi hoangtrong2305: 21-10-2014 - 22:52

Toán học là ông vua của mọi ngành khoa học.

Albert Einstein

(1879-1955)

Hình đã gửi


-------------------------------------------------------------------------------------------------------------------


Click xem Đạo hàm, Tích phân ứng dụng được gì?

và khám phá những ứng dụng trong cuộc sống


#4
anhhoang1997

anhhoang1997

    Binh nhất

  • Thành viên
  • 22 Bài viết

ad ơi sao hình ko xem được nhỉ?



#5
30 minutes

30 minutes

    Hạ sĩ

  • Thành viên
  • 89 Bài viết

Sau khi nhúng vô tô xà phòng, ta được hình ảnh các màng xà phòng bám trên các que tăm có dạng hình sau:


stei10_images_phocagallery_Hinh-hoc_thumstei11_images_phocagallery_Hinh-hoc_thum


Chắc hẳn bạn không ngờ đáp án lại là hình dạng này đúng không nào? Tổng chiều dài đoạn đường là $1+\sqrt{3} \approx 2, 73 \text{km}$ đấy. Bạn có thể kiểm chứng đáp án này. Biết rằng trong hình trên, cứ hai đoạn thẳng nào giao nhau thì sẽ tạo với nhau góc $120^{o}$.


stei12_images_phocagallery_Hinh-hoc_thum

Tổng hợp chiều dài qua $6$ bản thiết kế


Bài toán này là 1 dạng của bài toán cây Steiner (hay còn gọi là Bài toán cây Steiner tối thiểu), một vấn đề trong ngành Tối ưu hóa tổ hợp. Bài toán phát biểu như sau:
 

“Cho một tập hợp $V$ gồm các điểm, hãy kết nối chúng bằng một mạng lưới (hay đồ thị) sao cho tổng chiều dài của các cạnh là ngắn nhất.”
Bài toán cây Steiner ứng dụng rất nhiều trong thiết kế mạng lưới. Nhiều phiên bản của bài toán này nằm ở vấn đề $\text{NP – đầy đủ}$ thuộc ngành lý thuyết tính toán phức tạp. Một số trường hợp hạn chế được ứng dụng trong hàm đa thức thời gian, dùng để xử lý độ phức tạp của thuật toán.
 

Bài toán gốc của bài toán này là Bài toán cây Steiner trong không gian Euclide. Khi đó, những điểm trong đồ thị phải là cấp $3$, tức điểm đó là điểm chung của $3$ đoạn thẳng khác nhau và 3 đoạn thẳng này hợp lại tạo thành góc $120^{o}$ (điểm Fermat). Dẽ nhận thấy rằng công cụ xà phòng đã giúp cho ta áp dụng được bài toán này vào thực tế.
 

Mở rộng thêm vấn đề, nếu như tôi có $3$ tòa nhà xếp thành hình tam giác như thì bản thiết kế đường đi tối ưu sẽ thế nào? Lại sử dụng “công nghệ” xà phòng, ta được kết quả:

stei13_images_phocagallery_Hinh-hoc_thum


Giao điểm của 3 đoạn thẳng trên gọi là điểm Steiner (hay điểm Fermat) và cứ 2 cạnh bất kỳ sẽ tạo với nhau góc $120^{o}$. Mở rộng thêm cho trường hợp $4, 5, 6$ điểm, ta có các kết quả:

stei10_images_phocagallery_Hinh-hoc_thumstei14_images_phocagallery_Hinh-hoc_thum

stei15_images_phocagallery_Hinh-hoc_thumstei16_images_phocagallery_Hinh-hoc_thum

stei17_images_phocagallery_Hinh-hoc_thum

Với trường hợp $8$ điểm, ta có kết quả:


stei18_images_phocagallery_Hinh-hoc_thum

$$(1)$$

a ơi, ko xem đc hình


:wub:  Nguyễn Thùy Dung  :wub: 


#6
hoangtrong2305

hoangtrong2305

    Trảm phong minh chủ

  • Phó Quản lý Toán Ứng dụ
  • 861 Bài viết

ad ơi sao hình ko xem được nhỉ?

 

 

a ơi, ko xem đc hình

 

Các bạn vào clip trong mục 1, phần "Tài liệu sử dụng trong bài viết này" ở cuối bài, hình ảnh mình chụp từ clip đó. Xin lỗi các bạn vì sự bất tiện này.


  • lvx yêu thích

Toán học là ông vua của mọi ngành khoa học.

Albert Einstein

(1879-1955)

Hình đã gửi


-------------------------------------------------------------------------------------------------------------------


Click xem Đạo hàm, Tích phân ứng dụng được gì?

và khám phá những ứng dụng trong cuộc sống





1 người đang xem chủ đề

0 thành viên, 1 khách, 0 thành viên ẩn danh