Algoritmos Computacionales
MSI Edna Martha Miranda Chávez
MC Sergio Fuenlabrada Velázquez
Ago- Dic 2007
Solución de problemas
Sergio Fuenlabrada Velázquez, Edna Martha Miranda Chávez
Índice
¿Qué es un problema?
Tipos de solución
Diseño de la solución uso de Diagramas y esquemas
–
–
–
–
–
–
Diagramas de Arbol
Diagramas Venn
Cuadros de doble entrada o matriz
Integramas
Mapas Karnaugh o diagramas de Veitch
Grafos
Heurística
Solución de problemas
Sergio Fuenlabrada Velázquez, Edna Martha Miranda Chávez
¿Qué es un problema?
• El hombre ha estado siempre
vinculado con la problemática
que le presenta el medio
ambiente.
• En el siglo IX, el matemático
Abu Ja´Far Mohamed Ibn
Musa Al-Khowarizni fija las
primeras reglas para resolver
operaciones clásicas.
Solución de problemas
Sergio Fuenlabrada Velázquez, Edna Martha Miranda Chávez
Definición de problema
• Es la desviación de los resultados esperados
• El proceso físico, mental o mecánico en donde se
presenta diferentes tipos de resistencia o inercia
que deben de vencerse para obtener el resultado
deseado.
¿Que resultados
estamos obteniendo
ahora?
¿Que resultados
deseamos obtener?
Los problemas
generan necesidades;
para resolver un
problema debemos
encontrar su origen
(evitando los
distractores).
Solución de problemas
Sergio Fuenlabrada Velázquez, Edna Martha Miranda Chávez
Necesidad & Deseo
• Necesidad.- esta en función
directa de una
problemática, es una
situación real que debe ser
resuelta.
• Deseo.- Esta íntimamente
ligado a los sentimientos,
anhelos y sueños de las
personas (irracionales,
inalcanzables e
improbables)
?
n
e
c
e
s
i
d
a
d
Solución de problemas
Sergio Fuenlabrada Velázquez, Edna Martha Miranda Chávez
d
e
s
e
o
Para diferenciar una necesidad
de un deseo
• Finalidad(fin) es
una meta a
alcanzar; un
objetivo.
• Medios es el
elemento que nos
permite alcanzar
un fin.
Fines
Transportarse
y placer
Estátus
¿Que finalidad se
persigue?
¿Si yo hago esto, cual
será el resultado?
Medios
Pie
Bicicleta
Patineta
Motocicleta
Coche económico
Pecera
Metro
Camión
Rolls Royce
Mercedes
Avión
Finalidad
•Mesurable
•Medible
•Justifica
Solución de problemas
Sergio Fuenlabrada Velázquez, Edna Martha Miranda Chávez
Tipos de objetivos
• Individuales y Colectivos
• Generales y Particulares
• Básicos , Secundarios y Colaterales
• Corto y Largo Plazo
• Naturales y Subjetivos (arbitrarios )
Solución de problemas
Sergio Fuenlabrada Velázquez, Edna Martha Miranda Chávez
Objetivos individuales y colectivos
Los objetivos
individuales deben
coincidir con los
propósitos del grupo
Objetivos Generales y Particulares
particulares
particulares
Generales
particulares
Solución de problemas
Sergio Fuenlabrada Velázquez, Edna Martha Miranda Chávez
Objetivos básicos, secundarios y
colaterales
Básicos
secundarios
Beneficios
Beneficios
secundarios
Beneficios
secundarios
Beneficios
secundarios
Objetivos a largo y corto plazo
Particulares
Generales
Corto plazo
Largo plazo
Solución de problemas
Sergio Fuenlabrada Velázquez, Edna Martha Miranda Chávez
Objetivos naturales y subjetivos
Objetivos Generales
Naturales
Subjetivos
Orden
calidad
tenacidad
Propósitos
de los
objetivos
Sin justificación
no aportan al éxito
$
• Económicos
• Distributivos del
ingreso.
• Maximización de
beneficios
Solución de problemas
Sergio Fuenlabrada Velázquez, Edna Martha Miranda Chávez
Reglas para fijar Objetivos
•¿Que?
•¿Qué busca Alcanzar?
•¿Qué se pretende?
•¿Cuál es la meta?
•¿Cómo?
•¿Cómo se pretende
lograrlo?
•¿En forma integral o
parcial?
•¿Inmediato o largo plazo?
•¿Quién?
•¿Quién es responsable?
•¿Quienes lo hará posible?
•¿Dónde?
•¿Producto interno o
externo?
•¿Área que usa el
meta
producto?
•¿Cuándo?
•¿Cuándo debe lograrse?
•¿Tiempo de las partes?
•¿Es urgente o
postergable?
•¿Por qué?
•¿Por que se persigue el
Obj.?
usuario
•¿Es subjetivo?
•¿Es un objetivo personal?
Solución de problemas
Sergio Fuenlabrada Velázquez, Edna Martha Miranda Chávez
Visión global del producto
•Hacer alto
•Analizar
•Nuevos objetivos
•O. Anteriores VS O.
Nuevos
•Discrepancias
Cambios
Visión Global del Producto
Pasos para hacer los objetivos
1. Tiro las dianas
2. Pinto el blanco
1. Pinto el blanco
2. Tiro las dianas
Solución de problemas
Sergio Fuenlabrada Velázquez, Edna Martha Miranda Chávez
Estrategias para alcanzar los objetivos
Tipos de factores:
Factores mensurables
(medibles).- Pueden ser
cuantificados. Base más
objetiva y confiable a
diferencia de los de mera
apreciación.
Factores controlables.- Son
factores que podemos
adquirir o manipular, se
conoce su origen, fuente,
costo, etc.; a diferencia de
los factores no
controlables.
Factores estratégicos.Influyen en forma
decisiva al logro del
objetivo, se debe cuidar
que estos factores sean
siempre propicios.
Factores imprevisibles.Son aquellos que se
presentan en forma
inesperada ó fortuita, se
deben tratar de prever,
con el fin de buscar el
modo de controlarlos.
Solución de problemas
Sergio Fuenlabrada Velázquez, Edna Martha Miranda Chávez
Estrategias para alcanzar los objetivos
Factores que afectan
• Internos - Pertenecer al
• Externos - Pertenecer
medio ambiente interno
al medio ambiente
como serian las políticas de
externo como seria la
la dirección, disponibilidad
Política económica del
de herramientas, productos
país e internacional,
y procesos que ayudarán al
sociedad, avances
logro de la meta,
técnicos, etcétera.
estabilidad en el
financiamiento, fuerza de
trabajo, disponibilidad de
suministros, etcétera.
Solución de problemas
Sergio Fuenlabrada Velázquez, Edna Martha Miranda Chávez
Tipos de solución
“La forma de como lograr el objetivo se le
denomina, La solución”.
– Alternativas de solución (al menos con dos alternativas).
– “En el proceso para encontrar la solución se cambia
contantemente de puntos de vista”
– “La capacidad de soslayar (esquivar) una dificultad y
seguir un camino indirecto cuando el directo no aparece,
es lo que coloca al animal inteligente y a los hombres
de talento por encima de sus compañeros y de los otros
hombres”.
– En el proceso para la generación de la mejor alternativa,
se involucran varios factores, los cuales en el grado que
se apliquen determinara la calidad de la propuesta de
solución.
Solución de problemas
Sergio Fuenlabrada Velázquez, Edna Martha Miranda Chávez
Factores que determinan una solución
 Grado de conocimiento de la organización y área a
donde se aplicará la solución.
 Grado de conocimiento de la problemática.
 Grado de conocimiento del objetivo.
 Visión Objetiva y creativa.
 Experiencia laboral (en la generación de
soluciones).
 Actualización tecnológica.
 Apoyo de un grupo de trabajo con experiencia en
problemáticas similares.
 Nivel de involucración del usuario
 Número de evaluaciones previas a la presentación
de la propuesta de solución.
Solución de problemas
Sergio Fuenlabrada Velázquez, Edna Martha Miranda Chávez
Tipos de solución
• Solución
Una solución se presenta cuando la situación
del problema esta bajo control y los
resultados
obtenidos son deseados y
satisfactorios. Se hace notar que no hay
solución absoluta a problemas, ya que esta
se vuelve asintótica con respecto a las
necesidades, y en cuanto se pierde el
control del problema sus resultados varían.
Solución de problemas
Sergio Fuenlabrada Velázquez, Edna Martha Miranda Chávez
Tipos de solución
• Resolución
Se da una resolución, cuando se obtienen
resultados parciales y los efectos
más
significativos del problema se encuentran
bajo control.
• Disolución
Se presenta una disolución cuando se eliminan o
controlan las causas del problema, de esta
forma se establecen los controles para tener
un resultado deseable, sin someter al
problema a un proceso directo.
Solución de problemas
Sergio Fuenlabrada Velázquez, Edna Martha Miranda Chávez
Solución Ideal
¿Que se considera como la solución
ideal?
¿Cual es la solución ideal?
¿Que satisfactores se desean?
La solución ideal estará en función del grado
de satisfacción de las necesidades del cliente,
utilización optima de recursos y beneficios o
utilidad devengada.
Solución de problemas
Sergio Fuenlabrada Velázquez, Edna Martha Miranda Chávez
Metodología para el desarrollo de
algoritmos
1) Descripción del problema.- Comprender y plasmar
los datos de entrada y los datos requeridos de salida
2) Diseño de la solución.- Diseño del algoritmo. En
términos generales las operaciones básicas para
solucionar el problema.
3) Desarrollo.- Codificación, captura del programa,
código
4) Pruebas.- Pruebas al programa, pruebas de
integración.
5) Entrega.- Presentación y entrega del programa o del
software al usuario.
Solución de problemas
Sergio Fuenlabrada Velázquez, Edna Martha Miranda Chávez
Diseño de la solución uso de
Diagramas y esquemas
Su objetivo es la representación del
pensamiento, ideas ó el entorno a través de:
notaciones matemáticas, dibujos, imágenes
o texto; los cuales deberán ser conocidos
por todas las personas relacionadas .
El uso de diagramas y esquemas facilita la
comprensión y por lo tanto la solución y
tratamiento del problema.
Solución de problemas
Sergio Fuenlabrada Velázquez, Edna Martha Miranda Chávez
Diagramas de Árbol
Sistem.
Dir.
Gral.
Sistem. Admón. Finan.
Soporte Desarro
Prod.
Dir.
Gral.
Soporte
Desarro
Prod.
Admón.
Finan.
Describe la estructura o composición de un objeto o
situación de una manera jerárquica, para así comprender
su funcionamiento y su relación con su medio ambiente.
Solución de problemas
Sergio Fuenlabrada Velázquez, Edna Martha Miranda Chávez
Diagramas de Arbol
Se basan en la descomposición funcional, la división
del problema en subproblemas.
El proceso de descomposición funcional establece
que se debe dividir a una entidad hasta lograr
identificar sus elementos básicos llamados también
tareas o procesos.
Una función esta compuesta
por una o más acciones que
están dirigidas con un objeto
especifico.
Solución de problemas
Sergio Fuenlabrada Velázquez, Edna Martha Miranda Chávez
Reglas de descomposición funcional
HIJO
Todas las
funciones del
negocio de cierto nivel
deben representar el
conjunto de actuación
abajo de las
mismas
Deben existir por lo
menos dos niveles de
descomposición
Para cualquier
función del negocio,
sus subfunciones
deben representarla
completamente sin
traslaparse
El usuario es el
único que puede juzgar
si están correctamente
descompuestas
las funciones
Solución de problemas
Sergio Fuenlabrada Velázquez, Edna Martha Miranda Chávez
Razones para construir diagramas
de árboles
• Definir la información necesaria para asegurar
que la aplicación cubra los objetivos.
• Conocer el alcance de la aplicación.
• Identificar los elementos que afectan a la
aplicación.
• Definir las necesidades que cubriera la
aplicación por área.
• Identificar como los objetivos de la aplicación
están acorde con las áreas de negocios.
.
Solución de problemas
Sergio Fuenlabrada Velázquez, Edna Martha Miranda Chávez
Representación de relaciones
PADRE
HIJO
PADRE
HIJO
HIJO
HIJO
PADRE
HIJO
PADRE
HIJO
HIJO
HIJO
HIJO
En una estructura funcional, hay funciones menores en
los niveles inferiores que conforman la función del nivel
superior.
Solución de problemas
Sergio Fuenlabrada Velázquez, Edna Martha Miranda Chávez
Pasos para la descomposición
1. Seleccionar la función a descomponer.
2. Descomponer la función en subfunciones
3. Verificar la descomposición funcional
Regla unión “AND”: Todas las funciones deben
ejecutarse para conformar el nivel superior.
Regla intersección “OR”: Cada subfunción
representa el total de la función del nivel superior.
4.- Verificar la descomposición funcional.
Una regla de refinamiento establece que se debe
evitar que se traslapen las funciones en la
descomposición.
Una función debe ser descompuesta hasta que sus
subfunciones no se puedan descomponer o no sea de
interes el descomponerlas
Solución de problemas
Sergio Fuenlabrada Velázquez, Edna Martha Miranda Chávez
Diagramas de Venn
Esquema utilizado para el estudio de
conjuntos, útil para la definición de estructuras
de bases de datos.
Num. Tarjeta
A
Tarjeta de
crédito
C
B
Materias
CI, II
de Crédito
Datos
Personales
Nombre
Num. de
Cuenta
Cheques
Solución de problemas
Cheques
Sergio Fuenlabrada Velázquez, Edna Martha Miranda Chávez
Historial
crediticio
Cuadro con doble entrada o
Matriz
Asigna actividades
para realizar fiesta
Se utiliza para comparar dos elementos
Pablo
Alejandra
Sergio
Solución de problemas
Sergio Fuenlabrada Velázquez, Edna Martha Miranda Chávez
Anal. Inf.
Recop.
Ordenar
Inf.
Est. SW
en merc.
Est. Sol.
previas
Nombre
Recop.
Inf. Usu.
Actividad
Integramas
Se utiliza para comparar 3 o más elementos
Alumnos
S Nomb Juan Bety Pablo Ana Raquel Pepe
e
c 2CM1
u
2CM2
e
n 2NM1
c
i
a 2NM2
M M1
a
t
e M2
r
i M3
a
Solución de problemas
Sergio Fuenlabrada Velázquez, Edna Martha Miranda Chávez
¿y el
maestro?
Mapas de Karnaugh, Mapa K o
Diagramas de Veitch
• Propuesto primero por Veitch y modificado
ligeramente por Karnaugh.
• Representa la información en un diagrama de
cuadros, a su vez cada cuadro representa un
termino mínimo.
• Es el más utilizado para la simplificación de
funciones boleanas hasta con 6 variables.
• Util para representar información de forma
gráfica facilitando el reconocimiento de
patrones.
Solución de problemas
Sergio Fuenlabrada Velázquez, Edna Martha Miranda Chávez
Problema
Se tiene una biblioteca con 8 compartimentos para
clasificar libros de historia y literatura que a su vez
unos están encuadernados de forma rústica y otros
con pasta dura. ¿Cuantos libros tengo en total si
tengo?
– 52 Libros de historia los cuales 27 están en ingles.
– 34 libros de pasta dura de los cuales 3 son de historia en
francés.
– 46 Libros en ingles, la mitad rústica.
– 20 Libros de literatura en francés.
– 31 Libros en rústica de literatura.
Solución de problemas
Sergio Fuenlabrada Velázquez, Edna Martha Miranda Chávez
Problema
Rústicos
Pasta dura
Historia
Literatura
Francés
Inglés
Solución de problemas
Sergio Fuenlabrada Velázquez, Edna Martha Miranda Chávez
Francés
Problema
Rústicos
Pasta dura
Historia
22
4
23
3
Literatura
12
19
0
8
Francés
Inglés
Solución de problemas
Sergio Fuenlabrada Velázquez, Edna Martha Miranda Chávez
Francés
Diagramas de Gráfos
• Una gráfica es un conjunto finito de puntos,
algunos de los cuales están conectados por
líneas.
• Una gráfica dirigida es un conjunto finito de
puntos algunos de los cuales están conectados
por flechas.
• La conexión entre puntos puede ser a través de
líneas rectas o curvas, líneas largas o cortas,
una línea o varias, lo importante es la
incidencia en el punto.
Solución de problemas
Sergio Fuenlabrada Velázquez, Edna Martha Miranda Chávez
Ejemplo
• Diagrama de flujos.
• Diagrama de Pert
B
A
E
C
D
Solución de problemas
Sergio Fuenlabrada Velázquez, Edna Martha Miranda Chávez
Noción Algorítmica
• Es una técnica auxiliar para la solución de
problemas cíclicos e iterativos
• Un algoritmo es una sucesión de eventos o
pasos bien establecidos que tienen la finalidad
de dar solución a una problemática.
• Un algoritmo generalmente se representa por
símbolos (nomenclatura clara e identificable).
• El tratamiento a un problema no es una tarea
fácil, ya que depende del tipo de problema y
de las variables internas y externas que lo
afectan.
Solución de problemas
Sergio Fuenlabrada Velázquez, Edna Martha Miranda Chávez
Noción Algorítmica
La noción algorítmica establece que hay que
conocer el problema de tal forma y con tanta
profundidad y detalle que con gran facilidad se
pueda:
 Describir
 Esquematizar - Representar cada una de sus
partes y variables (conocer el comportamiento
del problema).
La visión analítica es aplicada en forma intuitiva
por muchas personas (hacerla consciente).
Fuertemente ligada a los conocimientos y
experiencia del individuo.
Solución de problemas
Sergio Fuenlabrada Velázquez, Edna Martha Miranda Chávez
Permite:
Visión Analítica
 Identificar el tipo de problema que se trata,
 Analizar la situación y
 Otorgar soluciones preliminares muy
acertadas.
La experiencia aunada a una visión analítica
permite con mayor facilidad el establecer
estimaciones acertadas de tiempos de desarrollo,
personal requerido, costos, ventajas y desventajas,
riesgos, limitaciones y alcances.
La visión analítica global (visión sistémica) deberá
permanecer en todo el proceso de gestión del
producto permitiéndole con esto detectar fallas
y/o desviaciones a tiempo.
Solución de problemas
Sergio Fuenlabrada Velázquez, Edna Martha Miranda Chávez
División modular del problema
También conocido como divide y vencerás, descomposición
y refinamiento. El problema es dividido en módulos
para dar solución por separado a cada uno de ellos, de
esta forma se soluciona el problema estableciendo
controles en cada modulo.
– ¿El problema se puede dividir en módulos?
– ¿Puede ser tratado cada modulo como entidad?
– ¿Él módulo es un caso especial ó es un caso genérico?
– ¿La solución del modulo esta enfocada a obtener los
resultados esperados del problema?.
Solución de problemas
Parte 1
Parte 2
Parte 5
Parte 4
Parte
3
Sergio Fuenlabrada Velázquez, Edna Martha Miranda Chávez
Subir la cuesta
• El principio se basa en que el problema y la
solución existen pero la solución y su
algoritmo no son satisfactorios.
• Se conceptualiza un segundo algoritmo para
obtener un resultado más veraz.
• Así sucesivamente hasta obtener una
solución.
Solución de problemas
Sergio Fuenlabrada Velázquez, Edna Martha Miranda Chávez
Retroceder trabajando
• Esta técnica es empleada cuando se tienen los
resultados ideales pero se desconoce el algoritmo
con el cual fue tratado el problema.
• Se toma el paso inmediato anterior a los
resultados finales.
• Se genera el algoritmo que se prueba hasta
obtener los resultados ideales.
• Una vez obtenidos estos se toma el paso que le
antecede.
• Se aplica el mismo procedimiento así
sucesivamente hasta completar el tratamiento del
problema.
Solución de problemas
origen
Sergio Fuenlabrada Velázquez, Edna Martha Miranda Chávez
Warnier
Esta técnica unifica a las tres técnicas anteriores:
1ro. Se toma el problema y se divide en módulos.
2do. Se identifica en cada modulo la solución
ideal.
3ro. Se aplica un algoritmo existente que se
aproxime a la solución y se optimiza hasta
obtener la solución ideal.
Parte 1
Parte 2
Parte 5
Parte 3
Parte 4
origen
Solución de problemas
Sergio Fuenlabrada Velázquez, Edna Martha Miranda Chávez
Marcha atrás
Esta técnica contempla una serie de alternativas de
solución al problema las cuales a su vez se dividen
en subalternativas
• Se debe conocer a fondo todas las alternativas para
poder elegir la más conveniente
• Una vez seleccionada se efectúa un seguimiento
para evaluar sus resultados
• En el momento que se detecte que los resultados no
son los esperados se abandona esta alternativa y se
elige otra.
• Hasta encontrar la que cumpla con los resultados
g
d
ideales.
i
b
e
a
c
Solución de problemas
h
j
f
Sergio Fuenlabrada Velázquez, Edna Martha Miranda Chávez
Brinca y atrapa
• Esta es una técnica genérica.
• Se establecen características particulares del problema y
para cada característica se genera un algoritmo.
• Una vez determinado y tratado, se busca otra
característica para generar su correspondiente
algoritmo.
• De tal forma que al finalizar el control del problema no
exista ningún punto por algoritmizar.
• Ya completada la algoritmización se evalúa cada
solución particular y se une con las soluciones mas
factibles hasta lograr la solución final.
General
• Esta forma se establece que esta
Particular
técnica ataca el problema de lo
particular a lo general.
Solución de problemas
Sergio Fuenlabrada Velázquez, Edna Martha Miranda Chávez
Recursión
Es un método que se basa en buscar un algoritmo
sencillo el cual sea común para tratar al
problema en forma general y que de una
solución a cada módulo del problema.
Solución de problemas
Sergio Fuenlabrada Velázquez, Edna Martha Miranda Chávez
Simulación
• Cuando en el problema existe una gran población de
variables no determinísticas y se desea conocer el estado
más favorable del problema.
• Crear un modelo que determina el comportamiento
estadístico del problema.
• Se obtienen funciones para generar valores aleatorios
para probar el comportamiento del modelo.
• Se evalúan los resultados si estos son los deseados el
problema queda resuelto.
• Por el, contrario hay que experimentar con una adición o
eliminación de variables u otros valores en las variables,
así hasta llegar al resultado esperado.
Solución de problemas
Sergio Fuenlabrada Velázquez, Edna Martha Miranda Chávez
Heurística
La mayoría de los problemas a los que se
enfrenta el Informático son del tipo Polinomial
(P), esto es que se pueden representar por medio
de un polinomio, por ejemplo: y2- 2x + 2
Sin embargo existen otro tipos de problemas los
No Polinomiales (NP), esto es, que no se
pueden representar por medio de un polinomio.
Solución de problemas
Sergio Fuenlabrada Velázquez, Edna Martha Miranda Chávez
Heurística
• Los problemas NP, son problemas tan complejos
que jamas se obtendrá la solución ideal. Lo que se
hace es expresar una aproximación a la solución
ideal.
• Se crea o diseña un algoritmo que se aproxime a
los resultados deseados. Para esto se necesita:
• Conocer el proceso para tratar el problema.
• Establecer el resultado que se aproximen a la
solución esperada.
 Especificar todos los elementos necesarios
para llegar al resultado.
Solución de problemas
Sergio Fuenlabrada Velázquez, Edna Martha Miranda Chávez
Heurística
• La solución optima para lo problemas no
polinomiales (NP) es dividir el
problema en partes de tal manera que los
tamaños
sean
computacionalmente
factibles de solucionar.
• Y se define un punto de unión entre los
grupos, esto facilita la solución.
• Y la representación clásica a este tipo de
problemas se presenta con el problema
del agente viajero.
Solución de problemas
Sergio Fuenlabrada Velázquez, Edna Martha Miranda Chávez
Heurística
El problema del Agente Viajero
Se tiene que un agente viajero debe recorrer todas las
capitales de los estados de la republica mexicana (incluido el
DF), para repartir sus productos, la pregunta sería ¿Cuál es la
mejor ruta que debe seleccionar el agente para cumplir
óptimamente con su misión.
Esto es que se recorra en el menor tiempo, con el menor
gasto posible y que toque todos los puntos indicados.
Para llegar de un punto a otro se representa como 2!. (ida y
vuelta).
Cuando se tienen 4 puntos a tocar se representa 4! (ida y
vuelta). Si solo se quiere obtener las formas posibles como se
pueden llegar a los cuatro puntos se represente (4!)/2 (grafo
dirigido).
Solución de problemas
Sergio Fuenlabrada Velázquez, Edna Martha Miranda Chávez
Heurística
El Problema del agente viajero
La formula para determinar la complejidad es n! (factorial)
Por ejemplo una ruta entre dos nodos es:
2!, esto es igual 1 * 2 = 2.
Si se hace dirigido el grafo seria n!/2:
(2!)/2 = (1*2)/2 = 2/2 = 1
Que pasa si se desea encontrar la ruta para tocar las 32 ciudades
principales de la república mexicana, seria:
32! = 2.6313083693369353016721801216e+35
Si hacemos el grafo dirigido se tendría:
32!/2=1.3156541846684676508360900608e+35
Son tantas las posibilidades y cálculos requeridos
computacionalmente que se convierte en un problema No
polinomial (NP).
Solución de problemas
Sergio Fuenlabrada Velázquez, Edna Martha Miranda Chávez
El problema del Agente viajero
• Esto es, el tiempo que se llevaría resolver el
problema costaría quizá más de los
beneficios que arrojaría, o tal vez el obtener
la solución tardaría mucho.
• Para resolverlos se debe tomar en cuenta los
costos, tiempo, desgaste del coche, etc, que
tomaría el escoger una u otra ruta.
• Muchas veces la diferencia de llegar del
punto A al D por una u otra ruta es mínima.
A
C
B
Solución de problemas
D
Sergio Fuenlabrada Velázquez, Edna Martha Miranda Chávez
El problema del agente viajero
Para solucionar este tipo de problemas se formar grupos.
A cada unión de nodos (ruta, arco que une a dos nodos) se le
asigna un valor, este puede se puede medir en litros de
gasolina, kilometraje, tiempo o cualquier otra unidad de
medida.
Se agrupan los nodos normalmente por cercanía (nodos zona
norte, centro y sur) y se establece un punto de unión o
conexión entre los grupos.
El problema se ha simplificado ahora se tienen tres grupos
con 11!, 10! Y 11!.
A su vez se puede subdividir un grupo en subgrupos. Tantas
veces como la complejidad del problema disminuya y ayude a
la solución.
Solución de problemas
Sergio Fuenlabrada Velázquez, Edna Martha Miranda Chávez
Descargar

6. Metodología para la solución de problemas