Теорема коммивояжера аналитиков - Analysts traveling salesman theorem - Wikipedia

В задача коммивояжера аналитика является аналогом задача коммивояжера в комбинаторная оптимизация. В своей простейшей и оригинальной форме он спрашивает, при каких условиях может E в двухмерном Евклидово пространство ${\displaystyle \mathbb {R} ^{2}}$ содержаться внутри выпрямляемая кривая конечной длины. Таким образом, в то время как в исходной задаче коммивояжера требуется кратчайший путь для посещения каждой вершины графа дискретным путем, эта аналитическая версия требует, чтобы кривая посетила, возможно, бесконечно много точек.

β-числа

A posteriori, для E содержаться в спрямляемой кривой Γ, поскольку Γ имеет касательные в ЧАС¹-почти каждая точка в Γ (где ЧАС¹ обозначает одномерный Мера Хаусдорфа ), E должен смотреть плоский когда вы приближаете точки в E. Это говорит о том, что условие, которое скажет нам, может ли набор содержаться в кривой, должно каким-то образом включать информацию о том, насколько плоский E это когда мы приближаем точки E в разных масштабах.

Это обсуждение мотивирует определение следующей величины:

${\displaystyle \beta _{E}(Q)={\frac {1}{\ell (Q)}}\inf\{\delta :{\text{ there is a line }}L{\text{ so that for every }}x\in E\cap Q,\;{\text{dist}}(x,L)<\delta \},}$

Где Q это любой квадрат, ${\displaystyle \ell (Q)}$ это сторона Q, и расст (Икс, L) измеряет расстояние от Икс к линии L. Интуитивно ${\displaystyle 2\beta _{E}(Q)\ell (Q)}$ ширина наименьшего прямоугольника, содержащего часть E внутри Q, и поэтому ${\displaystyle \beta _{E}(Q)}$ дает нам масштабно-инвариантное понятие плоскостность.

Теорема Джонса о коммивояжере в R²

Обозначим через Δ набор диадических квадратов, т. Е.

${\displaystyle \Delta =\{[i2^{k},(i+1)2^{k}]\times [j2^{k},(j+1)2^{k}]:i,j,k\in \mathbb {Z} \},}$

куда ${\displaystyle \mathbb {Z} }$ обозначает набор целых чисел. Для набора ${\displaystyle E\subseteq \mathbb {R} ^{2}}$, определять

${\displaystyle \beta (E)={\text{diam}}E+\sum _{Q\in \Delta }\beta _{E}(3Q)^{2}\ell (Q)}$

где диаметр E это диаметр из E. потом Питер Джонс с^[1] Теорема коммивояжера аналитика может быть сформулирована следующим образом:

• Есть номер C > 0 такой, что всякий раз, когда E это набор с таким, что β(E) < ∞, E может содержаться в кривой длиной не более Cβ(E).
• Наоборот (что значительно труднее доказать), если Γ - спрямляемая кривая, то β(Γ) 1(Γ).

Обобщения и кривизна Менгера

Евклидово пространство и гильбертово пространство

Доказано, что теорема о коммивояжере верна в общих евклидовых пространствах. Кейт Окикиолу,^[2] то есть та же теорема выше верна для множеств ${\displaystyle E\subseteq \mathbb {R} ^{d}}$, d > 1, где Δ теперь набор диадических кубов в ${\displaystyle \mathbb {R} ^{d}}$ определяется аналогично диадическим квадратам. В ее доказательстве постоянная C растет экспоненциально с размерностьюd.

С некоторыми небольшими изменениями в определении β(E), Раанан Шуль^[3] показал, что теорема о коммивояжере верна и для множеств E что ложь в любом Гильбертово пространство, и, в частности, следует теоремы Джонса и Окикиолу, где теперь постоянная C не зависит от размерности. (В частности, это предполагает использование β-число шариков вместо кубиков).

Кривизна Менгера и метрические пространства

Hahlomaa^[4] дополнительно скорректировал определение β(E), чтобы получить условие, когда набор E произвольного метрическое пространство может содержаться в Липшиц -изображение подмножества ${\displaystyle A\subseteq \mathbb {R} }$ положительной меры. Для этого ему пришлось пересмотреть определение понятия β-числа с использованием кривизна Менгера (поскольку в метрическом пространстве не обязательно есть понятие куба или прямой).

Искривление по Менгеру, как и в предыдущем примере, может использоваться для получения численных оценок, которые определяют, содержит ли набор исправляемое подмножество, и доказательства этих результатов часто зависят от β-числа.

Теорема Данжуа – Рисса

В Теорема Данжуа – Рисса дает общие условия, при которых точечное множество покрывается гомеоморфным образом кривой. Это верно, в частности, для всякого компакта полностью отключен подмножество евклидовой плоскости. Однако может оказаться необходимым, чтобы такая дуга имела бесконечную длину, что не соответствует условиям теоремы коммивояжера аналитика.

Рекомендации

1. Джонс, Питер (1990). «Выпрямляемые множества и задача коммивояжера». Inventiones Mathematicae. 102: 1–15. Bibcode:1990InMat.102 .... 1J. Дои:10.1007 / BF01233418.
2. Окикиолу, Кейт (1992). «Характеризация подмножеств спрямляемых кривых в Rn». Журнал Лондонского математического общества. 46 (2): 336–348. Дои:10.1112 / jlms / s2-46.2.336.
3. Шуль, Раанан (2007). «Подмножества спрямляемых кривых в гильбертовом пространстве - TSP аналитика». Журнал д'анализа математика. 103: 331–375. arXiv:математика / 0602675. Дои:10.1007 / s11854-008-0011-у.
4. Хахломаа, Иммо (2005). «Кривизна Менгера и липшицевы параметризации в метрических пространствах». Фонд. Математика. 185 (2): 143–169. Дои:10.4064 / FM185-2-3.