Optimality under uniform traversal times
Lax330177.UniformCosts · concepts/Lax330177/UniformCosts.lean · lax-330177
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Definition
With constant traversal time c, elapsed time equals total internal waiting plus c times the number of hops. At c = 0, fastest and minimum-waiting paths coincide. At c = 1 a hop contributes one unit even if the path never waits.
- Elapsed time splits into travel and waiting. If every available traversal takes c time units, every feasible path has elapsed time equal to its total internal waiting time plus c times its number of hops.
- Zero traversal time. With uniform traversal time zero, a feasible path is fastest exactly when it minimizes total internal waiting time.
- Unit traversal time. With uniform traversal time one, a feasible path is fastest exactly when it minimizes the sum of its hop count and its total internal waiting time.
Concept map
Lean source view on GitHub
| 1 | import Lax330177.OptimalPaths |
| 2 | |
| 3 | /-! |
| 4 | --- |
| 5 | title: Optimality under uniform traversal times |
| 6 | type: definition |
| 7 | --- |
| 8 | With constant traversal time c, elapsed time equals total internal waiting plus |
| 9 | c times the number of hops. At c = 0, fastest and minimum-waiting paths coincide. |
| 10 | At c = 1 a hop contributes one unit even if the path never waits. |
| 11 | |
| 12 | - [Elapsed time splits into travel and waiting.](Lax330177Proofs.UniformCosts.elapsed_eq.html) If every available traversal takes c time units, every feasible path has elapsed time equal to its total internal waiting time plus c times its number of hops. |
| 13 | - [Zero traversal time.](Lax330177Proofs.UniformCosts.zero_optima.html) With uniform traversal time zero, a feasible path is fastest exactly when it minimizes total internal waiting time. |
| 14 | - [Unit traversal time.](Lax330177Proofs.UniformCosts.unit_optima.html) With uniform traversal time one, a feasible path is fastest exactly when it minimizes the sum of its hop count and its total internal waiting time. |
| 15 | -/ |
| 16 | namespace Lax330177.UniformCosts |
| 17 | open Lax330177.Representations Lax330177.OptimalPaths |
| 18 | variable {n : ℕ} {G : Graph n} {q : Query G} |
| 19 | def Uniform (q : Query G) (c : ℕ) := ∀ t u v, G.edge t u v → q.transit t u v = c |
| 20 | |
| 21 | end Lax330177.UniformCosts |
| 22 |
Builds on
From Mathlib
none
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments