000			03770nam a2200289Ia 4500
001			76923
003			ft6119
005			20251105170609.0
008			190311n 000 0 eng d
040			_erda
041			_aengtag
050			_aQA76.9 M36 2014
082			_a.
100			_aMaria Kris Emmanuel P. Manzano and Jeffrey M. Ramos.
245		0	_aA further enhancement of the ashay dharwadker's algorithm in finding hamiltonian cycle with application for food delivery service
264			_a. _b. _cc2014
300			_bUndergraduate Thesis: (BSCS major in Computer Science) - Pamantasan ng Lungsod ng Maynila, 2014.
336			_b. _atext _2rdacontent
337			_30 _b. _aunmediated _2rdamedia
338			_30 _b. _avolume _2rdacarrier
505			_aABSTRACT: Hamiltonian Cycle came from the idea and invention of Icosian Game by William Rowan Hamilton. The aim of the game to visit every vertex once on a Dodecahedron graph and the ending point must be starting point forming a cycle. This problem is considered as NP-complete that is known to be theoretically and computationally difficult to be solve. Studying different graphs, and analysing the original and existing algorithm, the researchers found three problems on the existing algorithm in terms of finding Halmitonian cycles. The researchers formulated the three specific objectives based on the problems observed: 1. To improve the existing process in evaluating the nearest vertex connected to Vi in order to produce better and more effective Hamiltonian cycle; 2. To modify and improve the process and condition on the existing algorithm for cases of having exactly equal vertices to produce more optimal and better results and; 3. To eliminate the chances of not visiting all the vertices which are not connected to each other. This study applied the descriptive type of research and used surveying and interviewing as methods of gathering data from the delivery boy from different food establishments, The data gathered help and support the idea and theory formed on the study. The researchers analyse ad conducted intensive research in formulating the enhanced algorithm in order to solve the stated problems and meet the objectives. For the first problem and objective, the researchers improved the evaluation process by adding searching the nearest two pints (Vi and Vj). The researchers also added another category called “load” wherein the user will specify the load on a given vertex for the purpose of choosing the better cycle among the cycle with same distance. For the second problem and objective, the enhanced algorithm was modified that it will apply the nearest neighbour algorithm to the vertices to create path from each vertex to a particular vertex where it was equal. Alternative routes are also displayed for those cycle with equal distance on the result that was shown by the enhanced algorithm. For the third problem and objective, the researchers added a “verification process” on the last 2 parts of the algorithm wherein it will try all vertices as the starting vertex and apply the whole algorithm again until it tries all vertices as starting vertex. In the end, the algorithm will choose the path with least weight and produce the solution starting on the original home vertex. Existing and enhanced algorithm was compared using the simulator and a food delivery route finder application were developed by using the formulated enhanced algorithm. Researchers recommendations were to include time relations or running time for enhancing the algorithm, improve the implementation of the food delivery application and consider more areas on the application.
506			_a5
526			_aF
540			_a5
655			_a.
942			_alcc _cMS _2lcc
999			_c25392 _d25392