Shortest Path seriation is a seriation Technique used in OptiPath and described in a paper by Brett Shepardson and Fred Shepardson which is being prepared for publication. The seriation Technique can be set in the Seriations table.
The object of seriation is to determine an ordering of a number of items (assemblages or artifacts) that replicates as closely as possible the historical order of events that they represent. As with all seriation techniques, shorrtest path seriation relies on the assumption that the artifacts to be seriated share characteristics or features whose measures evolve gradually over time. The ordering of artifacts that produces the most gradual evolution of all features for all artifacts is considered the optimal seriation. Alternatively, one could use the Objective to Maximize Unimodality to maximize unimodality.
Shortest Path seriation is a special case of the Optimal Path seriation model. Setting the seriation parameter Technique to Shortest Pathspecifies OptiPath's standard implementation of Shortest Path seriation. Data may take on any numerical value. Blanks are treated as absent and unknown value. All other numerical values are taken to indicate the presence of the feature and non-numerical values are treated as unknowns. Setting the seriation parameter Technique to Shortest Pathcauses OptiPath to automatically set the feature parameters Data, Ranks, Metric, Normalize, Transition, Earlier, Later, Blanks and Zeroes to specific values.
When OptiPath optimizes the gradualness of the rate of change of features in the seriation, the problem is a variant of the Hamiltonian path problem with time windows. There are no known algorithms that will solve large problems optimally in a heuristic technique that produces good answers with moderate effort. If there are no Earliest or Latest dates assigned to individual artifacts, this model simplifies to one of minimizing the total distance of the path determined by the seriation. This problem can be solved as a Hamiltonian path problem, a variant of the traveling salesman problem. Although this problem is easier than the problem with time windows, there are still no known algorithms that will solve large problems optimally in a reasonable amount of time. OptiPath uses a heuristic technique that produces good answers with moderate effort, less than that required for the problem with time windows.
The following are the default feature parameter settings for shortest path seriation. To change them you must first select the Custom Seriation technique.
| Parameter | Value |
| Data | Measured |
| Ranks | 0 |
| Metric | Euclidean |
| Normalize | Yes |
| Transition | 5 |
| Earlier | Absent & Unknown |
| Later | Absent & Unknown |
| Blanks | Absent & Unknown |
| Zeroes | Present & Zero |
These settings result in any numerical entry in the Data being interpreted as indicating the presence of a feature (class or style). If you do not want blanks or zeroes to be interpreted in this way, you should set the seriation parameter Technique to Custom and reset the feature parameters Blanks and Zeroes.
In shortest path seriation, careful thought should be put into setting the feature parameters appropriately - see Setting the Earlier, Later, Blanks, Zeroes and Transition Parameters.