-
Notifications
You must be signed in to change notification settings - Fork 5
/
LP4.swift
30 lines (28 loc) · 1.26 KB
/
LP4.swift
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
//
// LP4.swift
// AlgorithmsSwift
//
// Created by Michael Ho on 11/12/20.
//
class LP4 {
/**
The content in this lecture is another example of SAT problem - Max SAT problem. In the previous graph lecutres,
2-SAT and 3-SAT problems were discussed. The major difference between those and Max SAT is that those problems has
certain answers while Max SAT problem only has optimal answers. We need to keep iterating through the equations in
order to approach the best answer. Real world examples that Max SAT can apply to are:
1. Find a shortest path/plan/execution/...to a goal state
2. Find a smallest explanation
3. Find a least resource-consuming schedule
4. Find a most probable explanation (MAP)
Reference: https://www.cs.helsinki.fi/group/coreo/aaai16-tutorial/aaai16-maxsat-tutorial.pdf
Course ref: https://gt-algorithms.com/lp-approx/
P.S. I haven't done enough research on this algorithm, please feel free to contribute.
*/
func calculateMaxSAT(_ variable: Int, _ clauses: Int, clauseLeft: [Int], clauseRigt: [Int]) -> Int {
// Max SAT solvers
// 1. Branch-and-bound
// 2. Iterative, model-based
// 3. Integer Linear Programming (ILP)
return 0
}
}