Answers.Body: <p>Since you mention the <strong>A* algorithm</strong>, then you are definitely using a heuristic somewhere in there, at least with the A* algorithm while solving the subproblems using the straight-line distance as your <strong>heuristic function</strong>.</p>
  
  <p>Although your approach does not seem to incorporate a "shortcut mathematical formula" as a heuristic after that, it does us a precalculated <strong>heuristic table</strong> as a reference and that may qualify as a heuristic. Wikipedia page <a href="https://en.wikipedia.org/wiki/Heuristic_(computer_science)" rel="nofollow">here</a> says (although without citation) the following which does seem to describe what you are doing where your heuristic is not a fixed but a precalculated function/table:</p>
  
  <blockquote>
    <p>A heuristic function, also called simply a heuristic, is a function
    that ranks alternatives in search algorithms at each branching step
    based on available information to decide which branch to follow. For
    example, it may approximate the exact solution.</p>
  </blockquote>
  
  <p>On another note, your method also seems to have hints of <strong>dynamic programming</strong> since you use the precalculated and stored solutions to subproblems and instead of recalculating every time.</p>
  
  <p>I wonder if the term <strong>approximate dynamic programming</strong> would fit this situation as a non-stochastic version with no uncertainties? Unfortunately I could not find any simple description or categorization for that term.</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2016-10-04T07:22:16.297Z
Answers.Text: Good catch with A* using heuristics.
Answers.UserDisplayName: SF.
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2016-10-03T20:01:07.193Z
Answers.LastActivityDate: 2016-10-03T20:01:07.193Z
Answers.UserDisplayName: hekimgil
Answers.Body: <p>Whether or not a label fits any particular instance depends on what you're using the label for. If something specific is riding on whether this approach is a 'heuristic' or not, that context is important.</p>
  
  <p>But I wouldn't call this a heuristic, because I think of that as a shortcut for <em>solving</em> a problem, not either <em>storing</em> a solution or <em>reformulating</em> the problem (which is how I'd think of this). </p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2016-09-29T15:08:10.713Z
Answers.LastActivityDate: 2016-09-29T15:08:10.713Z
Answers.UserDisplayName: Matthew Gray
Answers.Body: <p>A 'heuristic' is simply a 'rule-of-thumb', i.e. something which doesn't guarantee an optimal solution to a problem.</p>
  
  <p>Beyond the above notion (certainly within the discipline of optimization), the notion of what constitutes a heuristic is not particularly strict, and could certainly include hints for constructing a new solution from parts of a previous one, as you are doing.</p>
  
  <p>A related concrete example is the "nearest neighbour heuristic" for the Travelling Salesman Problem, in which a solution is constructed by starting at some random city and iteratively choosing the nearest. The resulting completed tour is then used as an initial input to some more sophisticated optimization procedure.</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2016-10-02T18:49:55.890Z
Answers.LastActivityDate: 2016-10-02T18:49:55.890Z
Answers.UserDisplayName: NietzscheanAI
Body: <p>This is a question about a nomenclature - we already have the algorithm/solution, but we're not sure whether it qualifies as utilizing heuristics or not.</p>
  
  <hr>
  
  <p>feel free to skip the problem explanation:</p>
  
  <blockquote>
    <p>A friend is writing a path-finding algorithm - an autopilot for an
    (off-road) vehicle in a computer game. This is a pretty classic
    problem - he finds a viable, not necessarily optimal but "good enough"
    route using the A* algorithm, by taking the terrain layout and vehicle
    capabilities into account, and modifying a direct (straight) line path
    to account for these. The whole map is known a'priori and invariant,
    though the start and destination are arbitrary (user-chosen) and the
    path is not guaranteed to exist at all.</p>
    
    <p>This cookie-cutter approach comes with a twist: limited storage space.
    We can afford some more volatile memory on start, but we should free
    most of it once the route has been found. The travel may take days -
    of real time too, so the path must be saved to disk, and the space in
    the save file for custom data like this is severely limited. Too
    limited to save all the waypoints - even after culling trivial
    solution waypoints ('continue straight ahead'), and by a rather large
    margin, order of 20% the size of our data set.</p>
    
    <p>A solution we came up with is to calculate the route once on start,
    then 'forget' all the trivial and 90% of the non-trivial waypoints.
    This both serves as a proof that a solution exists, and provides a set
    of points reaching which, in sequence, guarantees the route will take
    us to the destination.</p>
    
    <p>Once the vehicle reaches a waypoint, the route to the next one is
    calculated again, from scratch. It's known to exist and be correct
    (because we did it once, and it was correct), it doesn't put too much
    strain on the CPU and the memory (it's only about 10% the total route
    length) and it doesn't need to go into permanent storage (restarting
    from any point along the path is just a subset of the solution
    connecting two saved waypoints).</p>
  </blockquote>
  
  <hr>
  
  <p>Now for the actual question:</p>
  
  <p>The pathfinding algorithm follows a sparse set of waypoints which by themselves are not nearly sufficient as a route, but allow for easy, efficient  calculation of the actual route, simultaneously guarantying its existence; they are a subset of the full solution. </p>
  
  <p>Is this a heuristic approach?</p>
  
  <p>(as I understand, normally, heuristics don't guarantee existence of a solution, and merely suggest more likely candidates. In this case, the 'hints' are taken straight out of an actual working solution, thus my doubts.)</p>
  
Tags: <heuristics><path-planning>
Title: Is a subset of a problem solution, used to recreate complete solution considered a heuristic?
UserDisplayName: SF.
ThreadText: # Is a subset of a problem solution, used to recreate complete solution considered a heuristic?
  
  (Asked by: username_0 on 2016-09-29)
  
  This is a question about a nomenclature - we already have the algorithm/solution, but we're not sure whether it qualifies as utilizing heuristics or not.
  
  ---
  
  feel free to skip the problem explanation:
  
  > A friend is writing a path-finding algorithm - an autopilot for an
  > (off-road) vehicle in a computer game. This is a pretty classic
  > problem - he finds a viable, not necessarily optimal but "good enough"
  > route using the A\* algorithm, by taking the terrain layout and vehicle
  > capabilities into account, and modifying a direct (straight) line path
  > to account for these. The whole map is known a'priori and invariant,
  > though the start and destination are arbitrary (user-chosen) and the
  > path is not guaranteed to exist at all.
  >
  > This cookie-cutter approach comes with a twist: limited storage space.
  > We can afford some more volatile memory on start, but we should free
  > most of it once the route has been found. The travel may take days -
  > of real time too, so the path must be saved to disk, and the space in
  > the save file for custom data like this is severely limited. Too
  > limited to save all the waypoints - even after culling trivial
  > solution waypoints ('continue straight ahead'), and by a rather large
  > margin, order of 20% the size of our data set.
  >
  > A solution we came up with is to calculate the route once on start,
  > then 'forget' all the trivial and 90% of the non-trivial waypoints.
  > This both serves as a proof that a solution exists, and provides a set
  > of points reaching which, in sequence, guarantees the route will take
  > us to the destination.
  >
  > Once the vehicle reaches a waypoint, the route to the next one is
  > calculated again, from scratch. It's known to exist and be correct
  > (because we did it once, and it was correct), it doesn't put too much
  > strain on the CPU and the memory (it's only about 10% the total route
  > length) and it doesn't need to go into permanent storage (restarting
  > from any point along the path is just a subset of the solution
  > connecting two saved waypoints).
  
  ---
  
  Now for the actual question:
  
  The pathfinding algorithm follows a sparse set of waypoints which by themselves are not nearly sufficient as a route, but allow for easy, efficient calculation of the actual route, simultaneously guarantying its existence; they are a subset of the full solution.
  
  Is this a heuristic approach?
  
  (as I understand, normally, heuristics don't guarantee existence of a solution, and merely suggest more likely candidates. In this case, the 'hints' are taken straight out of an actual working solution, thus my doubts.)
  
  **Tags:** heuristics, path-planning
  
  
  ---
  
  ## 3 answers
  
  ### Answer by username_1 on 2016-10-03. Score: 1 | Accepted answer
  
  Since you mention the **A\* algorithm**, then you are definitely using a heuristic somewhere in there, at least with the A\* algorithm while solving the subproblems using the straight-line distance as your **heuristic function**.
  
  Although your approach does not seem to incorporate a "shortcut mathematical formula" as a heuristic after that, it does us a precalculated **heuristic table** as a reference and that may qualify as a heuristic. Wikipedia page [here](https://en.wikipedia.org/wiki/Heuristic_(computer_science)) says (although without citation) the following which does seem to describe what you are doing where your heuristic is not a fixed but a precalculated function/table:
  
  > A heuristic function, also called simply a heuristic, is a function
  > that ranks alternatives in search algorithms at each branching step
  > based on available information to decide which branch to follow. For
  > example, it may approximate the exact solution.
  
  On another note, your method also seems to have hints of **dynamic programming** since you use the precalculated and stored solutions to subproblems and instead of recalculating every time.
  
  I wonder if the term **approximate dynamic programming** would fit this situation as a non-stochastic version with no uncertainties? Unfortunately I could not find any simple description or categorization for that term.
  
  > **Comments:**
  > **username_0**: Good catch with A* using heuristics.  
  
  ---
  
  ### Answer by username_2 on 2016-09-29. Score: 1
  
  Whether or not a label fits any particular instance depends on what you're using the label for. If something specific is riding on whether this approach is a 'heuristic' or not, that context is important.
  
  But I wouldn't call this a heuristic, because I think of that as a shortcut for *solving* a problem, not either *storing* a solution or *reformulating* the problem (which is how I'd think of this).
  
  
  ---
  
  ### Answer by username_3 on 2016-10-02. Score: 1
  
  A 'heuristic' is simply a 'rule-of-thumb', i.e. something which doesn't guarantee an optimal solution to a problem.
  
  Beyond the above notion (certainly within the discipline of optimization), the notion of what constitutes a heuristic is not particularly strict, and could certainly include hints for constructing a new solution from parts of a previous one, as you are doing.
  
  A related concrete example is the "nearest neighbour heuristic" for the Travelling Salesman Problem, in which a solution is constructed by starting at some random city and iteratively choosing the nearest. The resulting completed tour is then used as an initial input to some more sophisticated optimization procedure.
  
  
  ---
  
  