Tales Igor Ebert

Tales Igor Ebert – Projetos de Universidade

Algorithm implementation for Solution through “backtracking”

The problem of “Military – Explore territory”!

Scenario: A military man has the important task of entering a hostile territory, exploring all the possibilities of existing paths and mapping a safe path to a final coordinate. There are obstacles that prevent him from pursuing, he needs to check if paths allow passage. He needs to deactivate the land mines that exist along that path. The main objective of the military is to bring back a map indicating all and the best safe route, marking for the other military the free passage coordinates and the location of each mine found and deactivated.

Backtracking: To solve this problem it is necessary to implement a backtracking and recursive algorithm. The proposal is similar to the implementations of the proposed labyrinth solutions with small adjustments to satisfy the initial proposal.

Results: The recursive backtracking algorithm runs from the position x (1), y (1), all possible paths with the order (north, south, east and west), marking the position as 3 for path used, 7 for Mine and 8 for final position. Every time you find a dead-end path, the recursion will drop to the last valid path.

See complete text PDF on: https://docs.google.com/document/d/1HRbpfoH_UrKZf4glPlNo_NGuJrUQGye1bGWqRvydKHE/pub

Input Matrix:
 {{1, 1, 1, 1}, // first state
 {1, 0, 0, 1},
 {1, 9, 0, 1},
 {1, 0, 4, 1},
 {1, 1, 1, 1};
 where the walls are represented by 1, the paths free by 0, 4 as the end, and the mines by number 9.

The algorithm will mark the valid path with 3, mines found by 7, and the end by 8.

At the end, all valid states (paths found) are stored in a list of states in the Search class. If you need to debug, enable the enable_debug attribute using the commented //first.enableDebug () method;

The FindBest class is just to find the best path.

Code on github: https://github.com/talesebert/backtraking_maze_mine

compile: javac Search.java State.java FindBest.java
run: java Search

The final output result is something like this:

We found 4 path(s)! Enable debug to view all paths.
 1 1 1 1
 1 3 3 1
 1 9 3 1
 1 0 8 1
 1 1 1 1
The best path :) with only: cost 3 and travaled 4Km

Junho 18th, 2017

Posted In: Recursive algorithm

Leave a Comment

Artigo sobre o trabalho Assist Automation, AA

Artigo sobre o trabalho Assist Automation, AA

Artigo apresenta um experimento de automação em nuvem que reúne diversos desafios, desde a confecção do protótipo de automação ao desenvolvimento de um software para automatizar e controlar ambientes remotamente. 

Article presents a cloud automation experiment that brings together a number of challenges, from the creation of the automation prototype development of a software to automate and control environments remotely.

Download Artigo: AA_TALF_3825.pdf

Outubro 13th, 2016

Posted In: Universidade

Etiquetas:, , ,

Leave a Comment

diagramaTrabalho da disciplina de Arquitetura e Organização de Computadores (Engenharia da Computação)

O objetivo do trabalho foi entender o funcionamento de um microcontrolador e construir um circuito capaz de receber e enviar 8Bits(1Byte) controlados por um computador e/ou microcontrolador.
Durante a apresentação foi demonstrado o funcionamento do ‘Módulo chaveador I/O 8‘ sendo controlado por uma placa Arduino(ATMEGA328) e controlado por um computador usando uma porta paralela.

Arquivo .PDF do trabalho com código fonte: Trabalho-Final

 

Vídeo:  http://tirs.com.br/universidade/arquitetura/ArOrgComp-trabalho-final_001.php

Julho 23rd, 2014

Posted In: Engenharia de Software

Etiquetas:, , ,

6 Comments