Desain dan Analisis Algoritma Minimum Mobile Guarded Guards pada Studi Kasus SPOJ OFBEAT - Officers on the Beat

Tanner, Timothyus (2021) Desain dan Analisis Algoritma Minimum Mobile Guarded Guards pada Studi Kasus SPOJ OFBEAT - Officers on the Beat. Undergraduate thesis, Institut Teknologi Sepuluh Nopember.

Text 05111740000103-Undergraduate_Thesis.pdf - Accepted Version Restricted to Repository staff only until 1 April 2023. Download (2MB) | Request a copy

Abstract

Mobile guarded guards adalah guards yang dijaga setidaknya oleh satu guard lainnya dan setiap guard memiliki jalur patrolinya sendiri yang berupa sebuah garis lurus yang berada pada poligon di mana garis lurus ini hanya mengarah vertikal atau horizontal, tidak terdapat garis diagonal. Orthogonal polygon adalah poligon di mana semua persimpangan tepinya berbentuk saling tegak lurus.
Topik tugas akhir ini mengulas algoritma minimum mobile guarded guards dengan bentuk poligon, yaitu orthogonal polygon. Metode penyelesaian permasalahan minimum mobile guarded guards dapat diselesaikan dengan mencari jumlah segmen vertikal minimal yang melindungi semua segmen horizontal dan mencari jumlah segmen horizontal minimal yang melindungi semua segmen vertikal.
Tugas akhir ini berhasil menyelesaikan permasalahan di atas dengan efisien, dengan waktu penyelesaian rata-rata 0,02 detik dan penggunaan memory rata-rata 4,74 MB.
=====================================================================================================
Mobile guarded guards are guards who are guarded by at least one other guard and each guard has his own patrol line which is a straight line that is in a polygon where this straight line is only vertical or horizontal, there are no diagonal lines. Orthogonal polygon is a polygon where all the intersections of the edges are perpendicular.
The topic of this final project examines the minimum algorithm for mobile guarded guards with a polygon shape, namely orthogonal polygon. The method for solving the minimum problem of mobile guarded guards can be obtained by finding the minimum number of vertical segments that cover all horizontal segments and finding the minimum number of horizontal segments that cover all vertical segments.
This thesis are successful in solving the above problems efficiently, with an average resolution time of 0,02 seconds and an average memory usage of 4,74 MB.

Item Type:	Thesis (Undergraduate)
Uncontrolled Keywords:	garis horizontal, mobile guarded guards, persegi vertical, poligon orthogonal horizontal line, mobile guarded guards, orthogonal polygon, vertical rectangle
Subjects:	Q Science > QA Mathematics > QA166 Graph theory Q Science > QA Mathematics > QA640.7 Discrete geometry Q Science > QA Mathematics > QA9.58 Algorithms
Divisions:	Faculty of Intelligent Electrical and Informatics Technology (ELECTICS) > Informatics Engineering > 55201-(S1) Undergraduate Thesis
Depositing User:	Timothyus Tanner
Date Deposited:	03 Mar 2021 01:14
Last Modified:	03 Mar 2021 01:14
URI:	http://repository.its.ac.id/id/eprint/83155

Actions (login required)

View Item