Прогрессивная аппроксимация
Рисунок 24 - больший граф поиска, 8.5 млн.
вершин Рисунок 25 - Время против длины сегментаЧтобы сделать рассмотрение более подробным, до настоящего времени все приведенные примеры использовали относительно малую область поиска. Они все занимают в большинстве случаев нескольких секунд расчета. Для того чтобы понять эффективность работы на больших графах давайте рассмотрим рисунок 24, который показывает путь, где расстояние между источником и адресатом - приблизительно 64 км (размер ячейки - 25 м). Для ясности, рисунок только указывает главные дороги и позволяет различить разные типы местности воду, город или другую. Фактические данные графа для поиска такие же, как в предыдущих примерах, только намного больше, поэтому они не представлены подробно. Полный граф для поиска, содержит приблизительно 8.5 миллионов вершин. Враги отсутствуют. При использовании стандартного алгоритма, расчет занял 48 сек, на Pentium 133 с 18МБ свободной памяти. Время для выборки растровых данных не учитано. Большинство времени было отнято управлением виртуальной памятью на жестком диске. Для сравнения, вычисление 'грубого' решения при коэффициенте 6 укрупненного графа заняло только 2.5s! Насколько хорош прогрессивный метод при той же проблеме? Это незначительно зависит от выбранной длины сегмента; при большом количестве сегментов, большое количество непроизводительных затрат; поэтому их должны быть немного (то есть длинные) насколько возможно. С другой стороны, если они слишком длинные, мы снова исчерпаем память, и на обмен с диском будет тратиться много времени. Рисунок 25 показывает график времени от длины сегмента для нескольких тестов. Все эти тесты использовали 6-кратное укрупненное приблизительное решение, которые были затем разделены на сегменты различных длин. Длина сегмента выражена как число граней в укрупненном графе решения (то есть 1/6-ой из числа граней в точном графе). Во всех упомянутых случаях (даже один 6-кратный укрупненный граф) результат фактически был визуально неразличим на рисунке 24 вследствие того, что размер ячейки был намного меньше, чем экранный пиксел. 8.6
Еще по теме Прогрессивная аппроксимация:
- Прогрессивная аппроксимация
- Аппроксимация теоретического описания технической системы
- 7.1.3. Прогрессивность и регрессивность подоходного налога
- Приложение 3. Результаты аппроксимации экспериментальных данных
- Приложение 1 ІА. Аппроксимация квадратичной й кубической кривых
- Прогрессивная политическая партия
- Вопрос № 12. Принцип прогрессивной латерализации в развитии мозговой организации ВПФ.
- Предрассудок прогрессивного развития всего и вся.
- Экономический смысл прогрессивного налогообложения доходов
- Именно в силу этого главного качества сенат был задуман как тормоз на пути прогрессивного и
- 1.3. Дискретные каналы и их модели
- 2. Построение разностных схем методом неопределенных коэффициентов.
- Глава 6Методы расщепления
- 4. Сокращенный сложный силлогизм
- 4.2 Аппроксимативная оценка корреляционной функции
- 4.4 Указания к решению задач РГКР № 2
- 4. Методы расщепления для прикладных задач математической физики