Tôi có công thức boolean: (x_ {1} hoặc x_ {2}) và (x_ {3} hoặc x_ {4}) và ..... và (x_ {2r-1 } hoặc x_ {2r}), trong đó x_ {i} thuộc về tập hợp: {p_ {1}, p_ {2}, ... p_ {99}, ~ p_ {1}, ~ p_ { 2}, ... ~ p_ {99}} và tôi phải xác định xem một số giá trị của x_ {i} công thức đã cho có thể đúng không.Boolean satisfiability - thuật toán
Tôi biết rằng tính năng này thường khó tính toán. Nhưng có cách nào khá nhanh tôi có thể làm được vấn đề đặc biệt này không? Cho đến nay tôi đã cố gắng backtracking - đó là đệ quy tôi substitude mọi giá trị có thể (0 hoặc 1 vì vậy không nhiều) cho mỗi biến có thể và mọi biến, mà không có giá trị nào được nêu ra, là trivially đúng. Trước khi tôi đi sâu hơn vào đệ quy tôi chceck công thức (ngay cả khi không phải mọi biến đã có một giá trị) và nếu nó là sai, tôi không đi sâu hơn. Nhưng nó quá chậm. Bất kỳ ý tưởng? Tôi sẽ rất biết ơn sự giúp đỡ.
Âm thanh như một vấn đề thú vị, nhưng có lẽ [Math.StackExchange] (http://math.stackexchange.com/) có thể giúp bạn nhiều hơn với việc phát triển thuật toán. Chúng tôi sẽ giúp bạn thực hiện nó mặc dù! –