Skip to content
TheChatArchiveThe Chat Archive
gpt-3.5-turbo-0301· OpenAIAi2 WildChat-4.8M (AI2)

Cho n thành phố, hãy tô màu các thành phố này sao cho không có bất kỳ hai thành phố nào…

  1. User

    Cho n thành phố, hãy tô màu các thành phố này sao cho không có bất kỳ hai thành phố nào kề nhau được tô cùng một màu và số màu được tô là ít nhất có thể. Dữ liệu vào được lưu trên một trận vuông cij. Nếu cij = 1 thì hai thành phố i,j là kề nhau, cij=0 thì hai thành phố i,j không kề nhau. Bài toán tô màu là bài toán thuộc lớp bài toán NP-Đầy đủ. TH4-01.CPP Lập trình thuật toán tham lam Welch-Powell giải bài tô màu đồ thị; file input được cho bởi file colorx.txt

  2. Assistant

    Để giải quyết bài toán tô màu đồ thị, chúng ta có thể áp dụng thuật toán tham lam Welch-Powell. Theo thuật toán này, chúng ta sẽ sắp xếp các đỉnh của đồ thị theo thứ tự giảm dần của số lượng đỉnh kề của chúng. Sau đó, chúng ta sẽ lần lượt duyệt các đỉnh đã được sắp xếp và tô màu theo quy tắc sau:

    • Đối với đỉnh đầu tiên, ta tô màu 1.
    • Đối với mỗi đỉnh tiếp theo, ta đánh dấu các màu đã được sử dụng cho các đỉnh kề của nó. Sau đó, ta chọn màu chưa được đánh dấu nào để tô cho đỉnh đó.

    Sau khi duyệt hết tất cả các đỉnh, chúng ta sẽ có một bộ phân hoạch màu cho đồ thị, sao cho hai đỉnh kề nhau sẽ không có cùng màu.

    Ở đây, chúng ta có thể lưu trữ đồ thị dưới dạng ma trận kề. Để sắp xếp các đỉnh theo thứ tự giảm dần của số lượng đỉnh kề, ta có thể sử dụng một vector lưu trữ các đỉnh và sắp xếp nó bằng cách so sánh số lượng đỉnh kề của từng đỉnh.

    Dưới đây là đoạn code tham khảo để giải quyết bài toán này:

    #include #include #include

    using namespace std;

    const int MAXN = 100;

    int n; // Số đỉnh của đồ thị int c[MAXN][MAXN]; // Ma trận kề của đồ thị

    vector order; // Các đỉnh được sắp xếp theo thứ tự giảm dần của số đỉnh kề

    int color[MAXN]; // Màu của từng đỉnh

    void welch_powell() { // Sắp xếp các đỉnh theo thứ tự giảm dần của số đỉnh kề order.clear(); for (int i = 0; i < n; i++) { int cnt = 0; for (int j = 0; j < n; j++) { if (c[i][j]) cnt++; } order.push_back(i); } sort(order.begin(), order.end(), [](int u, int v) { int cntu = 0, cntv = 0; for (int i = 0; i < n; i++) { if (c[u][i]) cntu++; if (c[v][i]) cntv++; } return cntu > cntv; });

    // Tô màu cho từng đỉnh theo thứ tự đã sắp xếp
    int num_colors = 0;
    for (int i : order) {
        // Đánh dấu các màu đã được sử dụng cho các đỉnh kề của i
        bool used[MAXN] = {false};
        for (int j = 0; j < n; j++) {
            if (c[i][j] && color[j] != -1) {
                used[color[j]] = true;
            }
        }
        // Chọn màu chưa được sử dụng để tô cho i
        int j;
        for (j = 1; ; j++) {
            if (!used[j]) {
                color[i] = j;
                num_colors = max(num_colors, j);
                break;
            }
        }
    }
    
    cout << "So mau can dung: " << num_colors << endl;
    
    // In ra màu của từng đỉnh
    for (int i = 0; i < n; i++) {
        cout << "Dinh " << i << " - Mau " << color[i] << endl;
    }
    

    }

    int main() { // Đọc dữ liệu đầu vào // ...

    // Khởi tạo màu ban đầu cho các đỉnh
    fill_n(color, n, -1);
    
    welch_powell();
    
    return 0;
    

    }