Diagrama De Tiempo Uml

Facultad de Tecnología-Carrera de Informatica

1

UNIVERSIDAD AUTONOMA GABRIEL RENE MORENO
FACULTAD DE CIENCIAS EXACTAS Y TECNOLOGÍA
CARRERA DE INGENIERÍA INFORMÁTICA

INTELIGENCIA ARTIFICIAL

Presentación Final del Problema de la Triangulación
Grupo:

12

Integrantes

Días
Trabaj.
8
8
8

Rosales Toledo Hernan
Sejas Pozo Harol
Villarroel Villarroel José

Fecha dePresentación:
Fecha Presentada:

Horas
Grupo
25
25
25

AutoEval.
Horas
Individual
12
5
12
5
12
5

Jueves, 26 de octubre del 2006
jueves, 26 de octubre del 2006

Días de Retraso:

©Copyright Derechos Reservados ChangoSoft S.A.

0

Made in Bolivia

Facultad de Tecnología-Carrera de Informatica

Índice
1. Introducción
2. Antecedentes Teóricos.
3. Representación.
a.Herramientas de Librerías.
b. Estructura de Datos.
c. Heurísticas.
d. Algoritmos.
4. Conclusiones y Recomendaciones.
5. Bibliografía.
6. Anexos.

©Copyright Derechos Reservados ChangoSoft S.A.

Made in Bolivia

2

Facultad de Tecnología-Carrera de Informatica

3

Informe Final
Problema de Triangulación
1. Introducción.- El problema consiste en definir un Polígono de N-Puntos(N>3), en
cuyo interior se debe trazar rectas de punto a punto, de modo que la suma de las
longitudes de esas rectas sea la menor posible. Estas rectas no deben intersectarse
con otras rectas, ya sean rectas del polígono o rectas interiores.
2. Antecedentes Teóricos
Delimitación de Búsqueda.- Antes de entrar al BackTrack el programa delimita ya
sobre que tiene que buscar posibilidades, paraevitar así búsquedas innecesarias, esto
consiste en hacer una Lista de Listas, en cada nodo de la primer lista se guarda otra
lista, pero esta tiene ya los puntos con los que el primer nodo de la primer lista puede
trazar una recta, el segundo nodo de la primer lista guarda también una lista de los
puntos con los que puede trazar una recta, y así sucesivamente.
Dentro de este método están lasvalidaciones para que un punto no genere rectas consigo
mismo, o con puntos adyacentes a el.

©Copyright Derechos Reservados ChangoSoft S.A.

Made in Bolivia

Facultad de Tecnología-Carrera de Informatica
Eliminación de Redundancia.-Puede ocurrir el caso de que exista redundancia de
búsqueda, por ejemplo, si el nodo 0 de la primer lista puede visitar a los puntos 1 y 2, y el
nodo 2 de laprimer lista puede visitar al punto 0, esto es redundancia, es como decir, de 0
puedo ir a 2, y de 2 puedo ir a 0, en realidad es la misma recta, por eso es innecesario
preguntar de nuevo por una recta ya antes colocada, Así que antes de colocar un nuevo
punto a la lista se pregunta si esta ya esta colocada antes en otro nodo, Ejm si va a colocar
una recta de “i” a “j”, se pregunta si ya existerecta de “j” a “i”, esto para optimizar algo
más el algoritmo.

Intersección de dos Rectas.- El programa debía ser capaz de desechar posibilidades
(Rectas) que lo llevarían a una futura intersección con otras rectas, ya sean del polígono o
rectas interiores.
Un problema parecido se nos planteó en la Materia de Programación I, consistía en hacer
un método que dados dos rectas devolviera elpunto de intersección, luego de revisar
nuestros apuntes, lo adaptamos al proyecto, ya que no solo debía encontrar el punto de
intersección, sino que debía validar que ese punto este dentro del segmento de ambas
rectas, o que ese punto de intersección fuera un punto que esta definido en el polígono, en
cuyo caso esa recta debía ser valida.
Ejm.

©Copyright Derechos Reservados ChangoSoft S.A.Made in Bolivia

4

Facultad de Tecnología-Carrera de Informatica

5

Trazar una Recta dentro del Polígono.- El programa debía ser capaz de desechar
rectas que se dibujarían por fuera del polígono, por mas que estas sean de menor longitud
que las interiores.
Para resolver este problema nos planteamos un sin número de posibilidades, la mayoría de
ellas usando los teoremas de...