Trung tâm cá nhân
cuốn sách gpt4 ai đã làm

thuật toán - Tìm hiểu các vấn đề thỏa mãn ràng buộc: thuật toán tô màu bản đồ

In lại Tác giả: Taklimakan Thời gian cập nhật: 2023-11-03 05:13:58 31 4
mua khóa gpt4 Nike

Tôi đang cố gắng triển khai chức năng quay lui đệ quy này cho vấn đề thỏa mãn ràng buộc đối với một thuật toán nhất định:

hàm BACKTHACKING-SEARCH(csp) trả về giải pháp/thất bại
    trả về ĐỆ THI-BACKTHACK({},csp)
hàm RECURSIVE-BACKTRACKING(gán,csp) trả về kết quả/thất bại
    nếu bài tập hoàn thành thì trả lại bài tập
    var <- SELECT-UNASSIGNED-VARIABLE(BIẾN[csp],gán,csp)
    đối với mỗi giá trị trong ORDER-DOMAIN-VALUES(var,task,csp) do
        nếu giá trị phù hợp với phép gán đã cho CONSTRAINT[csp] thì
            thêm {var = value} vào bài tập
            kết quả <- ĐĂNG KÝ-BACKTHACK(bài tập, csp)
            nếu kết quả != thất bại thì trả về kết quả
            xóa {var = value} khỏi bài tập
    trả lại thất bại

Đầu vào của csp trong BACKTRACKING-SEARCH(csp) là một lớp csp chứa a) danh sách các trạng thái, b) danh sách các màu và c) một từ điển có thứ tự với các trạng thái là khóa và giá trị là danh sách lân cận của các trạng thái không thể có cùng màu.

Vấn đề là tôi gặp khó khăn trong việc hiểu thuật toán này hoạt động chính xác như thế nào. Nếu ai đó có thể cho tôi lời giải thích thích hợp về thuật toán này, tôi sẽ rất biết ơn. Một số câu hỏi cụ thể của tôi là:

    nếu bài tập hoàn thành thì trả lại bài tập

Tôi giả định rằng vì bài tập được nhập dưới dạng một từ điển trống {}, nên điều này sẽ trả về giải pháp, là một từ điển chứa các trạng thái và màu sắc của chúng. Tuy nhiên, tôi không hiểu làm thế nào để kiểm tra xem công việc đã hoàn thành chưa? Nó có giống như việc kiểm tra kích thước của từ điển dựa trên số lượng trạng thái không?

    var <- SELECT-UNASSIGNED-VARIABLE(BIẾN[csp],gán,csp)

Lớp csp đầu vào chứa danh sách các trạng thái, tôi cho rằng đây có thể chỉ là var bằng việc lấy một giá trị từ danh sách? Tôi đoán điều khiến tôi bối rối là tôi không chắc các tham số (VARIABLES[csp], gán, csp) đang thực hiện gì trong trường hợp đầu vào của tôi.

    đối với mỗi giá trị trong ORDER-DOMAIN-VALUES(var,task,csp) do

Một lần nữa, tôi bối rối không biết chính xác đầu vào của (var, task, csp) đang làm gì. Nhưng tôi cho rằng nó đi qua mọi giá trị (hàng xóm) trong từ điển trạng thái?

        nếu giá trị phù hợp với phép gán đã cho CONSTRAINT[csp] thì
            thêm {var = value} vào bài tập
            kết quả <- ĐĂNG KÝ-BACKTHACK(bài tập, csp)
            nếu kết quả != thất bại thì trả về kết quả
            xóa {var = value} khỏi bài tập

Làm cách nào để kiểm tra chính xác xem giá trị có phù hợp với việc gán ràng buộc nhất định [csp] không? Tôi cho rằng các ràng buộc phải là một phần của lớp csp mà tôi chưa triển khai? Tôi không hiểu câu lệnh if này có tác dụng gì trong việc kiểm tra. Sẽ rất hữu ích nếu ai đó có thể giải thích rõ ràng câu lệnh if này và phần nội dung của câu lệnh if.

câu trả lời hay nhất

Vì vậy, sau khi lấy lại một số tài liệu đại học (Trí tuệ nhân tạo: Cách tiếp cận hiện đại của Peter Norvig), hóa ra vấn đề bạn gặp phải là một ứng dụng đệ quy Quay lạinhư đang tìm kiếm Bài toán tô màu đồ thị Một dạng giải pháp, còn được gọi là tô bóng bản đồ (vì lịch sử của nó là giải quyết vấn đề giảm thiểu màu sắc cần thiết để vẽ bản đồ). Việc thay thế mỗi quốc gia trên bản đồ bằng một nút và đường viền của nó sẽ cung cấp cho bạn một biểu đồ nơi chúng tôi có thể áp dụng tính năng quay lui đệ quy để tìm ra giải pháp.

Quá trình quay lui đệ quy sẽ tìm kiếm các nút biểu đồ giảm dần dưới dạng cây theo chiều sâu, kiểm tra từng nút để xem liệu có sẵn màu hay không. Nếu không, hãy thử màu tiếp theo, nếu có, hãy thử nút liền kề chưa được xem tiếp theo. Nếu không có màu nào thỏa mãn điều kiện cho một nút nhất định thì nút đó sẽ quay lui (backtrack) và chuyển sang nút anh em (hoặc nút anh chị em của nút cha nếu nút đó không có nút anh em).

Vì thế,

Tôi giả sử rằng vì bài tập được nhập dưới dạng một từ điển trống {}, nên điều này sẽ trả về giải pháp, nghĩa là từ điển chứa các trạng thái và màu sắc của chúng ... Nó có giống như kiểm tra kích thước của từ điển so với số lượng không? tiểu bang?

Vâng, vâng. Khi từ điển chứa tất cả các nút của biểu đồ có màu, bạn sẽ có giải pháp.

Lớp csp đầu vào chứa danh sách các trạng thái, tôi cho rằng đây chỉ có thể là var bằng việc loại bỏ một giá trị trong danh sách?

Cú pháp mã giả khó hiểu, nhưng ý tưởng chung là bạn sẽ có cách để tìm ra nút nào trong biểu đồ chưa được tô màu. Một cách đơn giản là trả về một nút từ từ điển mà không cần gán. Vì vậy, nếu tôi hiểu đúng cú pháp,var Một nút sẽ được lưu trữ.BIẾN[csp] Đối với tôi, nó giống như một sự thể hiện danh sách các nút trong cấu trúc CSP.

Tôi không chắc các tham số (VARIABLES[csp], bài tập, csp) đang làm gì dựa trên thông tin đầu vào của tôi

Như đã đề cập ở trên, đối số gán là một từ điển chứa các nút được đánh giá cho đến nay (và giải pháp của tương lai) và csp là cấu trúc chứa a, b và c.

Một lần nữa, tôi bối rối về chính xác những gì đầu vào của (var, chuyển nhượng, csp) đang thực hiện. Nhưng tôi cho rằng nó sẽ đi qua từng giá trị (hàng xóm) trong từ điển của trạng thái?

ĐẶT HÀNG-DOMAIN-VALUES dường như là một hàm sẽ trả về một tập hợp màu được sắp xếp trong cấu trúc CSP của bạn. Vòng lặp FOR sẽ lặp qua từng màu để kiểm tra xem chúng có đáp ứng được mức độ đó của vấn đề hay không.

 nếu giá trị phù hợp với phép gán đã cho CONSTRAINT[csp] thì

Ở đây những gì bạn đang làm là kiểm tra ràng buộc với giá trị đó để đảm bảo rằng nó đúng. Trong trường hợp này, bạn muốn kiểm tra xem có nút nào liền kề với nút này không có màu đó hay không. Nếu nút liền kề có màu đó, IF sẽ bị bỏ qua và vòng lặp for được lặp lại để thử màu tiếp theo.

Nếu không có nút liền kề nào có màu đó thì nhập vào phần thân IF và sẽ có màu value nút var 添加到 phân công trong một từ điển (tôi tin rằng {var = value} là một biểu diễn bộ dữ liệu, tôi đã có thể viết {var,value}, nhưng ồ). Sau đó gọi hàm quay lui đệ quy, đệ quy. Nếu lệnh gọi đệ quy trả về không lỗi thì kết quả của nó sẽ được trả về (có nghĩa là giải pháp đã được tìm thấy).

Nếu nó trả về lỗi (có nghĩa là nó đã thử tất cả các màu và tất cả chúng tình cờ được một nút lân cận khác sử dụng), thì từ分配 (Giải pháp) Mảng và chuyển sang màu tiếp theo. Nếu sử dụng hết tất cả các màu, trả về lỗi.

Về thuật toán - Tìm hiểu vấn đề thỏa mãn ràng buộc: thuật toán tô màu bản đồ, chúng tôi tìm thấy một câu hỏi tương tự trên Stack Overflow: https://stackoverflow.com/questions/52682417/

31 4 0
Bài viết khuyến nghị: Con trỏ hoạt động như thế nào trong danh sách liên kết đơn?
Bài viết khuyến nghị: c# - DateTimeFormatter.parseLocalDate ném UnsupportedOperationException
Bài viết khuyến nghị: Làm cách nào để chuyển BigInteger từ java sang Postgres?
Bài viết khuyến nghị: Số bước ban đầu trong vòng lặp python
Taklimakan
Hồ sơ

Tôi là một lập trình viên xuất sắc, rất giỏi!

Nhận phiếu giảm giá taxi Didi miễn phí
Phiếu giảm giá taxi Didi
Các bài viết phổ biến trên toàn bộ trang web
Chứng chỉ ICP Bắc Kinh số 000000
Hợp tác quảng cáo: 1813099741@qq.com 6ren.com
Xem sitemap của VNExpress