Semana 5 — Huffman y Dijkstra, demostrados
Objetivos
- Demostrar que Huffman da un código óptimo.
- Demostrar que Dijkstra es correcto con pesos no negativos.
- Modelar un problema con restricciones como caminos mínimos sobre un grafo de estados.
Sesión A — Huffman demostrado · Minimizar el retraso máximo
Lectura: Apuntes, semana 5.
Apoyo: Erickson, sec. 4.4 (Huffman Codes). CLRS, capítulo Greedy Algorithms, 4.ª edición.
Temas:
- Minimizar el retraso máximo: atender primero el plazo más cercano. Demostración con inversiones adyacentes, que retoma las inversiones de la semana 2.
- Huffman, construido en Estructuras de Datos: unir los dos árboles menos frecuentes.
- Costo de un código como suma de frecuencia por profundidad.
- Primer paso: existe un código óptimo donde los dos símbolos menos frecuentes son hermanos en el nivel más profundo. Intercambio.
- Segundo paso: inducción sobre el número de símbolos, reemplazando esos dos por uno.
- Error común: creer que el intercambio ya termina la demostración, que todavía necesita la inducción.
Sesión B — Dijkstra demostrado
Lectura: Apuntes, semana 5.
Apoyo: Erickson, secs. 8.3 (The Only SSSP Algorithm) y 8.6 (Best-First: Dijkstra’s Algorithm). CLRS, capítulo Single-Source Shortest Paths, 4.ª edición.
Temas:
- Dijkstra, ya conocido, como greedy: fijar para siempre el nodo con la menor distancia conocida.
- Invariante: para cada nodo fijado, su distancia es la del camino mínimo. Demostración por inducción sobre los nodos fijados.
- Dónde se usa exactamente que los pesos no sean negativos, con el contraejemplo.
- El grafo de estados: si importa algo más que el nodo, ese algo entra en el nodo. Ejemplo: (ciudad, peajes usados).
- Costo en el grafo de estados: con k peajes hay V·(k + 1) nodos y a lo sumo E·(k + 1) arcos, si E cuenta arcos dirigidos: una carretera de doble sentido son dos.
- Error común: modelar los peajes con un contador global y no como parte del estado.
Laboratorio — Rutas con a lo sumo k peajes
- Dada una red de ciudades con carreteras, algunas con peaje, calcular la distancia mínima entre dos ciudades pasando por a lo sumo k peajes.
- Mostrar con un ejemplo pequeño por qué Dijkstra sobre las ciudades no alcanza.
- Construir el grafo de estados y correr Dijkstra sobre él, con
std::priority_queue. - Imprimir -1 cuando no haya ruta. Pasar todos los casos.
- Extensión: cambiar a un solo cupón que deja gratis una carretera, usando la misma idea.
Preguntas de repaso
- Demuestren que, en un código óptimo, un símbolo más frecuente no puede estar más profundo que uno menos frecuente.
- Con frecuencias 1, 1, 2, 3, 5, 8, ¿qué árbol da Huffman y cuál es su costo total?
- ¿En qué paso exacto falla la demostración de Dijkstra si hay una arista negativa?
- ¿Sirve sumar una constante a todos los pesos para eliminar aristas negativas? Den un contraejemplo.
- En el grafo de estados con k peajes, ¿cuántos nodos y aristas hay, y cuál es el costo de Dijkstra?
Código de la semana
Compilar y probar dentro del contenedor del curso con make y make test.
Ejemplos (16)Pruebas (1)Laboratorio (3)Compilación (1)
Ejemplos
Los programas que usan los apuntes y la clase.
// Dijkstra paso a paso: cómo queda d tras cada entrada, y la verdad del árbitro al lado.
#include <iomanip>
#include <iostream>
#include <string>
#include <vector>
#include "shortest_paths.h"
int main() {
Graph graph(6);
add_arc(graph, 0, 1, 4);
add_arc(graph, 0, 2, 1);
add_arc(graph, 2, 1, 2);
add_arc(graph, 2, 3, 7);
add_arc(graph, 1, 3, 3);
add_arc(graph, 3, 4, 0);
add_arc(graph, 4, 2, 5);
std::vector<long long> truth = relax_until_stable(graph, 0);
DijkstraResult result = dijkstra(graph, 0);
std::vector<long long> d(graph.size(), UNREACHABLE);
d[0] = 0;
std::size_t next_change = 0;
std::cout << "sale qué pasa d[0] d[1] d[2] d[3] d[4] d[5] verdad\n";
for (std::size_t i = 0; i < result.pops.size(); i++) {
const Pop& pop = result.pops[i];
while (next_change < result.changes.size() && result.changes[next_change].pop == i) {
const Change& change = result.changes[next_change];
d[static_cast<std::size_t>(change.node)] = change.value;
next_change++;
}
std::string entry = "(" + std::to_string(pop.distance) + "," + std::to_string(pop.node) + ")";
std::cout << std::left << std::setw(8) << entry
<< (pop.stale ? std::string("vieja ") : "fija al " + std::to_string(pop.node) + " ") << std::right;
for (long long value : d) {
std::cout << std::setw(5) << (value == UNREACHABLE ? std::string("inf") : std::to_string(value));
}
if (!pop.stale) {
std::cout << std::setw(6) << truth[static_cast<std::size_t>(pop.node)];
}
std::cout << '\n';
}
}// Dos ideas parecidas a Dijkstra, contra el árbitro.
#include <iostream>
#include <vector>
#include "shortest_paths.h"
int main() {
Graph first(3);
add_arc(first, 0, 1, 4);
add_arc(first, 0, 2, 1);
add_arc(first, 2, 1, 2);
std::cout << "0 -> 1 (4), 0 -> 2 (1), 2 -> 1 (2). Distancia a 1:\n";
std::cout << " fijar al descubrir: " << fix_on_discovery(first, 0)[1] << '\n';
std::cout << " Dijkstra: " << dijkstra(first, 0).distance[1] << '\n';
std::cout << " árbitro: " << relax_until_stable(first, 0)[1] << '\n';
Graph second(4);
add_arc(second, 0, 1, 1);
add_arc(second, 1, 3, 10);
add_arc(second, 0, 2, 2);
add_arc(second, 2, 3, 2);
std::cout << "0 -> 1 (1), 1 -> 3 (10), 0 -> 2 (2), 2 -> 3 (2). Distancia a 3:\n";
std::cout << " arco más barato: " << cheapest_arc_walk(second, 0, 3) << '\n';
std::cout << " Dijkstra: " << dijkstra(second, 0).distance[3] << '\n';
std::cout << " árbitro: " << relax_until_stable(second, 0)[3] << '\n';
}// Dos choferes se turnan en cada tramo, y debe llegar manejando el que salió:
// el número de tramos tiene que ser par.
#include <iostream>
#include <vector>
#include "shortest_paths.h"
#include "state_graph.h"
namespace {
void two_way(Graph& graph, int a, int b, long long weight) {
add_arc(graph, a, b, weight);
add_arc(graph, b, a, weight);
}
} // namespace
int main() {
Graph line(6);
two_way(line, 0, 1, 2);
two_way(line, 1, 2, 2);
two_way(line, 2, 3, 2);
DijkstraResult cities = dijkstra(line, 0);
std::cout << "sin la regla: " << cities.distance[3] << " por";
for (int node : path_to(cities.parent, 0, 3)) std::cout << ' ' << node;
std::cout << '\n';
WalkResult on_line = min_walk_multiple(line, 0, 3, 2);
std::cout << "con número par de tramos, solo la línea: "
<< (on_line.distance == UNREACHABLE ? "no hay recorrido" : "hay recorrido") << '\n';
Graph graph = line;
two_way(graph, 1, 4, 1);
two_way(graph, 4, 5, 1);
two_way(graph, 5, 1, 1);
WalkResult even = min_walk_multiple(graph, 0, 3, 2);
std::cout << "con número par de tramos, con el triángulo: " << even.distance << " por";
for (int node : even.walk) std::cout << ' ' << node;
std::cout << '\n';
}// Ideas para armar un código, contra la búsqueda exhaustiva, y el efecto de los empates.
#include <iostream>
#include <string>
#include <vector>
#include "huffman.h"
namespace {
void print_list(const std::vector<int>& values) {
for (int value : values) std::cout << ' ' << value;
}
void compare(const std::vector<long long>& freq) {
std::cout << "frecuencias:";
for (long long value : freq) std::cout << ' ' << value;
std::vector<int> split = top_down_split(freq);
std::vector<int> chain = chain_code(freq);
HuffmanResult result = huffman(freq);
std::cout << "\n mejor árbol, por búsqueda exhaustiva: " << brute_min_cost(freq);
std::cout << "\n dividir parejo: " << code_cost(freq, split) << " profundidades";
print_list(split);
std::cout << "\n en cadena : " << code_cost(freq, chain) << " profundidades";
print_list(chain);
std::cout << "\n Huffman : " << code_cost(freq, result.depth) << " profundidades";
print_list(result.depth);
std::cout << '\n';
}
void ties(const std::vector<long long>& freq) {
std::cout << "frecuencias:";
for (long long value : freq) std::cout << ' ' << value;
std::cout << '\n';
for (const std::vector<int>& depth : huffman_all_ties(freq)) {
std::cout << " profundidades";
print_list(depth);
std::cout << " costo " << code_cost(freq, depth) << '\n';
}
}
} // namespace
int main() {
compare({15, 7, 6, 6, 5});
compare({1, 1, 1, 1, 1, 1, 1, 1});
std::cout << "\nTodas las formas de romper los empates:\n";
ties({1, 1, 2, 2});
ties({1, 1, 2, 3, 5, 8});
}// La demostración de Huffman, con números: el intercambio y la inducción.
#include <algorithm>
#include <iomanip>
#include <iostream>
#include <string>
#include <utility>
#include <vector>
#include "huffman.h"
namespace {
void print_depths(const std::vector<long long>& freq, const std::vector<int>& depth, const std::string& label) {
std::cout << label << " profundidades";
for (int value : depth) std::cout << ' ' << value;
std::cout << " costo " << code_cost(freq, depth) << '\n';
}
void exchange() {
std::vector<long long> freq = {1, 2, 3, 4};
std::vector<int> depth = {1, 2, 3, 3};
std::cout << "Intercambio, con frecuencias 1 2 3 4:\n";
print_depths(freq, depth, " árbol inicial: ");
std::swap(depth[0], depth[2]);
print_depths(freq, depth, " cambia 1 con 3: ");
std::swap(depth[1], depth[3]);
print_depths(freq, depth, " cambia 2 con 4: ");
print_depths(freq, huffman(freq).depth, " Huffman: ");
}
void induction(std::vector<long long> freq) {
std::cout << "\nInducción, reemplazando los dos menores por su suma:\n";
std::cout << "alfabeto x y costo = costo del siguiente + x + y\n";
std::vector<std::vector<long long>> alphabets;
std::vector<long long> costs;
std::vector<long long> current = freq;
while (current.size() >= 2) {
alphabets.push_back(current);
costs.push_back(code_cost(current, huffman(current).depth));
std::sort(current.begin(), current.end());
long long joined = current[0] + current[1];
current.erase(current.begin(), current.begin() + 2);
current.push_back(joined);
}
for (std::size_t i = 0; i < alphabets.size(); i++) {
std::vector<long long> sorted = alphabets[i];
std::sort(sorted.begin(), sorted.end());
std::string text;
for (long long value : sorted) text += std::to_string(value) + " ";
std::cout << std::left << std::setw(22) << text << std::right << std::setw(4) << sorted[0] << std::setw(4)
<< sorted[1] << std::setw(7) << costs[i] << " = ";
long long next = i + 1 < alphabets.size() ? costs[i + 1] : 0;
std::cout << next << " + " << sorted[0] << " + " << sorted[1] << '\n';
}
}
} // namespace
int main() {
exchange();
induction({1, 1, 2, 3, 5, 8});
}// Códigos sin prefijos comunes: Huffman, ideas que fallan y un árbitro exhaustivo.
#pragma once
#include <algorithm>
#include <cstddef>
#include <functional>
#include <limits>
#include <numeric>
#include <queue>
#include <set>
#include <utility>
#include <vector>
// Costo de un código: suma de frecuencia por profundidad.
inline long long code_cost(const std::vector<long long>& freq, const std::vector<int>& depth) {
long long total = 0;
for (std::size_t i = 0; i < freq.size(); i++) {
total += freq[i] * depth[i];
}
return total;
}
struct HuffmanResult {
std::vector<int> depth; // profundidad de cada símbolo
std::vector<std::pair<long long, long long>> merges; // los dos pesos de cada unión
};
// Requiere al menos dos símbolos, todos con frecuencia positiva.
// A igual peso, sale primero el árbol creado antes.
inline HuffmanResult huffman(const std::vector<long long>& freq) {
using Entry = std::pair<long long, int>;
std::vector<int> parent(freq.size(), -1);
std::priority_queue<Entry, std::vector<Entry>, std::greater<Entry>> heap;
for (std::size_t i = 0; i < freq.size(); i++) {
heap.push({freq[i], static_cast<int>(i)});
}
HuffmanResult result;
while (heap.size() >= 2) {
Entry first = heap.top();
heap.pop();
Entry second = heap.top();
heap.pop();
int node = static_cast<int>(parent.size());
parent.push_back(-1);
parent[static_cast<std::size_t>(first.second)] = node;
parent[static_cast<std::size_t>(second.second)] = node;
result.merges.push_back({first.first, second.first});
heap.push({first.first + second.first, node});
}
for (std::size_t i = 0; i < freq.size(); i++) {
int depth = 0;
for (int node = static_cast<int>(i); parent[static_cast<std::size_t>(node)] != -1;
node = parent[static_cast<std::size_t>(node)]) {
depth++;
}
result.depth.push_back(depth);
}
return result;
}
inline long long merges_total(const std::vector<std::pair<long long, long long>>& merges) {
long long total = 0;
for (const auto& merge : merges) {
total += merge.first + merge.second;
}
return total;
}
// Un árbol lleno sobre n hojas se arma con n - 1 uniones, en algún orden, y cada unión
// baja un nivel todas sus hojas. Esta búsqueda prueba todos los pares en cada paso, sin
// ninguna regla, y llama a visit con las profundidades de cada árbol. Solo con n pequeño.
template <typename Visit>
void all_full_trees(std::vector<std::vector<int>>& groups, std::vector<int>& depth, Visit& visit) {
if (groups.size() == 1) {
visit(depth);
return;
}
for (std::size_t i = 0; i < groups.size(); i++) {
for (std::size_t j = i + 1; j < groups.size(); j++) {
std::vector<std::vector<int>> next;
std::vector<int> joined = groups[i];
joined.insert(joined.end(), groups[j].begin(), groups[j].end());
for (std::size_t g = 0; g < groups.size(); g++) {
if (g != i && g != j) next.push_back(groups[g]);
}
next.push_back(joined);
for (int symbol : joined) depth[static_cast<std::size_t>(symbol)]++;
all_full_trees(next, depth, visit);
for (int symbol : joined) depth[static_cast<std::size_t>(symbol)]--;
}
}
}
inline long long brute_min_cost(const std::vector<long long>& freq) {
std::vector<std::vector<int>> groups;
for (std::size_t i = 0; i < freq.size(); i++) {
groups.push_back({static_cast<int>(i)});
}
std::vector<int> depth(freq.size(), 0);
long long best = std::numeric_limits<long long>::max();
auto visit = [&](const std::vector<int>& d) { best = std::min(best, code_cost(freq, d)); };
all_full_trees(groups, depth, visit);
return best;
}
// Todas las formas de correr Huffman: en cada paso, cualquier par cuyos pesos sean los dos
// menores. Devuelve las profundidades distintas que se pueden obtener.
inline void huffman_ties_rec(const std::vector<long long>& weight, const std::vector<std::vector<int>>& groups,
std::vector<int>& depth, std::set<std::vector<int>>& out) {
if (groups.size() == 1) {
out.insert(depth);
return;
}
std::vector<long long> sorted = weight;
std::sort(sorted.begin(), sorted.end());
for (std::size_t i = 0; i < groups.size(); i++) {
for (std::size_t j = i + 1; j < groups.size(); j++) {
long long low = std::min(weight[i], weight[j]);
long long high = std::max(weight[i], weight[j]);
if (low != sorted[0] || high != sorted[1]) continue;
std::vector<long long> next_weight;
std::vector<std::vector<int>> next_groups;
for (std::size_t g = 0; g < groups.size(); g++) {
if (g != i && g != j) {
next_weight.push_back(weight[g]);
next_groups.push_back(groups[g]);
}
}
std::vector<int> joined = groups[i];
joined.insert(joined.end(), groups[j].begin(), groups[j].end());
next_weight.push_back(low + high);
next_groups.push_back(joined);
for (int symbol : joined) depth[static_cast<std::size_t>(symbol)]++;
huffman_ties_rec(next_weight, next_groups, depth, out);
for (int symbol : joined) depth[static_cast<std::size_t>(symbol)]--;
}
}
}
inline std::set<std::vector<int>> huffman_all_ties(const std::vector<long long>& freq) {
std::vector<std::vector<int>> groups;
for (std::size_t i = 0; i < freq.size(); i++) {
groups.push_back({static_cast<int>(i)});
}
std::vector<int> depth(freq.size(), 0);
std::set<std::vector<int>> out;
huffman_ties_rec(freq, groups, depth, out);
return out;
}
// Idea que falla: dividir de arriba hacia abajo. Se ordena de mayor a menor y se parte la
// lista donde las dos sumas queden más parejas (a igual diferencia, el primer corte).
inline void split_rec(const std::vector<long long>& freq, const std::vector<int>& ids, std::size_t lo, std::size_t hi,
int level, std::vector<int>& depth) {
if (hi - lo == 1) {
depth[static_cast<std::size_t>(ids[lo])] = level;
return;
}
long long total = 0;
for (std::size_t i = lo; i < hi; i++) total += freq[static_cast<std::size_t>(ids[i])];
long long left = 0;
long long best_gap = std::numeric_limits<long long>::max();
std::size_t cut = lo + 1;
for (std::size_t i = lo; i + 1 < hi; i++) {
left += freq[static_cast<std::size_t>(ids[i])];
long long gap = std::max(left, total - left) - std::min(left, total - left);
if (gap < best_gap) {
best_gap = gap;
cut = i + 1;
}
}
split_rec(freq, ids, lo, cut, level + 1, depth);
split_rec(freq, ids, cut, hi, level + 1, depth);
}
inline std::vector<int> top_down_split(const std::vector<long long>& freq) {
std::vector<int> ids(freq.size());
std::iota(ids.begin(), ids.end(), 0);
std::stable_sort(ids.begin(), ids.end(), [&](int a, int b) {
return freq[static_cast<std::size_t>(a)] > freq[static_cast<std::size_t>(b)];
});
std::vector<int> depth(freq.size(), 0);
split_rec(freq, ids, 0, freq.size(), 0, depth);
return depth;
}
// Idea que falla: un código en cadena, 0, 10, 110, ..., con los más frecuentes arriba.
inline std::vector<int> chain_code(const std::vector<long long>& freq) {
std::vector<int> ids(freq.size());
std::iota(ids.begin(), ids.end(), 0);
std::stable_sort(ids.begin(), ids.end(), [&](int a, int b) {
return freq[static_cast<std::size_t>(a)] > freq[static_cast<std::size_t>(b)];
});
std::vector<int> depth(freq.size(), 0);
for (std::size_t i = 0; i < ids.size(); i++) {
depth[static_cast<std::size_t>(ids[i])] = static_cast<int>(std::min(i + 1, ids.size() - 1));
}
return depth;
}// Tres reglas para ordenar tareas, contra la fuerza bruta.
#include <iostream>
#include <string>
#include <vector>
#include "scheduling.h"
namespace {
std::string names(const std::vector<int>& order) {
std::string text;
for (int id : order) {
text += static_cast<char>('A' + id);
}
return text;
}
void compare(const std::string& title, const std::vector<Job>& jobs) {
std::cout << title << "\n tareas (duración, plazo):";
for (std::size_t i = 0; i < jobs.size(); i++) {
std::cout << ' ' << static_cast<char>('A' + static_cast<int>(i)) << '(' << jobs[i].duration << ", "
<< jobs[i].deadline << ')';
}
std::cout << "\n óptimo por fuerza bruta: " << brute_min_max_lateness(jobs) << '\n';
std::vector<int> by_duration = order_by_duration(jobs);
std::vector<int> by_slack = order_by_slack(jobs);
std::vector<int> by_deadline = order_by_deadline(jobs);
std::cout << " dura menos : " << max_lateness(jobs, by_duration) << " orden " << names(by_duration) << '\n';
std::cout << " menos holgura: " << max_lateness(jobs, by_slack) << " orden " << names(by_slack) << '\n';
std::cout << " plazo antes : " << max_lateness(jobs, by_deadline) << " orden " << names(by_deadline) << '\n';
}
} // namespace
int main() {
compare("Contra dura menos:", {{1, 100}, {10, 10}});
compare("Contra menos holgura:", {{1, 2}, {10, 10}});
}// El ejemplo de cinco tareas: el orden por plazo y los intercambios de la demostración.
#include <iomanip>
#include <iostream>
#include <string>
#include <vector>
#include "scheduling.h"
namespace {
const std::vector<Job> JOBS = {{3, 5}, {2, 4}, {1, 7}, {4, 9}, {2, 9}};
std::string names(const std::vector<int>& order) {
std::string text;
for (int id : order) {
text += static_cast<char>('A' + id);
}
return text;
}
void print_schedule(const std::vector<int>& order) {
std::cout << "tarea duración plazo fin retraso\n";
long long now = 0;
for (int id : order) {
const Job& job = JOBS[static_cast<std::size_t>(id)];
now += job.duration;
std::cout << " " << static_cast<char>('A' + id) << std::setw(10) << job.duration << std::setw(7)
<< job.deadline << std::setw(5) << now << std::setw(9) << now - job.deadline << '\n';
}
std::cout << "retraso máximo: " << max_lateness(JOBS, order) << "\n\n";
}
} // namespace
int main() {
std::vector<int> by_deadline = order_by_deadline(JOBS);
print_schedule(by_deadline);
print_schedule({1, 0, 2, 4, 3}); // D y E, con el mismo plazo, al revés
std::vector<int> order = {3, 2, 4, 0, 1};
std::cout << "orden inversiones retraso máximo se cambia\n";
while (true) {
std::size_t i = first_adjacent_inversion(JOBS, order);
std::cout << names(order) << std::setw(10) << count_inversions(JOBS, order) << std::setw(14)
<< max_lateness(JOBS, order);
if (i == order.size()) {
std::cout << " ninguna\n";
break;
}
std::cout << " " << static_cast<char>('A' + order[i]) << static_cast<char>('A' + order[i + 1]) << '\n';
std::swap(order[i], order[i + 1]);
}
// Cambiar dos tareas que no son vecinas sí puede empeorar: las del medio se corren.
const std::vector<Job> far = {{1, 5}, {1, 2}, {5, 4}};
std::cout << "\nX(1, 5) M(1, 2) Y(5, 4)\n";
std::cout << "orden XMY: retraso máximo " << max_lateness(far, {0, 1, 2}) << '\n';
std::cout << "orden YMX: retraso máximo " << max_lateness(far, {2, 1, 0}) << '\n';
}// Una arista negativa: el paso de la demostración que deja de valer, con números.
#include <iostream>
#include <vector>
#include "shortest_paths.h"
int main() {
Graph graph(4);
add_arc(graph, 0, 1, 1);
add_arc(graph, 0, 2, 4);
add_arc(graph, 2, 1, -5);
add_arc(graph, 1, 3, 2);
std::vector<long long> truth = relax_until_stable(graph, 0);
DijkstraResult result = dijkstra(graph, 0);
std::cout << "se fija con distancia verdad\n";
for (const Pop& pop : result.pops) {
if (pop.stale) continue;
std::cout << " " << pop.node << " " << pop.distance << " "
<< truth[static_cast<std::size_t>(pop.node)];
if (pop.distance != truth[static_cast<std::size_t>(pop.node)]) std::cout << " se rompió el invariante";
std::cout << '\n';
}
std::cout << "al final, Dijkstra:";
for (long long value : result.distance) std::cout << ' ' << value;
std::cout << "\nal final, árbitro: ";
for (long long value : truth) std::cout << ' ' << value;
std::cout << '\n';
}// Minimizar el retraso máximo en una sola máquina, sin tiempo muerto.
#pragma once
#include <algorithm>
#include <cstddef>
#include <limits>
#include <numeric>
#include <vector>
struct Job {
long long duration;
long long deadline;
};
// Un horario es un orden de las tareas: la primera empieza en 0 y cada una empieza
// cuando termina la anterior. retraso = fin - plazo, negativo si terminó con holgura.
inline std::vector<long long> latenesses(const std::vector<Job>& jobs, const std::vector<int>& order) {
std::vector<long long> result;
long long now = 0;
for (int id : order) {
const Job& job = jobs[static_cast<std::size_t>(id)];
now += job.duration;
result.push_back(now - job.deadline);
}
return result;
}
inline long long max_lateness(const std::vector<Job>& jobs, const std::vector<int>& order) {
std::vector<long long> values = latenesses(jobs, order);
return *std::max_element(values.begin(), values.end());
}
// Una inversión es un par con la tarea de plazo mayor antes, estrictamente:
// dos tareas con el mismo plazo no forman una inversión.
inline bool inverted(const std::vector<Job>& jobs, int first, int second) {
return jobs[static_cast<std::size_t>(first)].deadline > jobs[static_cast<std::size_t>(second)].deadline;
}
inline int count_inversions(const std::vector<Job>& jobs, const std::vector<int>& order) {
int count = 0;
for (std::size_t i = 0; i < order.size(); i++) {
for (std::size_t j = i + 1; j < order.size(); j++) {
if (inverted(jobs, order[i], order[j])) count++;
}
}
return count;
}
// Posición de la primera inversión adyacente, o order.size() si no hay.
inline std::size_t first_adjacent_inversion(const std::vector<Job>& jobs, const std::vector<int>& order) {
for (std::size_t i = 0; i + 1 < order.size(); i++) {
if (inverted(jobs, order[i], order[i + 1])) return i;
}
return order.size();
}
// Ordena las tareas según una clave; a igual clave, se conserva el orden de la lista.
template <typename Key>
std::vector<int> order_by(const std::vector<Job>& jobs, Key key) {
std::vector<int> order(jobs.size());
std::iota(order.begin(), order.end(), 0);
std::stable_sort(order.begin(), order.end(), [&](int a, int b) {
return key(jobs[static_cast<std::size_t>(a)]) < key(jobs[static_cast<std::size_t>(b)]);
});
return order;
}
inline std::vector<int> order_by_deadline(const std::vector<Job>& jobs) {
return order_by(jobs, [](const Job& job) { return job.deadline; });
}
inline std::vector<int> order_by_duration(const std::vector<Job>& jobs) {
return order_by(jobs, [](const Job& job) { return job.duration; });
}
inline std::vector<int> order_by_slack(const std::vector<Job>& jobs) {
return order_by(jobs, [](const Job& job) { return job.deadline - job.duration; });
}
// El árbitro: prueba todas las permutaciones. Solo sirve con n pequeño.
inline long long brute_min_max_lateness(const std::vector<Job>& jobs) {
std::vector<int> order(jobs.size());
std::iota(order.begin(), order.end(), 0);
long long best = std::numeric_limits<long long>::max();
do {
best = std::min(best, max_lateness(jobs, order));
} while (std::next_permutation(order.begin(), order.end()));
return best;
}// ¿Sirve sumar una constante a todos los pesos? Cambia cuál camino gana.
#include <iostream>
#include <vector>
#include "shortest_paths.h"
namespace {
long long path_weight(const Graph& graph, const std::vector<int>& path) {
long long total = 0;
for (std::size_t i = 0; i + 1 < path.size(); i++) {
long long best = UNREACHABLE;
for (const Arc& arc : graph[static_cast<std::size_t>(path[i])]) {
if (arc.to == path[i + 1] && arc.weight < best) best = arc.weight;
}
total += best;
}
return total;
}
void print_path(const std::vector<int>& path) {
for (int node : path) std::cout << node << ' ';
}
} // namespace
int main() {
Graph graph(4);
add_arc(graph, 0, 1, 1);
add_arc(graph, 0, 2, 4);
add_arc(graph, 2, 1, -5);
add_arc(graph, 1, 3, 2);
const long long shift = 5;
Graph shifted(4);
for (std::size_t u = 0; u < graph.size(); u++) {
for (const Arc& arc : graph[u]) {
add_arc(shifted, static_cast<int>(u), arc.to, arc.weight + shift);
}
}
DijkstraResult result = dijkstra(shifted, 0);
std::vector<int> chosen = path_to(result.parent, 0, 3);
std::vector<int> real = {0, 2, 1, 3};
std::cout << "se suma " << shift << " a cada peso\n";
std::cout << "camino que gana tras sumar: ";
print_path(chosen);
std::cout << " pesa " << path_weight(shifted, chosen) << " con la suma, " << path_weight(graph, chosen)
<< " sin ella\n";
std::cout << "camino mínimo original: ";
print_path(real);
std::cout << " pesa " << path_weight(shifted, real) << " con la suma, " << path_weight(graph, real)
<< " sin ella\n";
std::cout << "árbitro, grafo original, distancia a 3: " << relax_until_stable(graph, 0)[3] << '\n';
}// Caminos mínimos en un grafo dirigido: Dijkstra con entradas viejas, y un árbitro lento.
#pragma once
#include <cstddef>
#include <functional>
#include <limits>
#include <queue>
#include <utility>
#include <vector>
struct Arc {
int to;
long long weight;
};
using Graph = std::vector<std::vector<Arc>>;
inline const long long UNREACHABLE = std::numeric_limits<long long>::max();
inline void add_arc(Graph& graph, int from, int to, long long weight) {
graph[static_cast<std::size_t>(from)].push_back({to, weight});
}
struct Pop {
long long distance;
int node;
bool stale; // el nodo ya estaba fijado: esta entrada se ignora
};
// Una mejora de d[node], hecha al atender la entrada número pop.
struct Change {
std::size_t pop;
int node;
long long value;
};
struct DijkstraResult {
std::vector<long long> distance;
std::vector<int> parent;
std::vector<Pop> pops;
std::vector<Change> changes;
};
// Invariante: todo nodo fijado tiene ya su distancia de camino mínimo, si los pesos no son negativos.
inline DijkstraResult dijkstra(const Graph& graph, int source) {
using Entry = std::pair<long long, int>;
std::size_t n = graph.size();
DijkstraResult result{std::vector<long long>(n, UNREACHABLE), std::vector<int>(n, -1), {}, {}};
std::vector<bool> fixed(n, false);
std::priority_queue<Entry, std::vector<Entry>, std::greater<Entry>> heap;
result.distance[static_cast<std::size_t>(source)] = 0;
heap.push({0, source});
while (!heap.empty()) {
auto [d, u] = heap.top();
heap.pop();
std::size_t index = static_cast<std::size_t>(u);
result.pops.push_back({d, u, fixed[index]});
if (fixed[index]) continue;
fixed[index] = true;
for (const Arc& arc : graph[index]) {
std::size_t to = static_cast<std::size_t>(arc.to);
if (d + arc.weight < result.distance[to]) {
result.distance[to] = d + arc.weight;
result.parent[to] = u;
result.changes.push_back({result.pops.size() - 1, arc.to, result.distance[to]});
heap.push({result.distance[to], arc.to});
}
}
}
return result;
}
// Idea que falla: dar por definitiva la primera distancia con la que se descubre un nodo.
// Es BFS con pesos: los nodos se atienden en el orden en que se descubrieron.
inline std::vector<long long> fix_on_discovery(const Graph& graph, int source) {
std::vector<long long> distance(graph.size(), UNREACHABLE);
std::queue<int> pending;
distance[static_cast<std::size_t>(source)] = 0;
pending.push(source);
while (!pending.empty()) {
int u = pending.front();
pending.pop();
for (const Arc& arc : graph[static_cast<std::size_t>(u)]) {
std::size_t to = static_cast<std::size_t>(arc.to);
if (distance[to] == UNREACHABLE) {
distance[to] = distance[static_cast<std::size_t>(u)] + arc.weight;
pending.push(arc.to);
}
}
}
return distance;
}
// Idea que falla: caminar desde el origen tomando siempre el arco más barato hacia un nodo
// no visitado, hasta llegar al destino o quedarse sin salida. Devuelve UNREACHABLE en ese caso.
inline long long cheapest_arc_walk(const Graph& graph, int source, int target) {
std::vector<bool> visited(graph.size(), false);
long long total = 0;
int now = source;
visited[static_cast<std::size_t>(now)] = true;
while (now != target) {
const Arc* best = nullptr;
for (const Arc& arc : graph[static_cast<std::size_t>(now)]) {
if (!visited[static_cast<std::size_t>(arc.to)] && (best == nullptr || arc.weight < best->weight)) {
best = &arc;
}
}
if (best == nullptr) return UNREACHABLE;
total += best->weight;
now = best->to;
visited[static_cast<std::size_t>(now)] = true;
}
return total;
}
// El árbitro: relajar todas las aristas una y otra vez hasta que nada cambie.
// No elige ningún orden, y da la verdad también con pesos negativos si no hay ciclos negativos.
inline std::vector<long long> relax_until_stable(const Graph& graph, int source) {
std::vector<long long> distance(graph.size(), UNREACHABLE);
distance[static_cast<std::size_t>(source)] = 0;
bool changed = true;
while (changed) {
changed = false;
for (std::size_t u = 0; u < graph.size(); u++) {
if (distance[u] == UNREACHABLE) continue;
for (const Arc& arc : graph[u]) {
std::size_t to = static_cast<std::size_t>(arc.to);
if (distance[u] + arc.weight < distance[to]) {
distance[to] = distance[u] + arc.weight;
changed = true;
}
}
}
}
return distance;
}
inline std::vector<int> path_to(const std::vector<int>& parent, int source, int target) {
std::vector<int> reversed;
for (int node = target; node != source; node = parent[static_cast<std::size_t>(node)]) {
reversed.push_back(node);
}
reversed.push_back(source);
return std::vector<int>(reversed.rbegin(), reversed.rend());
}// Cuánto crece Dijkstra con el número de capas, en un grafo al azar de 20 000 ciudades.
// Los conteos no dependen de la máquina. Los tiempos sí: menor de 3 intentos, con -O2.
#include <algorithm>
#include <chrono>
#include <iomanip>
#include <iostream>
#include <random>
#include <vector>
#include "shortest_paths.h"
#include "state_graph.h"
int main() {
std::mt19937 rng(505);
const int cities = 20000;
const int arcs = 100000;
Graph graph(cities);
for (int i = 0; i < arcs; i++) {
int a = static_cast<int>(rng() % cities);
int b = static_cast<int>(rng() % cities);
add_arc(graph, a, b, 1 + static_cast<long long>(rng() % 1000));
}
std::cout << "capas estados sacadas arcos mirados ms\n";
for (int c : {1, 2, 4, 8, 16, 32}) {
double best = 1e18;
WalkResult result{};
for (int attempt = 0; attempt < 3; attempt++) {
auto start = std::chrono::steady_clock::now();
result = min_walk_multiple(graph, 0, 1, c);
auto stop = std::chrono::steady_clock::now();
best = std::min(best, std::chrono::duration<double, std::milli>(stop - start).count());
}
std::cout << std::setw(5) << c << std::setw(11) << cities * c << std::setw(11) << result.pops << std::setw(15)
<< result.relaxations << std::setw(8) << std::fixed << std::setprecision(1) << best << '\n';
}
}// Grafo de estados: lo que hay que recordar entra en el nodo.
// Aquí se recuerda cuántos tramos lleva el recorrido, módulo c.
#pragma once
#include <cstddef>
#include <functional>
#include <queue>
#include <utility>
#include <vector>
#include "shortest_paths.h"
struct WalkResult {
long long distance; // UNREACHABLE si no hay recorrido
std::vector<int> walk; // las ciudades del recorrido, con repeticiones
long long pops; // entradas sacadas del heap
long long relaxations; // arcos del grafo de estados que se miraron
};
// Recorrido mínimo de source a target con un número de tramos múltiplo de c.
// El estado (ciudad, resto) se guarda como ciudad * c + resto. Los arcos no se construyen:
// salen de la lista de la ciudad, y todos van del resto r al resto (r + 1) mod c.
inline WalkResult min_walk_multiple(const Graph& graph, int source, int target, int c) {
using Entry = std::pair<long long, std::size_t>;
std::size_t layers = static_cast<std::size_t>(c);
std::size_t states = graph.size() * layers;
std::vector<long long> distance(states, UNREACHABLE);
std::vector<std::size_t> parent(states, states);
std::vector<bool> fixed(states, false);
std::priority_queue<Entry, std::vector<Entry>, std::greater<Entry>> heap;
std::size_t start = static_cast<std::size_t>(source) * layers;
distance[start] = 0;
heap.push({0, start});
WalkResult result{UNREACHABLE, {}, 0, 0};
while (!heap.empty()) {
auto [d, state] = heap.top();
heap.pop();
result.pops++;
if (fixed[state]) continue;
fixed[state] = true;
std::size_t city = state / layers;
std::size_t next_rest = (state % layers + 1) % layers;
for (const Arc& arc : graph[city]) {
result.relaxations++;
std::size_t next = static_cast<std::size_t>(arc.to) * layers + next_rest;
if (d + arc.weight < distance[next]) {
distance[next] = d + arc.weight;
parent[next] = state;
heap.push({distance[next], next});
}
}
}
std::size_t goal = static_cast<std::size_t>(target) * layers;
result.distance = distance[goal];
if (distance[goal] != UNREACHABLE) {
std::vector<int> reversed;
std::size_t state = goal;
while (state != start) {
reversed.push_back(static_cast<int>(state / layers));
state = parent[state];
}
reversed.push_back(source);
result.walk.assign(reversed.rbegin(), reversed.rend());
}
return result;
}// El ejemplo de los apuntes: cuatro ciudades, k = 1. Los arcos del grafo de estados están
// escritos a mano y Dijkstra corre sobre ellos sin saber qué es un peaje.
#include <iostream>
#include <string>
#include <vector>
#include "shortest_paths.h"
#include "toll_mistakes.h"
namespace {
// El estado (ciudad, peajes usados) se guarda como ciudad * 2 + peajes, con k = 1.
int state(int city, int used) { return city * 2 + used; }
std::string label(int id) {
return "(" + std::to_string(id / 2) + "," + std::to_string(id % 2) + ")";
}
} // namespace
int main() {
Graph layers(8);
// Carretera 0-2 sin peaje, largo 2: una copia en cada capa, en los dos sentidos.
for (int used = 0; used <= 1; used++) {
add_arc(layers, state(0, used), state(2, used), 2);
add_arc(layers, state(2, used), state(0, used), 2);
// Carretera 2-1 sin peaje, largo 3.
add_arc(layers, state(2, used), state(1, used), 3);
add_arc(layers, state(1, used), state(2, used), 3);
}
// Carreteras 0-1 y 1-3 con peaje, largo 1: suben de la capa 0 a la capa 1.
add_arc(layers, state(0, 0), state(1, 1), 1);
add_arc(layers, state(1, 0), state(0, 1), 1);
add_arc(layers, state(1, 0), state(3, 1), 1);
add_arc(layers, state(3, 0), state(1, 1), 1);
DijkstraResult result = dijkstra(layers, state(0, 0));
std::cout << "estado distancia\n";
for (const Pop& pop : result.pops) {
if (!pop.stale) std::cout << label(pop.node) << " " << pop.distance << '\n';
}
std::cout << "a (3,0): ";
if (result.distance[static_cast<std::size_t>(state(3, 0))] == UNREACHABLE) std::cout << "no se llega\n";
std::cout << "a (3,1): " << result.distance[static_cast<std::size_t>(state(3, 1))] << " por";
for (int id : path_to(result.parent, state(0, 0), state(3, 1))) std::cout << ' ' << label(id);
std::cout << '\n';
const std::vector<Road> roads = {{0, 2, 2, false}, {2, 1, 3, false}, {0, 1, 1, true}, {1, 3, 1, true}};
std::cout << "contador global: " << with_global_counter(4, roads, 0, 3, 1) << '\n';
std::cout << "una distancia por ciudad: " << with_one_distance_per_city(4, roads, 0, 3, 1) << '\n';
}// Dos formas equivocadas de contar peajes, para ver dónde fallan. Ninguna es correcta.
#pragma once
#include <cstddef>
#include <functional>
#include <limits>
#include <queue>
#include <tuple>
#include <vector>
struct Road {
int a;
int b;
long long length;
bool toll;
};
struct RoadEnd {
int to;
long long length;
bool toll;
};
inline std::vector<std::vector<RoadEnd>> road_lists(int cities, const std::vector<Road>& roads) {
std::vector<std::vector<RoadEnd>> lists(static_cast<std::size_t>(cities));
for (const Road& road : roads) {
lists[static_cast<std::size_t>(road.a)].push_back({road.b, road.length, road.toll});
lists[static_cast<std::size_t>(road.b)].push_back({road.a, road.length, road.toll});
}
return lists;
}
inline const long long NO_ROUTE = -1;
// Error: un solo contador para toda la búsqueda. Cuenta cada carretera con peaje que se mira,
// sea de la ruta que sea. Cuando llega a k, ya no se mira ninguna otra con peaje.
inline long long with_global_counter(int cities, const std::vector<Road>& roads, int source, int target, int k) {
using Entry = std::pair<long long, int>;
std::vector<std::vector<RoadEnd>> lists = road_lists(cities, roads);
const long long infinity = std::numeric_limits<long long>::max();
std::vector<long long> distance(static_cast<std::size_t>(cities), infinity);
std::vector<bool> fixed(static_cast<std::size_t>(cities), false);
std::priority_queue<Entry, std::vector<Entry>, std::greater<Entry>> heap;
int used = 0;
distance[static_cast<std::size_t>(source)] = 0;
heap.push({0, source});
while (!heap.empty()) {
auto [d, u] = heap.top();
heap.pop();
if (fixed[static_cast<std::size_t>(u)]) continue;
fixed[static_cast<std::size_t>(u)] = true;
for (const RoadEnd& end : lists[static_cast<std::size_t>(u)]) {
if (fixed[static_cast<std::size_t>(end.to)]) continue;
if (end.toll) {
if (used == k) continue;
used++;
}
if (d + end.length < distance[static_cast<std::size_t>(end.to)]) {
distance[static_cast<std::size_t>(end.to)] = d + end.length;
heap.push({distance[static_cast<std::size_t>(end.to)], end.to});
}
}
}
long long answer = distance[static_cast<std::size_t>(target)];
return answer == infinity ? NO_ROUTE : answer;
}
// Error: cada entrada recuerda sus peajes, pero cada ciudad se fija una sola vez, con la menor
// distancia. La primera llegada a una ciudad puede haber gastado los peajes que hacían falta después.
inline long long with_one_distance_per_city(int cities, const std::vector<Road>& roads, int source, int target,
int k) {
using Entry = std::tuple<long long, int, int>;
std::vector<std::vector<RoadEnd>> lists = road_lists(cities, roads);
std::vector<bool> fixed(static_cast<std::size_t>(cities), false);
std::priority_queue<Entry, std::vector<Entry>, std::greater<Entry>> heap;
heap.push({0, source, 0});
while (!heap.empty()) {
auto [d, u, used] = heap.top();
heap.pop();
if (fixed[static_cast<std::size_t>(u)]) continue;
fixed[static_cast<std::size_t>(u)] = true;
if (u == target) return d;
for (const RoadEnd& end : lists[static_cast<std::size_t>(u)]) {
int next_used = used + (end.toll ? 1 : 0);
if (next_used <= k && !fixed[static_cast<std::size_t>(end.to)]) {
heap.push({d + end.length, end.to, next_used});
}
}
}
return NO_ROUTE;
}Pruebas
Comprueban lo que afirman los apuntes; se ejecutan con make test.
// Comprueba lo que afirman los apuntes. Se compila con sanitizers.
#include <algorithm>
#include <cassert>
#include <iostream>
#include <numeric>
#include <random>
#include <set>
#include <tuple>
#include <utility>
#include <vector>
#include "huffman.h"
#include "scheduling.h"
#include "shortest_paths.h"
#include "state_graph.h"
#include "toll_mistakes.h"
namespace {
int below(std::mt19937& rng, int limit) { return static_cast<int>(rng() % static_cast<unsigned>(limit)); }
// ---------- Retraso máximo ----------
void test_lateness_counterexamples() {
std::vector<Job> a = {{1, 100}, {10, 10}};
assert(brute_min_max_lateness(a) == 0);
assert(max_lateness(a, order_by_duration(a)) == 1);
assert(max_lateness(a, order_by_deadline(a)) == 0);
std::vector<Job> b = {{1, 2}, {10, 10}};
assert(brute_min_max_lateness(b) == 1);
assert(max_lateness(b, order_by_slack(b)) == 9);
assert(max_lateness(b, order_by_deadline(b)) == 1);
}
std::vector<Job> random_jobs(std::mt19937& rng, int n) {
std::vector<Job> jobs;
for (int i = 0; i < n; i++) {
jobs.push_back({1 + below(rng, 6), below(rng, 16)}); // plazos en rango chico: muchos empates
}
return jobs;
}
void test_earliest_deadline_is_optimal() {
std::mt19937 rng(501);
for (int round = 0; round < 1500; round++) {
std::vector<Job> jobs = random_jobs(rng, 1 + below(rng, 7));
assert(max_lateness(jobs, order_by_deadline(jobs)) == brute_min_max_lateness(jobs));
}
}
// Todos los horarios sin inversiones dan el mismo máximo, sea cual sea el orden dentro de un mismo plazo.
void test_no_inversion_schedules_agree() {
std::mt19937 rng(502);
for (int round = 0; round < 300; round++) {
std::vector<Job> jobs = random_jobs(rng, 1 + below(rng, 7));
std::vector<int> order(jobs.size());
std::iota(order.begin(), order.end(), 0);
long long expected = max_lateness(jobs, order_by_deadline(jobs));
do {
if (count_inversions(jobs, order) == 0) {
assert(max_lateness(jobs, order) == expected);
}
} while (std::next_permutation(order.begin(), order.end()));
}
}
// Cambiar un par adyacente invertido quita exactamente una inversión y no sube el máximo.
// Sin inversiones adyacentes no hay ninguna inversión.
void test_adjacent_swaps() {
std::mt19937 rng(503);
for (int round = 0; round < 2000; round++) {
std::vector<Job> jobs = random_jobs(rng, 2 + below(rng, 7));
std::vector<int> order(jobs.size());
std::iota(order.begin(), order.end(), 0);
std::shuffle(order.begin(), order.end(), rng);
long long start = max_lateness(jobs, order);
while (true) {
std::size_t i = first_adjacent_inversion(jobs, order);
if (i == order.size()) {
assert(count_inversions(jobs, order) == 0);
break;
}
int inversions = count_inversions(jobs, order);
long long before = max_lateness(jobs, order);
std::swap(order[i], order[i + 1]);
assert(count_inversions(jobs, order) == inversions - 1);
assert(max_lateness(jobs, order) <= before);
}
assert(max_lateness(jobs, order) <= start);
assert(max_lateness(jobs, order) == max_lateness(jobs, order_by_deadline(jobs)));
}
}
// El ejemplo de cinco tareas: D y E tienen el mismo plazo, y cualquier orden entre ellas da 3.
void test_lateness_example() {
std::vector<Job> jobs = {{3, 5}, {2, 4}, {1, 7}, {4, 9}, {2, 9}};
assert(max_lateness(jobs, {1, 0, 2, 3, 4}) == 3);
assert(max_lateness(jobs, {1, 0, 2, 4, 3}) == 3);
assert(brute_min_max_lateness(jobs) == 3);
// Cambiar dos no vecinas puede subir el máximo, aunque estén invertidas.
std::vector<Job> far = {{1, 5}, {1, 2}, {5, 4}};
assert(max_lateness(far, {0, 1, 2}) == 3);
assert(max_lateness(far, {2, 1, 0}) == 4);
}
// ---------- Huffman ----------
void test_huffman_counterexamples() {
std::vector<long long> freq = {15, 7, 6, 6, 5};
assert(brute_min_cost(freq) == 87);
assert(code_cost(freq, top_down_split(freq)) == 89);
assert(code_cost(freq, huffman(freq).depth) == 87);
std::vector<long long> flat(8, 1);
assert(code_cost(flat, chain_code(flat)) == 35);
assert(code_cost(flat, huffman(flat).depth) == 24);
}
void test_review_question() {
std::vector<long long> freq = {1, 1, 2, 3, 5, 8};
HuffmanResult result = huffman(freq);
assert(code_cost(freq, result.depth) == 45);
assert(merges_total(result.merges) == 45);
assert(brute_min_cost(freq) == 45);
// Esta lista tiene empates de pesos, pero con ellos no se puede armar otro par: un solo árbol.
assert(huffman_all_ties(freq).size() == 1);
}
void test_two_symbols() {
std::vector<long long> freq = {3, 9};
HuffmanResult result = huffman(freq);
assert(result.depth == (std::vector<int>{1, 1}));
assert(code_cost(freq, result.depth) == 12);
assert(brute_min_cost(freq) == 12);
}
// Con empates de verdad hay árboles distintos, y todos cuestan lo mismo.
void test_ties_give_same_cost() {
std::vector<long long> freq = {1, 1, 2, 2};
std::set<std::vector<int>> trees = huffman_all_ties(freq);
assert(trees.size() == 3);
for (const std::vector<int>& depth : trees) {
assert(code_cost(freq, depth) == 12);
}
assert(brute_min_cost(freq) == 12);
}
void test_huffman_is_optimal() {
std::mt19937 rng(504);
for (int round = 0; round < 400; round++) {
int n = 2 + below(rng, 5);
std::vector<long long> freq;
for (int i = 0; i < n; i++) freq.push_back(1 + below(rng, 8));
long long best = brute_min_cost(freq);
HuffmanResult result = huffman(freq);
assert(code_cost(freq, result.depth) == best);
assert(merges_total(result.merges) == best); // suma de uniones = suma de frecuencia por profundidad
for (const std::vector<int>& depth : huffman_all_ties(freq)) {
assert(code_cost(freq, depth) == best); // cualquier forma de romper empates
}
}
}
// cost(T) = cost(T') + f(x) + f(y): para cada árbol T' del alfabeto reducido, con z = x + y al final,
// se arma T reemplazando la hoja z por x e y como hermanos, y se comparan los dos costos.
void test_cost_relation() {
std::mt19937 rng(505);
for (int round = 0; round < 200; round++) {
int n = 3 + below(rng, 3);
std::vector<long long> freq;
for (int i = 0; i < n; i++) freq.push_back(1 + below(rng, 9));
std::vector<long long> reduced(freq.begin() + 2, freq.end());
reduced.push_back(freq[0] + freq[1]);
auto visit = [&](const std::vector<int>& d) {
std::vector<int> expanded(freq.size(), 0);
for (std::size_t i = 2; i < freq.size(); i++) expanded[i] = d[i - 2];
expanded[0] = expanded[1] = d[freq.size() - 2] + 1;
assert(code_cost(freq, expanded) == code_cost(reduced, d) + freq[0] + freq[1]);
};
std::vector<std::vector<int>> groups;
for (int i = 0; i < n - 1; i++) groups.push_back({i});
std::vector<int> depth(static_cast<std::size_t>(n - 1), 0);
all_full_trees(groups, depth, visit);
}
}
// En un árbol óptimo, un símbolo más frecuente nunca está más hondo que uno menos frecuente.
void test_more_frequent_not_deeper() {
std::mt19937 rng(506);
for (int round = 0; round < 200; round++) {
int n = 2 + below(rng, 4);
std::vector<long long> freq;
for (int i = 0; i < n; i++) freq.push_back(1 + below(rng, 6));
long long best = brute_min_cost(freq);
std::vector<std::vector<int>> groups;
for (int i = 0; i < n; i++) groups.push_back({i});
std::vector<int> depth(freq.size(), 0);
auto visit = [&](const std::vector<int>& d) {
if (code_cost(freq, d) != best) return;
for (std::size_t i = 0; i < freq.size(); i++) {
for (std::size_t j = 0; j < freq.size(); j++) {
if (freq[i] > freq[j]) assert(d[i] <= d[j]);
}
}
};
all_full_trees(groups, depth, visit);
}
}
// ---------- Dijkstra ----------
Graph random_graph(std::mt19937& rng, int n, int arcs, int max_weight) {
Graph graph(static_cast<std::size_t>(n));
for (int i = 0; i < arcs; i++) {
add_arc(graph, below(rng, n), below(rng, n), below(rng, max_weight + 1)); // incluye peso 0
}
return graph;
}
// Cada nodo, al fijarse, ya tiene su distancia de camino mínimo. Y un nodo se fija una sola vez.
void test_dijkstra_invariant() {
std::mt19937 rng(507);
for (int round = 0; round < 2000; round++) {
int n = 1 + below(rng, 12);
Graph graph = random_graph(rng, n, below(rng, 40), 9);
std::vector<long long> truth = relax_until_stable(graph, 0);
DijkstraResult result = dijkstra(graph, 0);
std::vector<int> times(static_cast<std::size_t>(n), 0);
long long previous = 0;
for (const Pop& pop : result.pops) {
assert(pop.distance >= previous); // las distancias salen en orden creciente
previous = pop.distance;
if (pop.stale) continue;
times[static_cast<std::size_t>(pop.node)]++;
assert(pop.distance == truth[static_cast<std::size_t>(pop.node)]);
}
assert(result.distance == truth);
for (int v = 0; v < n; v++) {
// Se fijan exactamente los alcanzables.
assert(times[static_cast<std::size_t>(v)] == (truth[static_cast<std::size_t>(v)] != UNREACHABLE ? 1 : 0));
}
}
}
void test_negative_edge() {
Graph graph(4);
add_arc(graph, 0, 1, 1);
add_arc(graph, 0, 2, 4);
add_arc(graph, 2, 1, -5);
add_arc(graph, 1, 3, 2);
std::vector<long long> truth = relax_until_stable(graph, 0);
DijkstraResult result = dijkstra(graph, 0);
assert(truth == (std::vector<long long>{0, -1, 4, 1}));
assert(result.distance[3] == 3);
assert(result.distance != truth);
}
void test_shifting_changes_winner() {
Graph graph(4);
add_arc(graph, 0, 1, 6);
add_arc(graph, 0, 2, 9);
add_arc(graph, 2, 1, 0);
add_arc(graph, 1, 3, 7);
DijkstraResult result = dijkstra(graph, 0);
assert((path_to(result.parent, 0, 3) == std::vector<int>{0, 1, 3}));
assert(result.distance[3] == 13);
}
// Dos ideas parecidas a Dijkstra fallan en sus contraejemplos.
void test_wrong_ideas() {
Graph first(3);
add_arc(first, 0, 1, 4);
add_arc(first, 0, 2, 1);
add_arc(first, 2, 1, 2);
assert(fix_on_discovery(first, 0)[1] == 4);
assert(dijkstra(first, 0).distance[1] == 3);
Graph second(4);
add_arc(second, 0, 1, 1);
add_arc(second, 1, 3, 10);
add_arc(second, 0, 2, 2);
add_arc(second, 2, 3, 2);
assert(cheapest_arc_walk(second, 0, 3) == 11);
assert(dijkstra(second, 0).distance[3] == 4);
}
// El ejemplo de los apuntes: un arco de peso 0, un nodo sin llegada y dos entradas viejas.
void test_dijkstra_example() {
Graph graph(6);
add_arc(graph, 0, 1, 4);
add_arc(graph, 0, 2, 1);
add_arc(graph, 2, 1, 2);
add_arc(graph, 2, 3, 7);
add_arc(graph, 1, 3, 3);
add_arc(graph, 3, 4, 0);
add_arc(graph, 4, 2, 5);
DijkstraResult result = dijkstra(graph, 0);
assert(result.distance == (std::vector<long long>{0, 3, 1, 6, 6, UNREACHABLE}));
int stale = 0;
for (const Pop& pop : result.pops) stale += pop.stale ? 1 : 0;
assert(stale == 2);
}
// ---------- Grafo de estados ----------
// Árbitro para el recorrido par: tabla por número de tramos, sin grafo de estados. Un recorrido
// mínimo no repite estado, así que basta mirar hasta 2n tramos.
long long even_walk_table(const Graph& graph, int source, int target) {
std::size_t n = graph.size();
std::vector<long long> now(n, UNREACHABLE);
now[static_cast<std::size_t>(source)] = 0;
long long best = now[static_cast<std::size_t>(target)];
for (std::size_t steps = 1; steps <= 2 * n; steps++) {
std::vector<long long> next(n, UNREACHABLE);
for (std::size_t u = 0; u < n; u++) {
if (now[u] == UNREACHABLE) continue;
for (const Arc& arc : graph[u]) {
std::size_t to = static_cast<std::size_t>(arc.to);
next[to] = std::min(next[to], now[u] + arc.weight);
}
}
now = next;
if (steps % 2 == 0) best = std::min(best, now[static_cast<std::size_t>(target)]);
}
return best;
}
void test_even_walks() {
std::mt19937 rng(508);
for (int round = 0; round < 2000; round++) {
int n = 1 + below(rng, 8);
Graph graph = random_graph(rng, n, below(rng, 16), 9);
int target = below(rng, n);
WalkResult result = min_walk_multiple(graph, 0, target, 2);
assert(result.distance == even_walk_table(graph, 0, target));
if (result.distance != UNREACHABLE) {
assert(result.walk.size() % 2 == 1); // número par de tramos, impar de ciudades
}
}
}
// El ejemplo de los choferes: hace falta repetir una ciudad. Sin el triángulo no hay recorrido par.
void test_driver_example() {
Graph line(6);
for (auto [a, b, w] : std::vector<std::tuple<int, int, long long>>{{0, 1, 2}, {1, 2, 2}, {2, 3, 2}}) {
add_arc(line, a, b, w);
add_arc(line, b, a, w);
}
assert(dijkstra(line, 0).distance[3] == 6);
assert(min_walk_multiple(line, 0, 3, 2).distance == UNREACHABLE);
Graph graph = line;
for (auto [a, b, w] : std::vector<std::tuple<int, int, long long>>{{1, 4, 1}, {4, 5, 1}, {5, 1, 1}}) {
add_arc(graph, a, b, w);
add_arc(graph, b, a, w);
}
WalkResult even = min_walk_multiple(graph, 0, 3, 2);
assert(even.distance == 9);
assert(even.walk.size() == 7); // 6 tramos
std::set<int> distinct(even.walk.begin(), even.walk.end());
assert(distinct.size() < even.walk.size());
}
// El ejemplo de los peajes: la respuesta correcta y las dos formas equivocadas.
void test_toll_example() {
const std::vector<Road> roads = {{0, 2, 2, false}, {2, 1, 3, false}, {0, 1, 1, true}, {1, 3, 1, true}};
assert(with_one_distance_per_city(4, roads, 0, 3, 1) == NO_ROUTE);
assert(with_global_counter(4, roads, 0, 3, 1) == NO_ROUTE);
// Con dos peajes permitidos, la primera forma sí acierta: por eso una prueba suelta no la detecta.
assert(with_one_distance_per_city(4, roads, 0, 3, 2) == 2);
}
// La cuenta del costo: V * c estados y E * c arcos a lo sumo.
void test_state_counts() {
std::mt19937 rng(509);
Graph graph = random_graph(rng, 50, 300, 20);
for (int c : {1, 2, 3, 5}) {
WalkResult result = min_walk_multiple(graph, 0, 1, c);
assert(result.relaxations <= 300 * c);
assert(result.pops <= 1 + 300 * c); // una entrada por arco mirado, a lo sumo, y el origen
}
}
} // namespace
int main() {
test_lateness_counterexamples();
test_earliest_deadline_is_optimal();
test_no_inversion_schedules_agree();
test_adjacent_swaps();
test_lateness_example();
test_huffman_counterexamples();
test_review_question();
test_two_symbols();
test_ties_give_same_cost();
test_huffman_is_optimal();
test_cost_relation();
test_more_frequent_not_deeper();
test_dijkstra_invariant();
test_negative_edge();
test_shifting_changes_winner();
test_wrong_ideas();
test_dijkstra_example();
test_even_walks();
test_driver_example();
test_toll_example();
test_state_counts();
std::cout << "Todas las pruebas de la semana 5 pasaron.\n";
}Laboratorio
Archivos de partida del laboratorio de la semana.
TIEMPO = 2
include ../../../lab.mk# Rutas con peajes
Una empresa de transporte reparte entre ciudades unidas por carreteras. Algunas carreteras tienen
peaje. Para cada viaje, el contrato con el cliente fija cuántos peajes puede pagar el camión como
máximo, y el despacho quiere saber cuántos kilómetros recorrerá en la ruta más corta que respete ese
límite.
Todas las carreteras son de doble sentido. Pasar por una carretera con peaje cuenta como un peaje cada
vez que se pasa, en cualquier sentido. Una ruta puede repetir ciudades, si eso le conviene.
## Entrada
La primera línea tiene tres enteros: n, la cantidad de ciudades, numeradas de 0 a n − 1; m, la
cantidad de carreteras; y k, el máximo de peajes del viaje.
La segunda línea tiene dos enteros: s, la ciudad de salida, y t, la de llegada. Pueden ser la misma.
Cada una de las m líneas siguientes describe una carretera con cuatro enteros a, b, w y p: une las
ciudades a y b, mide w kilómetros, y tiene peaje si p = 1 o no lo tiene si p = 0. Entre dos ciudades
puede haber varias carreteras. Ninguna carretera une una ciudad consigo misma.
## Salida
Una línea con un entero: los kilómetros de la ruta más corta de s a t con a lo sumo k peajes, o -1 si
no hay ninguna ruta así.
## Límites
- 1 ≤ n ≤ 50 000
- 0 ≤ m ≤ 100 000
- 0 ≤ k ≤ 20
- 0 ≤ s, t < n
- 1 ≤ w ≤ 1 000 000 000
- a ≠ b
## Ejemplo
Entrada:
```text
5 6 1
0 4
0 1 2 1
1 4 3 1
0 2 3 0
2 1 4 0
2 3 6 0
3 4 5 1
```
Salida:
```text
10
```
La ruta 0, 1, 4 mide solo 5 kilómetros, pero pasa por dos peajes, y este viaje permite uno. La mejor con
un peaje es 0, 2, 1, 4, que mide 3 + 4 + 3 = 10. La ruta 0, 2, 3, 4 también tiene un solo peaje, y mide 14.
## Para pensar antes de programar
En el ejemplo, la forma más corta de llegar a la ciudad 1 mide 2 kilómetros, y la ciudad 1 está en la
mejor ruta hasta la 4. Aun así, esa ruta llega a la ciudad 1 después de 7 kilómetros. ¿Por qué? ¿Qué
respondería un programa que recuerda solo la menor distancia de cada ciudad?
Escriban un caso propio de 4 ciudades, distinto del de los apuntes, en el que ese programa diga -1 y sí
exista una ruta. Agréguenlo a su carpeta de pruebas.
## Tiempo
2 segundos por caso, compilado con `-O2`. Corran `make test` para probar con el juez. Algunos casos
grandes no se guardan: `casos/gen_NN.cpp` los escribe al correr `make test`.
## Extensión
Sin casos en el juez, para seguir pensando: cambien el contrato. Ya no hay límite de peajes, y el
despacho tiene un solo cupón que deja gratis, con 0 kilómetros contados, una carretera a elección.
¿Cuál es la distancia mínima de s a t? Usen la misma forma de razonar, y comparen su respuesta con una
búsqueda exhaustiva en redes pequeñas.// Rutas con peajes: lee la red e imprime 0. Reemplacen el cálculo.
#include <cstddef>
#include <iostream>
#include <vector>
struct Road {
int a;
int b;
int length;
int toll; // 1 si tiene peaje, 0 si no
};
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n = 0;
int m = 0;
int k = 0;
int source = 0;
int target = 0;
std::cin >> n >> m >> k >> source >> target;
std::vector<Road> roads(static_cast<std::size_t>(m));
for (Road& road : roads) {
std::cin >> road.a >> road.b >> road.length >> road.toll;
}
// Por hacer: calcular la respuesta con roads y k.
int answer = 0;
std::cout << answer << '\n';
}Compilación
Cómo se compilan y ejecutan los ejemplos.
# Semana 5: retraso máximo, Huffman, Dijkstra y grafos de estados.
# Se usa dentro del entorno del curso.
#
# make compila los ejemplos en build/
# make test corre las pruebas de los ejemplos, con sanitizers
# make bench corre la medición del grafo de estados, con -O2
# make clean borra lo generado
#
# El problema de lab/ tiene su propio Makefile y no entra aquí.
CXX = g++
CXXFLAGS = -Wall -Wextra -std=c++20 -g -fsanitize=address,undefined
BENCHFLAGS = -Wall -Wextra -std=c++20 -O2
BUILD = build
HEADERS = scheduling.h huffman.h shortest_paths.h state_graph.h toll_mistakes.h
PROGRAMS = lateness_rules lateness_trace huffman_rules huffman_trace dijkstra_trace \
dijkstra_wrong negative_edge shift_weights driver_turns toll_layers test_examples
BENCHES = state_graph_bench
.PHONY: all test bench clean
all: $(PROGRAMS:%=$(BUILD)/%) $(BENCHES:%=$(BUILD)/%)
$(PROGRAMS:%=$(BUILD)/%): $(BUILD)/%: %.cpp $(HEADERS) | $(BUILD)
$(CXX) $(CXXFLAGS) $< -o $@
# Lo que mide va con -O2 y sin sanitizers.
$(BENCHES:%=$(BUILD)/%): $(BUILD)/%: %.cpp $(HEADERS) | $(BUILD)
$(CXX) $(BENCHFLAGS) $< -o $@
$(BUILD):
mkdir -p $@
test: $(BUILD)/test_examples
$(BUILD)/test_examples
bench: $(BUILD)/state_graph_bench
$(BUILD)/state_graph_bench
clean:
rm -rf $(BUILD)