A grocery retailer builds each delivery route by appending the near…

Question

A grocery retailer builds each delivery route by appending the nearest unvisited store at every step. A planner finds a short first hop that forces a much longer trip later in the day. Which limitation of this route construction should the planner name?

Accepted Answer

Each step takes the locally best next store, so the route can miss a shorter full tour that would have started with a slightly longer first hop — Grabbing the closest donut can leave you across the room from the short path. You are looking at a greedy route: each hop is the local best and can miss a shorter tour. The trap is believing the nearest store is optimal just because every individual hop looked smart.

Answer

Each step already accounts for the full tour cost, so the nearest-store rule cannot miss a shorter route once the distances are ordinary road miles

Answer

The construction fails only when some road distances are negative, and with positive miles the nearest unvisited store yields the shortest full tour

Answer

The next store is chosen at random, so a costly later hop is sampling noise rather than a systematic preference for the locally nearest store

A grocery retailer builds each delivery route by appending the nearest unvisited store at every step. A planner finds a short first hop that forces a much longer trip later in the day. Which limitation of this route construction should the planner name?

Short Explanation

Full Explanation