O problema do Hiker Dice em tabuleiro compacto: um estudo algorítmico

The Hiker Dice was a game recently proposed in a software designed by Mara Kuzmich and Leonardo Goldbarg. In the game a dice is responsible for building a trail on an n x m board. As the dice waits upon a cell on the board, it prints the side that touches the surface. The game shows the Hamiltonian Path Problem Simple Maximum Hiker Dice (Hidi-CHS) in trays Compact Nth , this problem is then characterized by looking for a Hamiltonian Path that maximize the sum of marked sides on the board. The research now related, models the problem through Graphs, and proposes two classes of solution algorithms. The first class, belonging to the exact algorithms, is formed by a backtracking algorithm planed with a return through logical rules and limiting the best found solution. The second class of algorithms is composed by metaheuristics type Evolutionary Computing, Local Ramdomized search and GRASP (Greed Randomized Adaptative Search). Three specific operators for the algorithms were created as follows: restructuring, recombination with two solutions and random greedy constructive.The exact algorithm was teste on 4x4 to 8x8 boards exhausting the possibility of higher computational treatment of cases due to the explosion in processing time. The heuristics algorithms were tested on 5x5 to 14x14 boards. According to the applied methodology for evaluation, the results acheived by the heuristics algorithms suggests a better performance for the GRASP algorithm

Cartografia temporal e análise geoambiental da dinâmica da foz do Rio Piranhas-Açu, regiao de Macau-RN, com base em imagens Landast 5-MT

This work embraces the application of Landsat 5-TM digital images, comprising August 2 1989 and September 22 1998, for temporal mapping and geoenvironmental analysis of the dynamic of Piranhas-Açu river mouth, situated in the Macau (RN) region. After treatment using several digital processing techniques (e.g. colour composition in RGB, ratio of bands, principal component analysis, index methods, among others), it was possible to generate several image products and multitemporal maps of the coastal morphodynamics of the studied area. Using the image products it was possible the identification and characterization of the principal elements of interest (vegetation, soil, geology and water) in the surface of the studied area, associating the spectral characteristics of these elements to that presented by the image products resulting of the digital processing. Thus, it was possible to define different types of soils: Amd, AQd6, SK1 and LVe4; vegetation grouping: open arboreal-shrubby caatinga, closed arborealshrubby caatinga, closed arboreal caatinga, mangrove vegetation, dune vegetation and areas predominately constituted by juremas; geological units: quaternary units beach sediments, sand banks, dune flats, barrier island, mobile dunes, fixed dunes, alluvium, tidal and inundation flats, and sandy facies of the Potengi Formation; tertiary-quaternary units Barreiras Formation grouped to the clayey facies of the Potengi Formation, Macau Formation grouped to the sediments of the Tibau Formation; Cretaceous units Jandaíra Formation; moreover it was to identify the sea/land limit, shallow submersed areas and suspended sediments. The multitemporal maps of the coastal morphodynamics allowed the identification and a semi-quantitative evoluation of regions which were submitted to erosive and constructive processes in the last decade. This semi-quantitative evoluation in association with an geoenvironmental characterization of the studied area are important data to the elaboration of actions that may minimize the possible/probable impacts caused by the implantation of the Polo Gas/Sal and to the monitoring of areas explorated by the petroleum and salt industries