SA vẽ đồ thị: force-directed và min edge crossing

Giới thiệu

Bài này học cách xếp đỉnh đồ thị cho đẹp. Tranh đẹp giúp đọc cụm và đường đi dễ hơn.

Kiến thức cần nhớ

Cost vẽ đồ thị là gì

• Cost là điểm xấu của tranh, càng thấp càng đẹp.
• Gồm 3 ý: số cạnh cắt nhau, cạnh dài ngắn lệch, đỉnh dồn cục.
• Ví dụ đời thường: xếp bàn tiệc sao cho dây điện ít cắt nhau.
• Dịch 1 đỉnh là 1 bước đi, giữ nếu tranh đẹp lên.

Đếm giao cắt và vẽ hướng lực

• Đếm giao cắt: đếm cặp cạnh cắt nhau, đúng mục tiêu.
• Hướng lực: lò xo kéo đỉnh kề lại, lực đẩy tách đỉnh xa.
• Ví dụ đời thường: bạn bè ngồi gần, người lạ giữ khoảng cách.
• Thực tế: dùng hướng lực trước, đếm giao cắt để chấm cuối.

Chuyển đỉnh theo nhiệt độ

• Nóng: dịch xa, đảo cả cụm để thử bố cục mới.
• Nguội: dịch nhỏ để nắn từng cạnh.
• Ví dụ đời thường: lúc đầu dọn nhà mạnh tay, cuối chỉ chỉnh lọ hoa.
• Chạy nhiều seed rồi giữ tranh đẹp nhất.

Ví dụ

• Input: 4 đỉnh nối thành vòng, xếp gấp chéo. Output: SA bung ra thành hình vuông.
• Giải thích: chấp nhận xấu tạm vài bước mới gỡ được chỗ gấp.
• Code minh họa cost đơn giản:

# Tính cost: đếm giao cắt + phạt dồn cục
def cost(pos, edges):
    cut = count_crossing(pos, edges)  # số cặp cạnh cắt nhau
    crowd = crowd_penalty(pos)  # đỉnh quá gần nhau
    return cut * 10 + crowd

💻 Bài tập

Ngôn ngữ: Python 3 (hoặc C++). Dùng SA ngày 113, đếm giao cắt ngày 120, force-directed ngày 112. Nộp vào day-121/.

Bài 1: Hàm cost cho bức vẽ

def cost(G, pos, w_cross=10.0, w_len=1.0, w_close=5.0, ideal=1.0, min_dist=0.3) -> float:
    """w_cross * số giao cắt
     + w_len   * tổng (độ dài cạnh - ideal)^2
     + w_close * số cặp đỉnh gần hơn min_dist"""
def delta_move(G, pos, v, new_xy, ...) -> float:
    """Chỉ tính lại phần cost liên quan tới đỉnh v, không tính lại toàn bộ."""

Vòng 4 đỉnh xếp gấp chéo -> 1 giao cắt; xếp hình vuông -> 0
delta_move khớp cost(sau) - cost(trước) trên 1000 lần dời ngẫu nhiên

Bài 2: SA vẽ đồ thị

1. Láng giềng: dời 1 đỉnh ngẫu nhiên một đoạn tỉ lệ với nhiệt độ hiện tại (nóng dời xa, nguội dời gần).
2. Chạy trên: vòng 4 đỉnh gấp chéo, lưới 5x5 xáo trộn, cây nhị phân 31 đỉnh, Karate Club.
3. Mỗi đồ thị chạy 5 seed, giữ tranh tốt nhất. In số giao cắt và vẽ trước/sau.

Bài 3: Kết hợp và so sánh (nâng cao)

đồ_thị      spring_layout   force(ngày 112)   SA_từ_ngẫu_nhiên   force_rồi_SA   thời_gian
lưới 5x5    ...
cây 31      ...
Karate      ...

1. Chiến lược "force rồi SA": chạy force-directed trước, rồi SA ở nhiệt độ thấp để nắn giao cắt.
2. Vẽ cost theo bước của SA. Chỉ ra đoạn cost tăng tạm thời.
3. Tinh chỉnh trọng số w_cross, w_len, w_close. Mô tả ảnh hưởng của mỗi trọng số lên bức vẽ.

✅ Tiêu chí hoàn thành

• delta_move khớp tính lại toàn bộ.
• Vòng 4 đỉnh gấp chéo được bung ra thành hình vuông.
• Bảng so sánh 4 cách có số thật và hình trước/sau.
• Giải thích ảnh hưởng của 3 trọng số.

❓ Câu hỏi ôn tập

• Cost vẽ đồ thị gồm những số hạng nào?
• Đếm giao cắt khác vẽ hướng lực ở điểm gì?
• Lúc nóng và lúc nguội dịch đỉnh khác nhau thế nào?
• Vì sao phải chấp nhận xấu tạm mới thoát bố cục rối?

🌕 Bạn đã hoàn thành ngày 121. Làm hết bài tập phía trên rồi sang ngày tiếp theo.