Прогрессивная аппроксимация

Рисунок 24 - больший граф поиска, 8.5 млн.

Чтобы сделать рассмотрение более подробным, до настоящего времени все приведенные примеры использовали относительно малую область поиска. Они все занимают в большинстве случаев нескольких секунд расчета. Для того чтобы понять эффективность работы на больших графах давайте рассмотрим рисунок 24, который показывает путь, где расстояние между источником и адресатом - приблизительно 64 км (размер ячейки - 25 м). Для ясности, рисунок только указывает главные дороги и позволяет различить разные типы местности воду, город или другую. Фактические данные графа для поиска такие же, как в предыдущих примерах, только намного больше, поэтому они не представлены подробно. Полный граф для поиска, содержит приблизительно 8.5 миллионов вершин. Враги отсутствуют. При использовании стандартного алгоритма, расчет занял 48 сек, на Pentium 133 с 18МБ свободной памяти. Время для выборки растровых данных не учитано. Большинство времени было отнято управлением виртуальной памятью на жестком диске. Для сравнения, вычисление 'грубого' решения при коэффициенте 6 укрупненного графа заняло только 2.5s! Насколько хорош прогрессивный метод при той же проблеме? Это незначительно зависит от выбранной длины сегмента; при большом количестве сегментов, большое количество непроизводительных затрат; поэтому их должны быть немного (то есть длинные) насколько возможно. С другой стороны, если они слишком длинные, мы снова исчерпаем память, и на обмен с диском будет тратиться много времени. Рисунок 25 показывает график времени от длины сегмента для нескольких тестов. Все эти тесты использовали 6-кратное укрупненное приблизительное решение, которые были затем разделены на сегменты различных длин. Длина сегмента выражена как число граней в укрупненном графе решения (то есть 1/6-ой из числа граней в точном графе). Во всех упомянутых случаях (даже один 6-кратный укрупненный граф) результат фактически был визуально неразличим на рисунке 24 вследствие того, что размер ячейки был намного меньше, чем экранный пиксел. 8.6