Currently, we have Graphs with all the edges and vertices stored in memory. This is good for small finite graphs. But for use cases like the one given below, quoted from wikipedia,
For instance, in searching for a solution to a puzzle such as Rubik's Cube, one may define an implicit graph in which each vertex represents one of the possible states of the cube, and each edge represents a move from one state to another. It is straightforward to generate the neighbors of any vertex by trying all possible moves in the puzzle and determining the states reached by each of these moves; however, an implicit representation is necessary, as the state space of Rubik's Cube is too large to allow an algorithm to list all of its states.
it isn't possible to store all the vertices and the edges between them in the memory. So, we need to define a representation with the following components,
State/Node
Rule/Algorithm to generate next states from the current state.
The above framework may have different definitions of algorithms which are easily applied on graphs. These kind of implicit graphs are usually used in searching algorithms like, BFS, DFS, IDFS, etc.
A nice description is also given in [1] page 67 section 3.1.1. We can also consider using that representation.
Example of the problem
References/Other comments
.. [1] Artificial Intelligence A Modern Approach, Stuart Russell, Peter Norvig, Prentice Hall (2010)
subhangi2731
commented
3 years ago
Description of the problem
Currently, we have Graphs with all the edges and vertices stored in memory. This is good for small finite graphs. But for use cases like the one given below, quoted from wikipedia,
it isn't possible to store all the vertices and the edges between them in the memory. So, we need to define a representation with the following components,
The above framework may have different definitions of algorithms which are easily applied on graphs. These kind of implicit graphs are usually used in searching algorithms like, BFS, DFS, IDFS, etc.
A nice description is also given in [1] page 67 section 3.1.1. We can also consider using that representation.
Example of the problem
References/Other comments
.. [1] Artificial Intelligence A Modern Approach, Stuart Russell, Peter Norvig, Prentice Hall (2010)