Mọi người giúp mình bài toán này với.
Cho 1 matrix binary MxN. Mỗi cell có giá trị 1 hoặc 0. Các cell ở gần nhau có giá trị 0 được xem như là các đảo. Như ở hình trên là các cell màu xanh lá cây.
Xây dựng giải thuật để xây cầu kết nối tất cả các đảo với minimum cost ( VD như trong hình là các ô màu xám )…
ko biết làm, cùng hóng 
M, N giới hạn bao nhiêu, duyệt trâu được ko :V
Tầm khoảng < 20 bạn à.
vậy chắc xài all pair shortest path lên cả bản đồ. Rồi với mỗi đảo, tìm đường đi ngắn nhất tới từng đảo khác (lập từng ổ của đảo A tới từng ô đảo B, tìm đường ngắn nhất giữa 2 ô, lẹ hơn nếu đã tính all pair shortest path trước đó). Sau đó ta có 1 cái đồ thị nối V đảo từng đôi một với nhau, xài minimum spanning tree nữa là ra :V
chém gió vậy thôi chứ cài đặt ko biết làm :V
Min A => B + min B => C chưa chắc đã là min đia qua A,B,C
Hi Le Hoai.
Bạn thử mô hình hóa nó về dạng đồ thì xem. Đảo thì co lại thành 1 đỉnh. Thêm các đỉnh phụ để tạo thành mộ đồ thị rồi tim cây khung nhỏ nhất trên đồ thị. Chú ý các đỉnh thêm thì không nhất thiết thêm vào cây khung.
P/S Các cầy nối có được thông nhau không ?
nghĩa là sao?
minimum spanning tree đặc trị cho bài này mà https://en.wikipedia.org/wiki/Minimum_spanning_tree
tìm min A-B, min B-C. … là để tìm trọng số của đồ thị liên thông các đảo thôi. Mỗi đảo coi như là 1 đỉnh của đồ thị, 3 đảo thì 3 cạnh, 4 đảo 6 cạnh, n đảo n(n-1)/2 cạnh, rồi chuyển về MST mà trị :V
Thông được bình thường bạn nhé.
Bạn nói rõ hơn được tí ko?
Hi Le Hoai.
Khi đó xuất hiện bài toán đảo nhân tạo. Đại khai khi đó đỉnh của đồ thì không chỉ gồm các đảo mà có thể thêm một ô bất kỳ ở giữa nữa nó sẽ khá phức tạp khi đó cần phải phân tích kỹ xem khi nòa thì thêm các đảo nhân tạo vao.
Giờ ko biết phân tích như thế nào nhỉ…
Mãi vấn chưa nghĩ ra được cách làm hoàn chỉnh.
Mình nghĩ theo hướng của mình thôi. Chắc cũng chưa tối ưu.
Đầu tiên phải nhận dạng đc đảo trước bằng cách gom hết các ô 0 lại vào 1 list. Nhận dạng đảo bằng cách mỗi 1 ô bất kỳ(ngoài trừ các ô đụng lề) đều có 8 neighbors bao quanh) Cứ ô neighbor nào 0 thì add vào list đảo, ô nào 1 không add. Add đến khi nào không add đc nữa thì nhảy sang 1 ô khác tiếp tục. Nên dùng stack hoặc queue để giảm bớt quá trình add này.
Sau đó phải xác định đc các góc của đảo. Góc là các ô trong list đảo có số neighbors(=1) bao quanh lớn nhất.
Tính công thức dist từ 1 góc của 1 đảo đến 1 góc của 1 đảo khác. Tìm tất cả đảo rồi chọn đường ngắn nhất. Ko xét đến 2 đảo này nữa. Rồi cứ lặp lại đến khi hết.
Cách này dạng Dijkstra’s algorithm. Ko chắc chắn ngắn nhất nhưng thời gian giải đc nhanh nhất.
đúng rồi, có vụ cầu nối thông nhau nữa, vậy bài toán phức tạp hơn nhiều, xài MST chắc ko được :v
ví dụ
010
111
101
thì cầu nối sẽ là
010
1x1
101
cost: 1
nếu nối 3 đảo bằng 3 cạnh rồi xài MST thì nó ra có thể là 2 cạnh chứ ko có vụ ra 1 cạnh xài chung như vậy được…
010
x1x
101
cost: 2
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?