This project implements an exact and complete algorithm for computing all Minimal Hitting Sets (MHS) of a collection of sets, developed as part of the Algorithms and Data Structures course at Università degli Studi di Brescia.
A hitting set of a collection of sets is a set of elements that has a non-empty intersection with each set in the collection. A minimal hitting set is a hitting set such that no proper subset is also a hitting set.
The problem has numerous practical applications including:
- ⚡ Converting boolean expressions between DNF and CNF forms
- 🤖 Landmark selection in AI planning
- 🛠️ Software fault isolation
- 🧬 Model-based diagnosis systems
This implementation explores the solution space using a breadth-first search strategy over a partially ordered set (poset) structure, incorporating techniques to improve performance and reduce memory usage.
- ✅ Complete exact algorithm: Computes all minimal hitting sets for a given instance
- 🗂️ Efficient data structures: Custom FastBitSet implementation and use of PriorityQueue and LinkedHashMap
- ✂️ Cardinality pruning: Limits exploration depth based on problem constraints
- ⏱️ Timeout support: Configurable execution time limits with partial results
- 📊 Benchmark suite: Includes 1,397 test instances
The project includes two main algorithm implementations:
-
BaseMHS: Initial implementation using basic data structures
-
BoostMHS: Enhanced version with:
- 🏗️ Priority queue for hypothesis management
- 🗃️ Hash table for fast predecessor lookup
- ⚡ Average speedup of 1167.70× over BaseMHS
- 🚀 Maximum observed speedup of 6092.5×
- Java JDK 21 or higher
- Maven 3.8 or higher
- Git (optional, for cloning)
git clone https://github.com/Kevin-L-Github/asd-project.git
cd asd-project- Download the ZIP file from the repository
- Extract to your desired location
- Navigate to the project folder:
cd /path/to/asd-projectSimple compilation
mvn clean compileFull build with tests
mvn clean installGenerate executable JAR
mvn packageThe JAR file will be located at target/asd-project-1.0-SNAPSHOT.jar.
mvn exec:javaThe program will prompt you for:
- Benchmark file name (from
src/mybenchmarks/) - Maximum execution time in seconds
java -cp target/asd-project-1.0-SNAPSHOT.jar unibs.asd.playgrounds.Playground- Import the project as a Maven project
- Open
unibs.asd.playgrounds.Playground - Run the main method
- Input: Binary matrix in
.matrixformat (one row per line) - Output: Minimal hitting sets in
.mhsformat with statistics - Results are saved in the
results/directory
asd-project/
├── pom.xml
├── src/
│ ├── main/
│ │ └── java/
│ │ └── unibs/asd/
│ │ ├── benchmarks/ # Performance evaluation
│ │ ├── fileio/ # I/O management
│ │ ├── interfaces/ # Core interfaces
│ │ ├── mhs/ # Main algorithms
│ │ └── structures/ # Data structure implementations
│ ├── mybenchmarks/ # 1,397 test instances
│ └── results/ # Output directory
└── target/ # Build artifacts
- BoostMHS: Optimized MHS algorithm implementation
- BaseMHS: Baseline algorithm for comparison
- FastBitSet: Custom bit vector implementation
- BenchmarkReader/Writer: I/O handling
- Experiment: Automated benchmark execution with timeout
External libraries (managed automatically by Maven):
org.roaringbitmap:RoaringBitmap:1.3.0com.zaxxer:SparseBitSet:1.3org.openjdk.jol:jol-core:0.17
For detailed information about the algorithm, implementation choices, complexity analysis, and experimental results, please refer to the full project report: ASDProject23_24_def.pdf
The report includes:
- 📘 Theoretical problem analysis
- ⏱️ Complexity analysis (time and space)
- 🏗️ Implementation details and design patterns
- 📊 Comprehensive benchmark results
- ⚖️ Performance comparisons
- Kevin Liu (k.liu@studenti.unibs.it)
- Alessandro Rocchello (a.rocchello@studenti.unibs.it)
Academic Year: 2024/2025
Course: Algorithms and Data Structures
Institution: Università degli Studi di Brescia, Department of Information Engineering
This project was developed for academic purposes as part of a university course project.