Why are search problems assumed to have the structure of "find a path in a graph"?

Question

I have skimmed a few introductions to "search problems", and I have noticed that:

1. Stated informally search problems are defined as "find an object y inside a larger space/object X"

2. But when defining exact algorithms, search problems are thought of as "search inside a graph" or more specifically "finding a path inside a graph".

The texts I have read don't clearly explain the jump from 1 to 2 (at least not clear to me).

For example, wikipedia's search problem page states: Generic search algorithm: given a graph, start nodes, and goal nodes, incrementally explore paths from the start nodes. But also in textbooks such as Artificial Intelligence: A Modern Approach (Russell & Norvig), and others.

Why is this? Can we always represent any search problem as "search for a path inside a graph"? I am having trouble to see how. It seems very specific to focus specifically on path search in graphs. Aren't there many other types of search? (e.g. find a pattern in an image, or find a substrring in a string, or find an efficient algorithm that computes a function, etc).

Answer 1

You are completely right: The problems we call search problems are typically problems that can be modeled as a graph problem. The general gist of it is that there are "states", "locations", or whatever, that we often call nodes or vertices, and then you can move between states or locations, through things we call edges or arcs, or transitions. These can have properties, such as directions, weights, and other things.

There are other problems where we "search" for things that are not typically called search problems, and you correctly pointed out several of them. Finding or detecting patterns or objects in images are often called image recognition or pattern matching, finding patterns in strings is often referred to as pattern matching or string search, and searching for outliers in data sets is often referred to as outlier detection or anomaly detection etc.

Summarizing, search problems is usually used to describe problems where we are looking for paths or distances in problems that can be modeled using the language of graph theory.

Answer 2

There are at least two meanings of the word "search problem".

In one context, we use the phrase "search problem" to refer to searching for paths in a graph, or making a sequence of decisions. To make the context clearer, sometimes people refer to this as "graph search". See https://en.wikipedia.org/wiki/Graph_traversal.

In another context, we use the phrase "search problem" to refer to trying to find an object $y$ that has certain properties. For instance, we might be given a 3SAT formula, and the goal is to find a satisfying assignment. This particularly comes up in defining NP, and in distinguishing between a search problem vs a decision problem.

Even the Wikipedia page on search problems seems confused about these two distinct notions, and appears to conflate the two. The current version of that page starts out by defining a "search problem" to refer to the latter notion; but then some subsequent sections discuss the former notion. The 'talk page' seems to be aware that the Wikipedia page has serious problems, but it looks like they haven't been addressed yet.

It is certainly possible to express graph search ("search problem" in the first sense) as an instance of a "search problem" in the latter sense. For example, the input is a graph, a start vertex $s$, and an end vertex $t$; the goal is to find a path (a sequence of vertices where each consecutive pair is joined by an edge in this graph) whose first vertex is $s$ and last vertex is $s$. That is an instance of a search problem. Graph traversal algorithms like DFS and BFS are particular algorithms that can be used to solve that problem.

Answer 3

The objective of a search problem is to construct a description of an object that satisfies a specific property. The internal structure of possible descriptions is like a possibly infinite graph.

Some problems, say binary search in a list and pattern matching, degenerates, where the thing to be searched is just an index on a linear path. They are not usually considered the same problem as the general search. But as you can't say a linear path is not a graph, it serves no purpose to set an exact boundary between them.

Other "real" searching problems comes from two forms: the ones with an actual graph given as a complete description, and the ones that could be considered a graph in an abstract way, with nodes generated on the fly, sometimes having multiple interpretations of the exact structure. They might be approached and solved very differently, but mostly because for the ones with a complete description of the graph, there is a lower bound of the time complexity that is related to the size of the input, and there is not much to optimize. Algorithms on one set of problems is likely to be applicable to the other, even if far-fetched and not working better.