En este proyecto reuniremos los conceptos del curso para construir un planificador de entregas: modelaremos entidades con conjuntos y relaciones, validaremos funciones, analizaremos dependencias como un grafo, calcularemos rutas, optimizaremos una decisión y comunicaremos el resultado con una visualización.
Una empresa debe entregar seis paquetes en distintos puntos de una ciudad. Algunos paquetes tienen prioridad, cada tramo de la red tiene un costo y existen dependencias: por ejemplo, el paquete de refrigeración debe cargarse antes que el paquete frágil. El sistema debe recomendar un orden y una ruta que respete las reglas.
El proyecto no busca construir un sistema de logística completo. Busca demostrar cómo una situación concreta puede pasar de una descripción informal a un modelo matemático, un algoritmo verificable y una interfaz comprensible.
La pregunta central será: ¿cómo transformar relaciones discretas en una recomendación que podamos justificar?
Una especificación precisa evita que el código esconda decisiones importantes. Definimos:
Objetivo: encontrar un recorrido de costo mínimo que visite los puntos necesarios y respete el orden de las dependencias.
Alcance: una única unidad de reparto, sin ventanas horarias, con costos no negativos y todos los puntos conectados.
Restricciones: cada paquete se entrega una vez; una tarea dependiente no puede aparecer antes de su requisito; solo se recorren conexiones existentes.
Resultado verificable: el sistema devuelve una secuencia, una ruta, un costo y una lista de reglas comprobadas.
Estas decisiones son parte del modelo, no simples detalles de implementación. Si se permiten múltiples vehículos, costos negativos o ventanas de tiempo, cambia el problema y deben cambiar los algoritmos.
El proyecto utiliza varias estructuras matemáticas:
Una misma aplicación puede contener relaciones de naturalezas diferentes. No debemos mezclarlas: una dependencia entre paquetes no es una carretera entre puntos. El código puede usar objetos distintos aunque ambos se almacenen como pares.
const paquetes = [
{ id: 'A', ubicacion: 'Norte', prioridad: 3 },
{ id: 'B', ubicacion: 'Centro', prioridad: 2 },
{ id: 'C', ubicacion: 'Este', prioridad: 1 },
{ id: 'D', ubicacion: 'Oeste', prioridad: 2 },
{ id: 'E', ubicacion: 'Sur', prioridad: 1 },
{ id: 'F', ubicacion: 'Centro', prioridad: 3 }
];
const dependencias = [['A', 'B'], ['C', 'D'], ['B', 'E']];
const conexiones = [
['Depósito', 'Norte', 4], ['Depósito', 'Centro', 3],
['Norte', 'Este', 2], ['Centro', 'Este', 2],
['Centro', 'Oeste', 3], ['Este', 'Sur', 4], ['Oeste', 'Sur', 2]
];
console.log('Paquetes:', paquetes.length);
console.log('Dependencias:', dependencias.length);
console.log('Conexiones de la red:', conexiones.length);
console.log('Ubicación del paquete A:', paquetes.find(p => p.id === 'A').ubicacion);Antes de buscar una solución, verificamos que los datos representen realmente las estructuras declaradas. Una ubicación es función si cada paquete tiene una única ubicación. Las dependencias deben referirse a paquetes existentes y no deben contener ciclos si se exige un orden lineal.
function validarUbicaciones(paquetes) {
const ids = new Set();
for (const paquete of paquetes) {
if (ids.has(paquete.id)) return 'Hay identificadores repetidos';
if (!paquete.ubicacion) return `Falta ubicación para ${paquete.id}`;
ids.add(paquete.id);
}
return null;
}
function validarDependencias(paquetes, relaciones) {
const ids = new Set(paquetes.map(p => p.id));
for (const [antes, despues] of relaciones) {
if (!ids.has(antes) || !ids.has(despues)) return 'Dependencia desconocida';
if (antes === despues) return 'Una tarea no puede depender de sí misma';
}
return null;
}
const paquetesDePrueba = [
{ id: 'A', ubicacion: 'Norte' },
{ id: 'B', ubicacion: 'Centro' },
{ id: 'C', ubicacion: 'Este' }
];
const dependenciasDePrueba = [['A', 'B'], ['B', 'C']];
console.log('Validación de ubicaciones:', validarUbicaciones(paquetesDePrueba) ?? 'correcta');
console.log('Validación de dependencias:', validarDependencias(paquetesDePrueba, dependenciasDePrueba) ?? 'correcta');La validación debe ejecutarse tanto con datos cargados desde un formulario como con datos recibidos de una API. Nunca debemos asumir que una entrada externa ya es correcta.
La relación de dependencia se representa como un grafo dirigido. Si (A, B) pertenece a R, dibujamos A → B. Un orden válido es un orden topológico: cada paquete aparece después de todos sus requisitos.
El algoritmo de Kahn calcula el orden tomando vértices con grado de entrada cero. Al retirar un vértice, disminuye el grado de entrada de sus sucesores. Si al final quedan vértices sin retirar, existe un ciclo y no hay orden válido.
function ordenTopologico(nodos, relaciones) {
const grado = Object.fromEntries(nodos.map(n => [n, 0]));
const salidas = Object.fromEntries(nodos.map(n => [n, []]));
relaciones.forEach(([u, v]) => { salidas[u].push(v); grado[v]++; });
const disponibles = nodos.filter(n => grado[n] === 0);
const orden = [];
while (disponibles.length) {
const u = disponibles.shift();
orden.push(u);
salidas[u].forEach(v => {
grado[v]--;
if (grado[v] === 0) disponibles.push(v);
});
}
return orden.length === nodos.length ? orden : null;
}
const orden = ordenTopologico(
['A', 'B', 'C', 'D'],
[['A', 'B'], ['A', 'C'], ['B', 'D'], ['C', 'D']]
);
console.log('Orden topológico calculado:', orden.join(' → '));El orden puede no ser único. Si hay varias tareas disponibles, podemos elegir por prioridad, por cercanía o por fecha límite. Esa segunda decisión constituye una optimización dentro del conjunto de órdenes válidos.
La visualización debe mostrar tanto la estructura como el resultado. En el grafo siguiente, los nodos son puntos de la ciudad y las etiquetas de las aristas son costos. La ruta recomendada se resalta, pero el texto inferior informa explícitamente la secuencia y el costo.
Una interfaz integradora puede incluir una tabla con los paquetes, un diagrama de dependencias y este mapa. Cada vista debe consultar el mismo modelo: si se duplican los datos para cada pantalla, pueden aparecer contradicciones.
Con costos no negativos, Dijkstra obtiene la ruta de menor costo desde el depósito. Para reconstruir el recorrido no basta con guardar la distancia: hay que guardar también el predecesor de cada nodo. Al llegar al destino, seguimos esos predecesores hacia atrás.
function reconstruirRuta(anterior, destino) {
const ruta = [];
let actual = destino;
while (actual !== undefined) {
ruta.unshift(actual);
actual = anterior[actual];
}
return ruta;
}
// Invariante: distancia[v] es el mejor costo conocido al comienzo
// de cada iteración. La relajación solo lo reemplaza por un valor menor.
const predecesor = { Norte: 'Depósito', Centro: 'Depósito', Este: 'Norte', Sur: 'Este' };
console.log('Ruta reconstruida:', reconstruirRuta(predecesor, 'Sur').join(' → '));El algoritmo resuelve una ruta entre puntos, pero todavía falta relacionarla con los paquetes. La función ubicación convierte cada paquete en un punto; después podemos recorrer los puntos del orden topológico y concatenar rutas. Si dos paquetes comparten ubicación, se evita repetir el desplazamiento.
Una primera versión del planificador puede seguir este procedimiento:
Esta versión es una heurística: la prioridad puede producir un recorrido más caro que otro orden factible. La ventaja es que es fácil de explicar y rápida. Una versión avanzada podría comparar varias órdenes, usar programación dinámica o aplicar una búsqueda con poda.
function planificar(paquetes, dependencias, conexiones) {
const orden = ordenTopologico(paquetes.map(p => p.id), dependencias);
if (!orden) throw new Error('No existe un orden: hay un ciclo');
const prioridad = new Map(paquetes.map(p => [p.id, p.prioridad]));
orden.sort((a, b) => prioridad.get(b) - prioridad.get(a));
const puntos = orden.map(id => paquetes.find(p => p.id === id).ubicacion);
return { ordenPaquetes: orden, puntos, conexiones };
}
function ordenTopologico(nodos, relaciones) {
const grado = Object.fromEntries(nodos.map(n => [n, 0]));
const salidas = Object.fromEntries(nodos.map(n => [n, []]));
relaciones.forEach(([u, v]) => { salidas[u].push(v); grado[v]++; });
const disponibles = nodos.filter(n => grado[n] === 0);
const orden = [];
while (disponibles.length) {
const u = disponibles.shift();
orden.push(u);
salidas[u].forEach(v => { grado[v]--; if (grado[v] === 0) disponibles.push(v); });
}
return orden.length === nodos.length ? orden : null;
}
const plan = planificar(
[{ id: 'A', ubicacion: 'Norte', prioridad: 2 },
{ id: 'B', ubicacion: 'Centro', prioridad: 1 },
{ id: 'C', ubicacion: 'Sur', prioridad: 3 }],
[['A', 'B']],
[['Norte', 'Centro', 4], ['Centro', 'Sur', 3]]
);
console.log('Orden planificado:', plan.ordenPaquetes.join(' → '));
console.log('Puntos a visitar:', plan.puntos.join(' → '));En una aplicación real, el planificador debería devolver también la razón de cada decisión. La trazabilidad es una propiedad importante: permite corregir datos, explicar una recomendación y detectar cuándo una regla de negocio no fue representada.
Las pruebas deben verificar propiedades matemáticas, casos normales y casos límite. No alcanza con probar el ejemplo feliz.
| Caso | Resultado esperado | Concepto comprobado |
|---|---|---|
| Paquete sin ubicación | Error de validación | Función ubicación bien definida |
| Dependencia desconocida | Error de referencia | Relación sobre el conjunto correcto |
| Ciclo A → B → A | No existe orden topológico | Aciclicidad y transitividad operativa |
| Punto aislado | Ruta infinita o no disponible | Conectividad del grafo |
| Dos rutas con igual costo | Cualquiera de las óptimas, con criterio documentado | Relación de equivalencia de costos |
| Paquetes en el mismo punto | Una visita puede cubrir ambos | Función no necesariamente inyectiva |
function afirmar(condicion, mensaje) {
if (!condicion) throw new Error(`Prueba fallida: ${mensaje}`);
}
function ordenTopologico(nodos, relaciones) {
const grado = Object.fromEntries(nodos.map(n => [n, 0]));
const salidas = Object.fromEntries(nodos.map(n => [n, []]));
relaciones.forEach(([u, v]) => { salidas[u].push(v); grado[v]++; });
const disponibles = nodos.filter(n => grado[n] === 0);
const orden = [];
while (disponibles.length) {
const actual = disponibles.shift();
orden.push(actual);
salidas[actual].forEach(v => { grado[v]--; if (grado[v] === 0) disponibles.push(v); });
}
return orden.length === nodos.length ? orden : null;
}
const orden = ordenTopologico(['A', 'B', 'C'], [['A', 'B'], ['B', 'C']]);
afirmar(orden.indexOf('A') < orden.indexOf('B'), 'A debe preceder a B');
afirmar(orden.indexOf('B') < orden.indexOf('C'), 'B debe preceder a C');
afirmar(ordenTopologico(['A', 'B'], [['A', 'B'], ['B', 'A']]) === null, 'el ciclo debe detectarse');
console.log('Prueba 1: orden de dependencias correcto');
console.log('Prueba 2: ciclo detectado correctamente');El análisis del proyecto debe incluir límites. Ordenar dependencias con Kahn cuesta O(V + E). Dijkstra con una cola de prioridad cuesta aproximadamente O((V + E) log V). Si probamos todos los órdenes posibles de n paquetes, el costo puede crecer como O(n!).
También hay responsabilidades que no son matemáticas pero sí forman parte de un sistema correcto:
innerHTML; usar nodos de texto o escapar valores.Un proyecto integrador evalúa tanto la respuesta como la calidad de la explicación. La complejidad, la seguridad y la accesibilidad son parte del diseño, no tareas posteriores.
Cuando el proyecto crece, conviene separar el código por responsabilidades:
// En una aplicación real, cada función viviría en su propio módulo.
function cargarModelo() {
return { paquetes: ['A', 'B', 'C'], dependencias: [['A', 'B']] };
}
function validarModelo(modelo) {
return modelo.paquetes.length > 0 ? [] : ['No hay paquetes'];
}
function planificar(modelo) {
return { orden: ['A', 'B', 'C'], total: modelo.paquetes.length };
}
function mostrarResultado(resultado) {
console.log('Resultado del módulo controlador:', resultado);
}
const modelo = cargarModelo();
const errores = validarModelo(modelo);
if (errores.length) mostrarResultado({ errores });
else mostrarResultado(planificar(modelo));La separación permite reemplazar la interfaz sin cambiar los algoritmos y probar cada función con entradas pequeñas. Es una aplicación directa de una idea relacional: cada módulo recibe datos y produce una salida con un contrato claro.
Una vez terminada la versión base, el proyecto puede crecer de forma controlada:
Cada ampliación debe comenzar con una nueva especificación: qué conjunto aparece, qué relación se agrega, qué función cambia y qué pruebas garantizan que la versión anterior siga funcionando.
Construye tu propia variante del planificador o cambia el dominio: prerrequisitos de materias, red de transporte, recomendaciones de cursos, dependencias de tareas o asignación de recursos.
| Criterio | Pregunta orientadora |
|---|---|
| Modelo | ¿Los conjuntos, funciones y relaciones representan el problema sin ambigüedad? |
| Validación | ¿Detecta referencias inválidas, duplicados, ciclos y ausencia de solución? |
| Algoritmos | ¿Se explica por qué cada algoritmo es aplicable y cuál es su complejidad? |
| Correctitud | ¿Las pruebas comprueban invariantes y casos límite? |
| Interfaz | ¿La visualización muestra datos, resultado, costo y mensajes comprensibles? |
| Comunicación | ¿El usuario puede saber por qué se eligió la solución? |
Como entrega final, incluye una descripción del problema, el modelo formal, ejemplos de entrada y salida, decisiones de diseño, complejidad, limitaciones y posibles mejoras. El código debe poder ejecutarse con un conjunto de datos de prueba.
Las relaciones y funciones discretas aparecen cada vez que un programa conecta elementos, transforma entradas, organiza dependencias o decide entre alternativas. Lo que comienza como una definición matemática se convierte en una estructura de datos, un algoritmo y una interfaz.
El recorrido del curso nos llevó desde las propiedades básicas de las relaciones hasta sus aplicaciones en programación, bases de datos, grafos, inteligencia artificial, criptografía, visualización y optimización. El proyecto integrador muestra que esos conceptos no viven aislados: se combinan para construir soluciones que pueden verificarse y mejorarse.
Modelar con precisión, analizar con rigor y comunicar con claridad: esa es la habilidad que este curso deja como herramienta para programar.