Flinders Petrie, the travelling salesman problem, and the beginning of mathematical modeling in archaeology
type: Item
instance of: scholarly article
title: Flinders Petrie, the travelling salesman problem, and the beginning of mathematical modeling in archaeology
zbMATH Open document ID: 1263.01011
author: Thomas L. Gertzen
author: Martin Grötschel
published in: Documenta Mathematica
publication date: 2013-04-17T00:00:00Z
full work available at URL: 35 gertzen-thomas-groetschel-martin.html
review text: William Matthew Flinders Petrie (1853--1942) was the first one to employ mathematical methods in order to study archaelogical findings. As it turns out, Petrie introduced the concepts of \textit{Hamming metric}, and of \textit{seriation}, solving the travelling salesman problem (henceforth, simply TSP), exhibiting a mathematical model of the graveyard in Naqada (Egypt). What is surprising is that Petrie was only an amateur and not a proper mathematician. At any rate, the first problem Petrie faced was to fix the chronological distance between the various graves. For this purpose he employed the Hamming metric according to which the distance between two vectors is given by the number of different components in the same place. For example, given two vectors \(v = \{ x_1,\ldots,x_n\}\) and \(u = \{ y_1,\ldots,y_m\}\), and supposing that \(x_i = y_i\) for any \(1 \leq i \leq n,m\) except at \(j\) and \(k\) where \(v\) and \(u\) differ, then the distance between \(v\) and \(u\) is \(2\). Formally, \(\text{ dist}(v,u) = 2 \). In the case of Petrie, the vectors are ``graves'' and the components are the relative ``items of pottery''. So, the more pottery is in common, the closer are the graves in time. But this is not all. Petrie introduced also a matrix \(A\) of this form: \[ \begin{matrix} & B & P & F & C & N & W & D & R & L\\ g_1 & & & & & & & &\\ g_2 & & & & & & & &\\ g_3 & & & & & & & &\\ . & & & & & & & &\\ . & & & & & & & &\\ . & & & & & & & &\\ \end{matrix} \] The columns indicate what type of pottery is associated to the graves (represented in the rows, as \(g_1,g_2,\ldots\)). Then, one entry \(a_{ij} = 1\) iff the grave \(g_i\) presents pottery of type \(j\), \(0\) otherwise. For example, the grave B130 has the entries: \(a_{\mathrm{B}130, B}\), \(a_{\mathrm{B}130, F}\), \(a_{\mathrm{B}130, N}\); i.e.: \[ \begin{matrix} & B & P & F & C & N & W & D & R & L\\ \text{B}130 & 1 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0\\ \end{matrix} \] This means that the grave B130 has pottery…
reviewed by: Davide Bondoni
Mathematics Subject Classification ID: 01A55
Mathematics Subject Classification ID: 05-03
Mathematics Subject Classification ID: 90-03
Mathematics Subject Classification ID: 90C27
zbMATH DE Number: 6155090
zbMATH Keywords: travelling salesman problem
zbMATH Keywords: seriation
zbMATH Keywords: Hamming metric
zbMATH Keywords: archaeology
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 6155090