| Popis: |
U ovom radu bavimo se konstrukcijom Steinerovih sustava trojki, jednog od proučavanijih kombinatoričkih blokovnih dizajna. Nakon konciznog pregleda matematičke podloge, nastavljamo s usporedbom egzaktnog backtracking algoritma s heurističkim algoritmom penjanja uzbrdo na klasičnom NP-teškom 0–1 problemu naprtnjače, kako bismo pokazali prednosti (i poneke nedostatke) metoda heurističke pretrage. Slijedi opis Stinsonovog algoritma, temeljenog na heurističkom algoritmu penjanja uzbrdo, te dviju varijanti korištenih struktura podataka. Pokazujemo da je istim moguće konstruirati Steinerove sustave trojki viših redova (v > 5000) u razumnom vremenskom rasponu (oko 1 minute), s eksperimentalno utvrđenom vremenskom složenošću O(v^2 ln v^2). This thesis concerns with the construction of Steiner triple systems, one of the more studied combinatorial block designs. After a concise theoretical overview, we compare the exact backtracking algorithm with the heuristic hill-climbing algorithm on a classic NP-hard 0–1 knapsack problem, to show the advantages (and some of the disadvantages) of heuristic search. Further on, we describe the Stinson’s algorithm, based on the heuristic hill-climbing algorithm, which we implement using two different data structure sets. We show it is possible to employ the algorithm in construction of higher order Steiner triple systems (v > 5000), within reasonable time (around 1 min) and with experimentally determined time complexity of O(v2 ln v2). |
