Skip to content
Narrow screen resolution Wide screen resolution Auto adjust screen size Increase font size Decrease font size Default font size default color grey color
         
 | 
VNOI - Olympic tin học Việt Nam

Điểm tin VOJ

Số thành viên:6040
Số bài tập:1001
Số bài nộp:722923
Bài nộp hôm nay:0

Top 10 thành viên xuất sắc

HạngThành viênĐiểm
1mr_invincible587.9
2white_cobra418.6
3hieult403.4
4phaleq384.0
5vodanh9x368.2
6con_nha_ngheo352.0
7flash_mt350.2
8darksabers349.8
9yenthanh132345.3
10rockman9x_94343.1
1. Phân cụm In E-mail
(3 votes)
Người viết: Ngô Minh Đức   
27/03/2008
Phân cụm là một bài toán có ý nghĩa ứng dụng quan trọng trong các lĩnh vực như học máy, khai phá dữ liệu, thu thập dữ liệu và đòi hỏi phân hoạch tập các điểm dữ liệu ra thành các nhóm sao cho các điểm trong cùng một nhóm là “gần nhau”  và “cách xa” các nhóm khác. Trong bài này chúng ta xét một dạng đơn giản của bài toán phân cụm.

Cho tập gồm n đối tượng X = {x1, x2, ..., xn}, khoảng cách d(xi, xj) giữa mọi cặp xi ¹ xj và một số nguyên dương k (k £ n). Giả thiết là d(xi, xj) là các số nguyên dương, d(xi, xj) = d(xj, xi) và d(xi, xi) = 0, với mọi i, j = 1, 2, ..., n. Ta gọi một cách phân cụm là một  cách phân hoạch tập X ra thành k tập con khác rỗng (mỗi tập con như vậy được gọi là một cụm). Cho C = {C1, C2, ..., Ck}  là một cách phân cụm, ta gọi độ phân tách của cách phân cụm C (ký hiệu là r(C )) là giá trị nhỏ nhất trong số các khoảng cách giữa hai phần tử bất kỳ thuộc hai cụm khác nhau, nghĩa là

r(C ) = min {d(u,v): u Î Cp, v Î Cq , p ¹ q }.

Yêu cầu: Tìm cách phân cụm với độ phân tách là lớn nhất.

Dữ liệu: Vào từ file văn bản CLUSTER.INP:

  • Dòng đầu tiên chứa hai số nguyên nk.
  • Dòng thứ i trong số n dòng tiếp theo ghi các số d(xi, x1), d(xi, x2), ..., d(xi, xn), i = 1, 2, ..., n.

Các số trên cùng một dòng được ghi cách nhau bởi dấu cách.

Kết quả: Ghi ra file văn bản CLUSTER.OUT độ phân tách của cách phân cụm tìm được.

Ví dụ:

CLUSTER.INP

CLUSTER.OUT

4 3

0 1 2 3

1 0 2 3

2 2 0 3

3 3 3 0

2

Hạn chế:

  • Trong tất cả các test: 1 £ n £ 200; d(xi, xj) £ 32000, i, j = 1, 2, ..., n.
  • Có 50% số lượng test với n £ 100.
 
Tiếp >