Projekat predstavlja implementaciju i eksperimentalno poređenje više algoritama za rešavanje problema Shortest Common Superstring (SCS). Projekat je razvijen u okviru kursa Računarska inteligencija na Matematičkom fakultetu.
Dat je skup stringova S = {s₁, s₂, ..., sₙ}. Superstring je svaki string T takav da se svaki sᵢ pojavljuje kao podstring od T. Cilj je pronaći najkraći takav string.
SCS je NP-težak problem (Gallant et al., 1980) sa primenama u sekvenciranju genoma, kompresiji podataka i VLSI testiranju.
Projekat je implementiran u programskom jeziku Python. Za pokretanje koda potrebno je instalirati sledeće biblioteke:
pip install numpy pandas matplotlib jupyter
Za MILP algoritam potreban je IBM CPLEX Optimization Studio (studentska licenca) i docplex paket. Ostali algoritmi rade bez CPLEX-a.
Projekat sadrži implementacije algoritama i biblioteku za generisanje test instanci. Eksperimentalni deo je automatizovan kroz Jupyter notebook.
Za pokretanje koda:
- Otvoriti
src/Main.ipynb - Podesiti broj test instanci koje se generišu u pozivima funkcije
makeTests - Izvršiti notebook ćeliju po ćeliju
| Algoritam | Tip | Složenost | Skalabilnost |
|---|---|---|---|
| Brute Force | Egzaktni | O(2ⁿ) | malo (n ≤ 20) |
| MILP (CPLEX) | Egzaktni | - | malo/srednje |
| Greedy | Aproksimativni | O(n²) | sve veličine |
| Genetic Algorithm | Metaheuristika | O(gen·pop·n) | sve veličine |
| VNS | Metaheuristika | O(iter·n²) | sve veličine |
| VNS Weighted | Metaheuristika | O(iter·n²) | sve veličine |
Rezultati i prateća dokumentacija nalaze se u docs/.