Igra traženja duljeg lanca u zadanom težinskog grafu

undergraduate thesis

• Title (english): Finding a longer path game in the given weighted graph
• Author: Kristina Đunđek
• Mentor: Mario Osvin Pavčević (mentor)
• Committee member: Mario Osvin Pavčević (predsjednik povjerenstva)
• Committee member: Iva Manojlović (član povjerenstva)
• Committee member: Matija Livaić (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2024-07-09, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing

Abstract

Iako se s njim rjeđe susrećemo nego s problemom traženja najkraćeg lanca, problem traženje duljeg lanca također je jedan od problema u području teorije grafova. Ovaj rad bavi se implementacijom računalne igre zasnovane na problemu traženja duljeg lanca na težinskom grafu nasumično generiranih težina. U igri igrač i protivnik (računalo) naizmjenično biraju bridove pokušavajući maksimizirati svoju dobit. Implementirana su dva algoritma računala, lakše i teže razine, koristeći algoritme pretraživanja prostora stanja i heurističkog pretraživanja kao temelj. Za razvoj je korištena programska podrška Qt verzije 6.6.3, njezino integrirano razvojno okruženje Qt Creator verzije 13.0.1 i programski jezik C++ verzije 17.

Abstract (english)

Even though searching for the shortest path in a graph is more common, finding the longer path is also one type of problem found in Graph theory. The topic of this assignment is based on developing a computer game based on finding the longer path in a weighted graph. Two players, one of which is a computer, try chosing vertices that connect edges that bare more points. Two algorithms were developed, an easier and a harder level, taking inspiration from state space and heuristic search algorithms. It was developed in Qt version 6.6.3, its development environment Qt Creator version 13.0.1 and C++ programming language version 17.

• Keywords: Qt; teorija grafova; pretraživanje prostora; računalna igra
• Keywords (english): Qt; Graph theory; State space search; computer game
• Language: croatian
• URN:NBN: urn:nbn:hr:168:358289
• Study programme: Title: Computing; Study programme type: university; Study level: undergraduate; Academic / professional title: sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva (sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Closed access
• Created on: 2024-10-12 20:30:43