Optimal-Path Search Task

An Optimal-Path Search Task is a path search task that is an optimization task (minimization or maximization).

• AKA: Optimal Path Problem.
• Context:
  • Input: a Graph [math]\displaystyle{ G = (V, E) }[/math], a Graph Edge Weight Function [math]\displaystyle{ c : E \rightarrow \mathbb{R}^+ }[/math], and a Requirement Function.
  • output: an Optimal Path.
  • It can range from being a Shortest Path Finding Task to finding a Longest Path Finding Task.
  • It can range from being a Directed Graph Optimal-Path Finding Task to being an Undirected Graph Optimal-Path Finding Task.
  • It can range from being a Lattice Optimal-Path Finding Task to being a General-Graph Optimal-Path Finding Task.
  • It can range from being a Constrained Optimal-Path Search Task to being an Unconstrained Optimal-Path Search Task.
  • It can range from being a Simple Optimal-Path Search Task to being a Multiple Optimal-Path Search Task.
  • It can be solved by an Optimal-Path Finding System that applies an (optimal-path finding algorithm).
• Example(s):
  • an Optimal-Cycle Search Task, such as a traveling salesperson task.
  • …
• Counter-Example(s):
  • an Optimal-Subgraph Finding Task.
  • a Link-based Object Ranking Task.
• See: Path Optimization Algorithm.

---

---

References

2017

• (Wikipedia, 2017) ⇒ https://en.wikipedia.org/wiki/pathfinding Retrieved:2017-10-8.
  • Pathfinding or pathing is the plotting, by a computer application, of the shortest route between two points. It is a more practical variant on solving mazes. This field of research is based heavily on Dijkstra's algorithm for finding a shortest path on a weighted graph.

    Pathfinding is closely related to the shortest path problem, within graph theory, which examines how to identify the path that best meets some criteria (shortest, cheapest, fastest, etc) between two points in a large network.

---