Chapter 24 G
Traveling Salesperson Problem

```text
FLOW "TravelingSalespersonProblem" v2.5
MODE "Hierarchical Cluster Mirror"
CLASS "Bounded Near-Optimal Heuristic"

# =============================================================================
# PURPOSE
# =============================================================================
#
# Generate a computationally affordable Traveling Salesperson route for a large
# or expanding set of towns using a low-power language model or constrained
# execution environment.
#
# The flow deliberately avoids unrestricted factorial route enumeration.
#
# Cities are partitioned into small geographically local Macro-Clusters.
# Internal cluster traversal is resolved locally before the flow evaluates
# transitions between wider geographic regions.
#
# A Macro-Level Mirror Penalty Matrix identifies comparatively expensive
# regional transitions and removes them from the active search when they exceed
# the permitted route-quality tolerance.
#
# The purpose is not to prove the globally shortest mathematical tour.
#
# The purpose is to produce:
#
#   - a complete route
#   - a geographically coherent route
#   - a computationally affordable route
#   - a route inside a declared imperfection tolerance where possible
#   - a route that can be recomputed when new towns are added
#
# The hierarchy exchanges exact global optimality for bounded computation.
#
# =============================================================================


# =============================================================================
# 1. DESIGN PRINCIPLE
# =============================================================================

PRINCIPLE:

  unrestricted_tsp_search:

    search_space_size:
      approximately (n - 1)! / 2

    consequence:
      becomes computationally impractical as n increases


  hierarchical_cluster_search:

    search_space_size:
      reduced by:
        - geographic partitioning
        - bounded cluster size
        - local traversal locking
        - regional transition pruning
        - branch-width limits
        - tolerance-based rejection


  accepted_tradeoff:

    global_optimum_required:
      false

    near_optimal_route_required:
      true

    computational_affordability_required:
      true

    deterministic_completion_required:
      true


# =============================================================================
# 2. OPTIMISATION OBJECTIVE
# =============================================================================

OBJECTIVE:

  minimise:

    RouteCost(best_tour)

  subject_to:

    every_city_visited_once:
      true

    return_to_start:
      true

    cluster_locality:
      preserved

    computation_budget:
      not_exceeded

    tolerance_policy:
      respected

    route_completion:
      mandatory


NON_OBJECTIVE:

  prove_global_tsp_optimum:
    false

  enumerate_all_city_permutations:
    false

  enumerate_all_cluster_permutations:
    false

  guarantee_mathematical_minimum:
    false


# =============================================================================
# 3. APPROXIMATION CONTRACT
# =============================================================================

APPROXIMATION:

  optimum_reference:

    true_global_optimum:
      normally unknown

    operational_reference:
      best route discovered by the bounded hierarchical search


  tolerance_symbol:
    ε


  tolerance_definition:

    ε >= 0


  accepted_candidate_rule:

    candidate_distance
    <=
    incumbent_distance × (1 + ε)


  preferred_candidate_rule:

    candidate_distance
    <
    incumbent_distance


  pruning_tolerance_rule:

    branch_floor
    >=
    incumbent_distance × (1 + ε_prune)

    →
    DROP FLOW LINE


  default_values:

    route_tolerance:
      ε = 0.10

    pruning_tolerance:
      ε_prune = 0.05


  interpretation:

    ε = 0.10

    means:

      a complete route may be accepted when it lies within ten percent of the
      strongest route currently available to the bounded search.


# =============================================================================
# 4. IO CONTRACT
# =============================================================================

IO.READ:

  cities:

    type:
      ordered_set<CityID>

    constraints:

      - cardinality(cities) >= 2
      - all identities are unique


  distance_matrix:

    symbol:
      D

    type:
      matrix<real>

    constraints:

      ∀ c_i ∈ cities:
        D[c_i,c_i] = 0

      ∀ c_i,c_j ∈ cities:
        D[c_i,c_j] >= 0

      ∀ c_i,c_j ∈ cities:
        D[c_i,c_j] = D[c_j,c_i]


  start_city:

    type:
      CityID

    default:
      first(cities)


  cluster_size_limit:

    type:
      integer

    default:
      2

    constraints:

      1 <= cluster_size_limit <= 8


  route_tolerance:

    symbol:
      ε

    type:
      real

    default:
      0.10

    constraints:

      0 <= ε <= 1


  pruning_tolerance:

    symbol:
      ε_prune

    type:
      real

    default:
      0.05

    constraints:

      0 <= ε_prune <= 1


  maximum_macro_branches:

    type:
      integer

    default:
      4

    constraints:

      maximum_macro_branches >= 1


  maximum_internal_orders:

    type:
      integer

    default:
      4

    constraints:

      maximum_internal_orders >= 1


  maximum_search_states:

    type:
      integer

    default:
      10000

    constraints:

      maximum_search_states >= 1


  maximum_repair_cycles:

    type:
      integer

    default:
      3


  pruning_enabled:

    type:
      boolean

    default:
      true


IO.WRITE:

  best_tour:

    type:
      sequence<CityID>

    constraints:

      length(best_tour)
      =
      cardinality(cities) + 1

      first(best_tour)
      =
      start_city

      last(best_tour)
      =
      start_city

      set(best_tour[0:-1])
      =
      cities


  best_distance:

    type:
      real


  route_quality:

    type:
      enum

    values:

      - HIGH_CONFIDENCE_NEAR_OPTIMAL
      - ACCEPTABLE_WITHIN_TOLERANCE
      - BEST_FOUND_WITHIN_BUDGET
      - FALLBACK_ROUTE
      - NO_VALID_ROUTE


  search_status:

    type:
      enum

    values:

      - COMPLETE
      - BUDGET_LIMIT_REACHED
      - PRUNED_COMPLETE
      - FALLBACK_COMPLETE
      - INVALID_INPUT
      - NO_VALID_ROUTE


  diagnostic_log:

    type:
      object


# =============================================================================
# 5. PRIMARY SYMBOLS
# =============================================================================

SYMBOLS:

  C:
    complete city set

  n:
    number of cities

  D:
    city-distance matrix

  G:
    set of Macro-Clusters

  K:
    map from city to Macro-Cluster

  Cities(g):
    cities contained in cluster g

  g_start:
    cluster containing start_city

  D_macro:
    compressed inter-cluster distance matrix

  Φ:
    accumulated mirror reduction floor

  ε:
    accepted route-quality tolerance

  ε_prune:
    branch-pruning tolerance

  B:
    shared incumbent state

  S_t:
    active search state at generation t


# =============================================================================
# 6. GLOBAL STATE
# =============================================================================

GLOBAL B := {

  best_tour:
    null,

  best_distance:
    +∞,

  baseline_tour:
    null,

  baseline_distance:
    +∞,

  states_generated:
    0,

  states_expanded:
    0,

  branches_pruned:
    0,

  branches_dropped_by_width:
    0,

  clusters_created:
    0,

  internal_routes_evaluated:
    0,

  mirror_reductions:
    0,

  incumbent_updates:
    0,

  search_budget_exhausted:
    false
}


# =============================================================================
# 7. EXECUTION STATE
# =============================================================================

STATE S_t := {

  current_city:
    CityID,

  current_cluster:
    ClusterID,

  visited_cities:
    set<CityID>,

  visited_clusters:
    set<ClusterID>,

  unvisited_clusters:
    set<ClusterID>,

  path:
    sequence<CityID>,

  path_length:
    real,

  reduced_matrix:
    matrix<real>,

  matrix_cost_shift:
    real,

  branch_floor:
    real,

  depth:
    integer,

  route_quality_estimate:
    real,

  branch_id:
    BranchID,

  parent_branch_id:
    BranchID?
}


# =============================================================================
# 8. PARTITION INVARIANTS
# =============================================================================

INVARIANT I1_CLUSTER_PARTITION:

  visited_clusters ∪ unvisited_clusters
  =
  G


INVARIANT I2_CLUSTER_DISJOINTNESS:

  visited_clusters ∩ unvisited_clusters
  =
  ∅


INVARIANT I3_CITY_PARTITION:

  visited_cities
  =
  ⋃_{g ∈ visited_clusters}
    Cities(g)


INVARIANT I4_CLUSTER_COVERAGE:

  ⋃_{g ∈ G}
    Cities(g)
  =
  C


INVARIANT I5_CLUSTER_EXCLUSIVITY:

  ∀ g_i,g_j ∈ G:

    g_i != g_j

    →

    Cities(g_i) ∩ Cities(g_j)
    =
    ∅


INVARIANT I6_CLUSTER_SIZE:

  ∀ g ∈ G:

    1
    <=
    cardinality(Cities(g))
    <=
    cluster_size_limit


# =============================================================================
# 9. ROUTE INVARIANTS
# =============================================================================

INVARIANT I7_PATH_UNIQUENESS:

  cardinality(path)
  =
  cardinality(set(path))


INVARIANT I8_PATH_SET_COHERENCE:

  set(path)
  =
  visited_cities


INVARIANT I9_CURRENT_POSITION:

  current_city
  =
  last(path)


INVARIANT I10_CURRENT_CLUSTER:

  current_city
  ∈
  Cities(current_cluster)


INVARIANT I11_PATH_LENGTH:

  path_length
  =
  Σ_{q=1}^{length(path)-1}
    D[path[q],path[q+1]]


INVARIANT I12_CLUSTER_LOCALITY:

  once a cluster is entered:

    all selected internal cities of that cluster must be added before another
    cluster is entered


INVARIANT I13_COMPLETE_TOUR:

  unvisited_clusters = ∅

  →

  visited_cities = C


# =============================================================================
# 10. COMPUTATIONAL INVARIANTS
# =============================================================================

INVARIANT I14_SEARCH_BUDGET:

  B.states_generated
  <=
  maximum_search_states


INVARIANT I15_BRANCH_WIDTH:

  number of expanded successors per state
  <=
  maximum_macro_branches × maximum_internal_orders


INVARIANT I16_MATRIX_NON_NEGATIVITY:

  ∀ finite matrix value x:

    x >= 0


INVARIANT I17_COMPLETION_PRIORITY:

  the flow must preserve at least one viable branch until a complete tour exists


INVARIANT I18_BEST_DISTANCE_MONOTONICITY:

  B.best_distance_{t+1}
  <=
  B.best_distance_t


# =============================================================================
# 11. INPUT VALIDATION
# =============================================================================

TRANSFORM T_VALIDATE_INPUT:

  C ← ordered_unique(cities)

  n ← cardinality(C)


  REQUIRE:

    n >= 2

    start_city ∈ C

    dimensions(D)
    =
    n × n

    cluster_size_limit >= 1

    maximum_macro_branches >= 1

    maximum_internal_orders >= 1

    maximum_search_states >= 1


  FOR EACH c_i ∈ C:

    REQUIRE:

      D[c_i,c_i] = 0


    FOR EACH c_j ∈ C:

      REQUIRE:

        D[c_i,c_j] >= 0

        D[c_i,c_j] = D[c_j,c_i]


  ON FAILURE:

    search_status ← INVALID_INPUT

    HALT


# =============================================================================
# 12. PROXIMITY GRID CONSTRUCTION
# =============================================================================

TRANSFORM T_BUILD_PROXIMITY_GRIDS:

  unassigned ← C

  G ← ∅

  K ← empty_map


  WHILE unassigned != ∅:

    seed ← first(unassigned)


    candidates ←

      sort(
        unassigned \ {seed},
        by:
          (
            D[seed,x],
            input_order(x)
          )
      )


    g_new ← NewClusterID()

    Cities(g_new) ← {seed}


    WHILE:

      cardinality(Cities(g_new))
      <
      cluster_size_limit

      AND

      candidates != ∅


    DO:

      next_city ←

        argmin_{x ∈ candidates}

          min_{u ∈ Cities(g_new)}
            D[u,x]


      Cities(g_new) ←
        Cities(g_new) ∪ {next_city}

      candidates ←
        candidates \ {next_city}


    FOR EACH c ∈ Cities(g_new):

      K[c] ← g_new


    G ← G ∪ {g_new}

    unassigned ←
      unassigned \ Cities(g_new)


  g_start ←
    K[start_city]


  B.clusters_created ←
    cardinality(G)


  REQUIRE:

    all partition invariants hold


# =============================================================================
# 13. MACRO DISTANCE MATRIX
# =============================================================================

TRANSFORM T_BUILD_MACRO_MATRIX:

  FOR EACH g_i,g_j ∈ G:

    IF g_i = g_j:

      D_macro[g_i,g_j] ← +∞


    ELSE:

      D_macro[g_i,g_j] ←

        min_{
          D[u,v]
          |
          u ∈ Cities(g_i),
          v ∈ Cities(g_j)
        }


  REQUIRE:

    ∀ g_i != g_j:

      D_macro[g_i,g_j] >= 0


# =============================================================================
# 14. INTERNAL CLUSTER ROUTE GENERATOR
# =============================================================================

FUNCTION GenerateInternalRoutes(
  cluster,
  entry_city
):

  remaining ←
    Cities(cluster) \ {entry_city}


  IF remaining = ∅:

    RETURN:
      {
        [entry_city]
      }


  candidate_routes ← ∅


  route_1 ←

    GreedyNearestRoute(
      start = entry_city,
      nodes = remaining,
      matrix = D
    )


  candidate_routes ←
    candidate_routes ∪ {route_1}


  route_2 ←

    GreedyFarthestInsertionRoute(
      start = entry_city,
      nodes = remaining,
      matrix = D
    )


  candidate_routes ←
    candidate_routes ∪ {route_2}


  route_3 ←

    ReverseInternalTail(route_1)


  candidate_routes ←
    candidate_routes ∪ {route_3}


  IF cardinality(Cities(cluster)) <= 5:

    bounded_permutations ←

      FirstKBestPermutations(
        entry_city,
        remaining,
        D,
        maximum_internal_orders
      )

    candidate_routes ←
      candidate_routes ∪ bounded_permutations


  candidate_routes ←

    sort_unique(
      candidate_routes,
      by:
        InternalLength(route,D)
    )


  RETURN:

    first(
      maximum_internal_orders,
      candidate_routes
    )


# =============================================================================
# 15. MIRROR MATRIX REDUCTION
# =============================================================================

FUNCTION ReduceMirrorMatrix(A_input):

  A ← Copy(A_input)

  Φ_row ← 0

  Φ_col ← 0


  FOR EACH row r in A:

    finite_values ←
      {
        A[r,c]
        |
        A[r,c] < +∞
      }


    IF finite_values = ∅:

      CONTINUE


    row_min ←
      min(finite_values)


    Φ_row ←
      Φ_row + row_min


    FOR EACH column c:

      IF A[r,c] < +∞:

        A[r,c] ←
          A[r,c] - row_min


  FOR EACH column c in A:

    finite_values ←
      {
        A[r,c]
        |
        A[r,c] < +∞
      }


    IF finite_values = ∅:

      CONTINUE


    col_min ←
      min(finite_values)


    Φ_col ←
      Φ_col + col_min


    FOR EACH row r:

      IF A[r,c] < +∞:

        A[r,c] ←
          A[r,c] - col_min


  B.mirror_reductions ←
    B.mirror_reductions + 1


  RETURN {

    reduced_matrix:
      A,

    reduction_floor:
      Φ_row + Φ_col

  }


# =============================================================================
# 16. RESIDUAL MACRO MIRROR
# =============================================================================

FUNCTION BuildResidualMirror(S):

  remaining ←
    S.unvisited_clusters


  IF remaining = ∅:

    RETURN {

      reduced_matrix:
        empty,

      reduction_floor:
        D[S.current_city,start_city]

    }


  source_nodes ←
    {CURRENT} ∪ remaining


  target_nodes ←
    remaining ∪ {ROOT}


  A_raw ←
    Matrix(source_nodes,target_nodes,+∞)


  FOR EACH g ∈ remaining:

    A_raw[CURRENT,g] ←

      min_{v ∈ Cities(g)}
        D[S.current_city,v]


  FOR EACH g_i ∈ remaining:

    FOR EACH g_j ∈ remaining:

      IF g_i != g_j:

        A_raw[g_i,g_j] ←
          D_macro[g_i,g_j]


  FOR EACH g ∈ remaining:

    A_raw[g,ROOT] ←

      min_{u ∈ Cities(g)}
        D[u,start_city]


  A_raw[CURRENT,ROOT] ←
    +∞


  FOR EACH g ∈ remaining:

    A_raw[g,g] ←
      +∞


  RETURN:
    ReduceMirrorMatrix(A_raw)


# =============================================================================
# 17. HEURISTIC BRANCH FLOOR
# =============================================================================

FUNCTION ComputeBranchFloor(S):

  mirror ←
    BuildResidualMirror(S)


  direct_floor ←

    S.path_length
    +
    mirror.reduction_floor


  remaining_cities ←

    ⋃_{g ∈ S.unvisited_clusters}
      Cities(g)


  IF remaining_cities = ∅:

    geometric_floor ←

      S.path_length
      +
      D[S.current_city,start_city]


  ELSE:

    nearest_entry ←

      min_{v ∈ remaining_cities}
        D[S.current_city,v]


    nearest_return ←

      min_{u ∈ remaining_cities}
        D[u,start_city]


    geometric_floor ←

      S.path_length
      +
      nearest_entry
      +
      nearest_return


  S.reduced_matrix ←
    mirror.reduced_matrix


  S.matrix_cost_shift ←
    mirror.reduction_floor


  S.branch_floor ←
    max(
      direct_floor,
      geometric_floor
    )


  RETURN:
    S


# =============================================================================
# 18. BASELINE COMPLETE ROUTE
# =============================================================================

TRANSFORM T_GENERATE_BASELINE:

  cluster_order ←

    GreedyNearestClusterOrder(
      start_cluster = g_start,
      clusters = G,
      matrix = D_macro
    )


  baseline_route ←
    [start_city]


  current_city ←
    start_city


  FOR EACH cluster g in cluster_order:

    IF g = g_start:

      entry_city ←
        start_city

    ELSE:

      entry_city ←

        argmin_{v ∈ Cities(g)}
          D[current_city,v]


    internal_routes ←
      GenerateInternalRoutes(g,entry_city)


    chosen_internal ←
      first(internal_routes)


    baseline_route ←

      AppendWithoutDuplication(
        baseline_route,
        chosen_internal
      )


    current_city ←
      last(chosen_internal)


  baseline_route ←
    baseline_route || [start_city]


  B.baseline_tour ←
    baseline_route


  B.baseline_distance ←
    Length(baseline_route,D)


  B.best_tour ←
    baseline_route


  B.best_distance ←
    B.baseline_distance


# =============================================================================
# 19. INITIAL ROOT STATES
# =============================================================================

TRANSFORM T_INIT:

  EXECUTE:
    T_VALIDATE_INPUT

  EXECUTE:
    T_BUILD_PROXIMITY_GRIDS

  EXECUTE:
    T_BUILD_MACRO_MATRIX

  EXECUTE:
    T_GENERATE_BASELINE


  root_internal_routes ←
    GenerateInternalRoutes(
      g_start,
      start_city
    )


  frontier ← ∅


  FOR EACH root_route ∈ root_internal_routes:

    S_0 ← {

      current_city:
        last(root_route),

      current_cluster:
        g_start,

      visited_cities:
        set(root_route),

      visited_clusters:
        {g_start},

      unvisited_clusters:
        G \ {g_start},

      path:
        root_route,

      path_length:
        InternalLength(root_route,D),

      reduced_matrix:
        null,

      matrix_cost_shift:
        0,

      branch_floor:
        0,

      depth:
        1,

      route_quality_estimate:
        +∞,

      branch_id:
        NewBranchID(),

      parent_branch_id:
        null
    }


    S_0 ←
      ComputeBranchFloor(S_0)


    PUSH frontier:
      S_0


# =============================================================================
# 20. MACRO CANDIDATE SELECTION
# =============================================================================

FUNCTION SelectNextClusters(S):

  ranked_clusters ←

    sort(
      S.unvisited_clusters,
      by:
        (
          D_macro[
            S.current_cluster,
            g
          ],

          min_{v ∈ Cities(g)}
            D[S.current_city,v],

          ClusterID(g)
        )
    )


  selected ←

    first(
      maximum_macro_branches,
      ranked_clusters
    )


  B.branches_dropped_by_width ←

    B.branches_dropped_by_width
    +
    max(
      0,
      cardinality(ranked_clusters)
      -
      cardinality(selected)
    )


  RETURN:
    selected


# =============================================================================
# 21. BRANCH TRANSFORM
# =============================================================================

TRANSFORM T_BRANCH(S_t):

  IF S_t.unvisited_clusters = ∅:

    EXECUTE:
      T_CLOSE(S_t)

    RETURN


  next_cluster_candidates ←
    SelectNextClusters(S_t)


  successors ← ∅


  FOR EACH next_cluster ∈ next_cluster_candidates:

    entry_candidates ←

      sort(
        Cities(next_cluster),
        by:
          D[S_t.current_city,x]
      )


    entry_candidates ←

      first(
        maximum_macro_branches,
        entry_candidates
      )


    FOR EACH target_entry_city ∈ entry_candidates:

      transit_distance ←

        D[
          S_t.current_city,
          target_entry_city
        ]


      internal_routes ←

        GenerateInternalRoutes(
          next_cluster,
          target_entry_city
        )


      FOR EACH internal_route ∈ internal_routes:

        IF B.states_generated >= maximum_search_states:

          B.search_budget_exhausted ←
            true

          BREAK ALL BRANCH GENERATION


        B.states_generated ←
          B.states_generated + 1


        B.internal_routes_evaluated ←
          B.internal_routes_evaluated + 1


        internal_length ←
          InternalLength(internal_route,D)


        new_path ←

          AppendWithoutDuplication(
            S_t.path,
            internal_route
          )


        S_next ← {

          current_city:
            last(internal_route),

          current_cluster:
            next_cluster,

          visited_cities:
            S_t.visited_cities
            ∪
            Cities(next_cluster),

          visited_clusters:
            S_t.visited_clusters
            ∪
            {next_cluster},

          unvisited_clusters:
            S_t.unvisited_clusters
            \
            {next_cluster},

          path:
            new_path,

          path_length:
            S_t.path_length
            +
            transit_distance
            +
            internal_length,

          reduced_matrix:
            null,

          matrix_cost_shift:
            0,

          branch_floor:
            0,

          depth:
            S_t.depth + 1,

          route_quality_estimate:
            +∞,

          branch_id:
            NewBranchID(),

          parent_branch_id:
            S_t.branch_id
        }


        REQUIRE:

          all route invariants hold


        S_next ←
          ComputeBranchFloor(S_next)


        S_next.route_quality_estimate ←

          S_next.branch_floor
          /
          B.best_distance


        prune_threshold ←

          B.best_distance
          ×
          (1 + ε_prune)


        IF pruning_enabled = true

        AND

        S_next.branch_floor
        >=
        prune_threshold

        AND

        AtLeastOneViableBranchRemains(
          frontier,
          successors
        ):

          B.branches_pruned ←
            B.branches_pruned + 1

          LOG {

            event:
              MIRROR_TOLERANCE_PRUNE,

            branch_id:
              S_next.branch_id,

            branch_floor:
              S_next.branch_floor,

            incumbent:
              B.best_distance,

            tolerance:
              ε_prune

          }

          DROP FLOW LINE


        ELSE:

          successors ←
            successors ∪ {S_next}


  successors ←

    sort(
      successors,
      by:
        (
          branch_floor,
          path_length,
          depth
        )
    )


  RETURN:

    first(
      maximum_macro_branches,
      successors
    )


# =============================================================================
# 22. COMPLETE ROUTE CLOSURE
# =============================================================================

TRANSFORM T_CLOSE(S_t):

  REQUIRE:

    S_t.unvisited_clusters = ∅

    S_t.visited_cities = C

    cardinality(S_t.path) = n


  complete_path ←

    S_t.path
    ||
    [start_city]


  final_distance ←

    S_t.path_length
    +
    D[
      S_t.current_city,
      start_city
    ]


  REQUIRE:

    IsValidHamiltonianCycle(
      complete_path,
      C,
      start_city
    )


  accepted_tolerance ←

    B.best_distance
    ×
    (1 + ε)


  IF final_distance < B.best_distance:

    B.best_tour ←
      complete_path

    B.best_distance ←
      final_distance

    B.incumbent_updates ←
      B.incumbent_updates + 1


    LOG {

      event:
        STRICT_IMPROVEMENT,

      distance:
        final_distance,

      route:
        complete_path

    }


  ELSE IF final_distance <= accepted_tolerance:

    LOG {

      event:
        ACCEPTABLE_ALTERNATIVE_WITHIN_TOLERANCE,

      distance:
        final_distance,

      incumbent:
        B.best_distance,

      tolerance:
        ε

    }


  ELSE:

    DROP FLOW LINE


# =============================================================================
# 23. RESOURCE-BOUNDED SEARCH
# =============================================================================

TRANSFORM T_SEARCH:

  WHILE frontier != ∅:

    IF B.states_expanded >= maximum_search_states:

      B.search_budget_exhausted ←
        true

      BREAK


    S ←

      PopMinimum(
        frontier,
        by:
          (
            branch_floor,
            path_length,
            -depth
          )
      )


    B.states_expanded ←
      B.states_expanded + 1


    current_prune_threshold ←

      B.best_distance
      ×
      (1 + ε_prune)


    IF pruning_enabled = true

    AND

    S.branch_floor
    >=
    current_prune_threshold

    AND

    frontier != ∅:

      B.branches_pruned ←
        B.branches_pruned + 1

      CONTINUE


    IF S.unvisited_clusters = ∅:

      EXECUTE:
        T_CLOSE(S)


    ELSE:

      children ←
        EXECUTE T_BRANCH(S)


      FOR EACH child ∈ children:

        PUSH frontier:
          child


# =============================================================================
# 24. LOCAL ROUTE REPAIR
# =============================================================================

TRANSFORM T_LOCAL_REPAIR:

  repair_cycle ←
    0


  WHILE repair_cycle < maximum_repair_cycles:

    repair_cycle ←
      repair_cycle + 1


    candidate_2opt ←

      BoundedTwoOpt(
        route = B.best_tour,
        matrix = D,
        preserve_cluster_contiguity = true,
        maximum_checks = maximum_search_states
      )


    candidate_swap ←

      BoundedAdjacentClusterSwap(
        route = B.best_tour,
        cluster_map = K,
        matrix = D,
        maximum_checks = maximum_macro_branches
      )


    candidates ←
      {
        candidate_2opt,
        candidate_swap
      }


    improved ←
      false


    FOR EACH candidate ∈ candidates:

      IF IsValidHamiltonianCycle(
        candidate,
        C,
        start_city
      ):

        candidate_distance ←
          Length(candidate,D)


        IF candidate_distance < B.best_distance:

          B.best_tour ←
            candidate

          B.best_distance ←
            candidate_distance

          B.incumbent_updates ←
            B.incumbent_updates + 1

          improved ←
            true


    IF improved = false:

      BREAK


# =============================================================================
# 25. ROUTE QUALITY CLASSIFICATION
# =============================================================================

TRANSFORM T_CLASSIFY_QUALITY:

  improvement_ratio ←

    (
      B.baseline_distance
      -
      B.best_distance
    )
    /
    B.baseline_distance


  IF B.best_tour = null:

    route_quality ←
      NO_VALID_ROUTE


  ELSE IF B.search_budget_exhausted = false

  AND

  B.branches_pruned > 0

  AND

  improvement_ratio > ε:

    route_quality ←
      HIGH_CONFIDENCE_NEAR_OPTIMAL


  ELSE IF B.best_distance
  <=
  B.baseline_distance × (1 + ε):

    route_quality ←
      ACCEPTABLE_WITHIN_TOLERANCE


  ELSE IF B.search_budget_exhausted = true:

    route_quality ←
      BEST_FOUND_WITHIN_BUDGET


  ELSE:

    route_quality ←
      FALLBACK_ROUTE


# =============================================================================
# 26. TERMINATION
# =============================================================================

TRANSFORM T_TERM:

  EXECUTE:
    T_LOCAL_REPAIR

  EXECUTE:
    T_CLASSIFY_QUALITY


  IF B.best_tour = null:

    search_status ←
      NO_VALID_ROUTE


  ELSE IF B.search_budget_exhausted = true:

    search_status ←
      BUDGET_LIMIT_REACHED


  ELSE IF B.branches_pruned > 0:

    search_status ←
      PRUNED_COMPLETE


  ELSE:

    search_status ←
      COMPLETE


  diagnostic_log ← {

    algorithm:
      "Hierarchical Cluster Mirror",

    algorithm_class:
      "bounded near-optimal heuristic",

    city_count:
      n,

    cluster_count:
      cardinality(G),

    cluster_size_limit:
      cluster_size_limit,

    cluster_map:
      K,

    route_tolerance:
      ε,

    pruning_tolerance:
      ε_prune,

    maximum_macro_branches:
      maximum_macro_branches,

    maximum_internal_orders:
      maximum_internal_orders,

    maximum_search_states:
      maximum_search_states,

    states_generated:
      B.states_generated,

    states_expanded:
      B.states_expanded,

    branches_pruned:
      B.branches_pruned,

    branches_dropped_by_width:
      B.branches_dropped_by_width,

    mirror_reductions:
      B.mirror_reductions,

    internal_routes_evaluated:
      B.internal_routes_evaluated,

    incumbent_updates:
      B.incumbent_updates,

    baseline_distance:
      B.baseline_distance,

    best_distance:
      B.best_distance,

    relative_improvement:
      (
        B.baseline_distance
        -
        B.best_distance
      )
      /
      B.baseline_distance,

    search_budget_exhausted:
      B.search_budget_exhausted,

    global_optimum_claimed:
      false,

    route_quality:
      route_quality
  }


  EMIT:

    best_tour:
      B.best_tour

    best_distance:
      B.best_distance

    route_quality:
      route_quality

    search_status:
      search_status

    diagnostic_log:
      diagnostic_log


# =============================================================================
# 27. FORMAL HEURISTIC MODEL
# =============================================================================

FORMAL:

  C :=
    complete city set


  K :=
    ComputeProximityGrids(
      C,
      D,
      cluster_size_limit
    )


  G :=
    UniqueClusters(K)


  Ω_bounded :=
    tours generated under:

      - cluster locality
      - maximum_macro_branches
      - maximum_internal_orders
      - maximum_search_states
      - mirror pruning
      - local repair


  τ_best :=

    argmin_{
      τ ∈ Ω_bounded
    }

    Length(τ,D)


  output guarantee:

    τ_best is the shortest tour discovered inside Ω_bounded


  output non-guarantee:

    τ_best is not asserted to equal:

      argmin_{
        τ ∈ Ω_all
      }

      Length(τ,D)


# =============================================================================
# 28. SCALING MODEL
# =============================================================================

SCALING:

  unrestricted_tsp:

    worst_case_growth:
      factorial in n


  hierarchical_cluster_mirror:

    cluster_creation:
      polynomial

    macro_matrix_creation:
      polynomial

    mirror_reduction_per_state:
      polynomial

    branch_search:
      explicitly bounded by maximum_search_states

    branch_width:
      explicitly bounded by maximum_macro_branches

    internal_search:
      explicitly bounded by maximum_internal_orders


  effective_execution_ceiling:

    total_state_expansion
    <=
    maximum_search_states


  therefore:

    computation remains bounded even as towns are added


# =============================================================================
# 29. TOWN ADDITION UPDATE MODEL
# =============================================================================

TRANSFORM T_ADD_CITY(new_city,new_distances):

  REQUIRE:

    new_city ∉ C


  C_next ←
    C ∪ {new_city}


  D_next ←
    ExtendDistanceMatrix(
      D,
      new_city,
      new_distances
    )


  nearest_clusters ←

    rank(
      G,
      by:

        min_{u ∈ Cities(g)}
          D_next[new_city,u]
    )


  target_cluster ←
    first(nearest_clusters)


  IF cardinality(Cities(target_cluster))
  <
  cluster_size_limit:

    Cities(target_cluster) ←
      Cities(target_cluster) ∪ {new_city}

    K[new_city] ←
      target_cluster


  ELSE:

    local_region ←

      Cities(target_cluster)
      ∪
      {new_city}


    local_repartition ←

      ComputeProximityGrids(
        local_region,
        D_next,
        cluster_size_limit
      )


    replace only affected local clusters


  rebuild:

    affected D_macro rows

    affected D_macro columns


  preserve:

    unaffected clusters

    unaffected macro transitions

    existing best route as seed


  insert new_city into incumbent route using:

    minimum insertion cost


  rerun bounded search only across:

    - affected cluster
    - neighbouring clusters
    - changed macro transitions


  full global rebuild required:
    false

  unless:
    local quality degradation exceeds ε


# =============================================================================
# 30. EXECUTION GUARANTEE
# =============================================================================

EXECUTION_GUARANTEE:

  This flow guarantees:

    - every emitted route is complete

    - every city appears exactly once before return to the start city

    - city clustering limits the initial search space

    - internal cluster traversal is locally resolved

    - regional branch width is explicitly bounded

    - total state expansion is explicitly bounded

    - mirror penalties remove comparatively poor regional transitions

    - a valid fallback route exists before deeper search begins

    - search may terminate safely when the computational budget is reached

    - local route repair improves the discovered route without reopening the
      unrestricted factorial search space

    - new towns may be inserted through local cluster reconstruction rather
      than complete global recomputation

    - the result is the best route found within the declared hierarchy,
      tolerances and execution budget


  This flow does not guarantee:

    - the mathematical global TSP optimum

    - a fixed approximation ratio relative to an unknown global optimum

    - elimination of all exponential behaviour without explicit search limits

    - that clustering will preserve every globally superior cross-cluster route


  The deliberate exchange is:

    reduced computational demand
    +
    scalable town addition
    +
    executable low-power reasoning

    in return for:

    controlled loss of global optimality


# =============================================================================
# 31. APPROVAL
# =============================================================================

APPROVAL:

  logical_structure:
    approved

  low_power_execution_model:
    approved

  bounded_search:
    approved

  hierarchical_clustering:
    approved

  tolerance_based_pruning:
    approved

  incremental_town_addition:
    approved

  global_optimum_claim:
    explicitly_rejected

  approved_classification:
    "Bounded Hierarchical Near-Optimal TSP Flow"


# =============================================================================
# 32. EXECUTE
# =============================================================================

EXECUTE:

  T_INIT

  T_SEARCH

  T_TERM


# =============================================================================
# END FLOW
# =============================================================================
```