Новый взгляд на мир. Фрактальная геометрия | страница 51
ОПТИМАЛЬНЫЙ МАРШРУТ КОММИВОЯЖЕРА
В 1912 г. Серпинский незадолго до того, как открыл треугольник, названный в его честь, занимался изучением кривой, которая строилась по рекурсивному алгоритму и покрывала плоскость.
Сейчас эта кривая используется для решения задачи коммивояжера, в которой необходимо найти кратчайший маршрут, проходящий через определенные точки плоскости. Одна из возможных стратегий — обойти точки в той же последовательности, которую описывает кривая Серпинского. Для этого необходимо, во-первых, сформировать подобную кривую и нарисовать ее так, чтобы она покрывала все нужные точки маршрута. Если это не удалось, нужно использовать кривую Серпинского следующей итерации. Как только нам удалось построить кривую, которая проходит через все требуемые точки, искомый маршрут найден. Этот алгоритм применяется, например, при расчете маршрутов доставки почтовых посылок. Он также позволяет сократить общее расстояние, которое проходит перо плоттера при отрисовке карт.
* * *
Иными словами, размерность Минковского равна значению выражения log N (ε) / log (1/ε), когда ε стремится к 0.
Эта формула находит свое применение при подсчете клеток. Выполняются практически те же действия, что и при измерении расстояний на карте с помощью циркуля. Дана фигура, размерность которой мы хотим найти. Фигура помещается поверх сетки с шагом ε, который принимает значения 1 мм, 1 см и так далее в зависимости от размеров фигуры. Затем подсчитывается число квадратиков или клеток, которые покрывает фигура. Будем постепенно уменьшать значение и подсчитывать соответствующее число клеток для каждого. Затем, подобно алгоритму Ричардсона, построим график, осями которого будут логарифмические шкалы. На оси абсцисс будем обозначать логарифмы 1/ε, на оси ординат — логарифмы N(ε). Угловой коэффициент прямой, аппроксимирующей точки графика, будет равен D>M. Эта процедура применима к любым прямым, плоскостям и пространствам.
Подсчет клеток привлекает своей простотой, но размерности Минковского не хватает некоторых свойств, желательных с теоретической точки зрения. Немецкий математик Феликс Хаусдорф (1868–1942) из Боннского университета занимался теорией измерений и предложил новое определение размерности. Оно не применяется на практике, но имеет большое теоретическое значение и порой полезно для сравнения размерности некоторых разнородных множеств, которые имеют одинаковую размерность Минковского. В целом размерность Хаусдорфа меньше или равна размерности Минковского.
