Релаксационные методы
Альтернатива алгоритму 'в глубину' для выполнения полного перебора так называемый алгоритм поиска 'ширина вначале', см. [CORM90], стр. 469 .. 477. Он получил название по способу, которым он расширяет 'фронт поиска' из точки начала (в решающем дереве).
Этот вариант не дает больших преймуществ по сравнению с предыдущим методом. Однако, здесь есть основной класс алгоритмов поиска на графе, основанный на методике так называемой 'релаксацией', см. [CORM90], при котором используют идеи, очень схожие с алгоритмом поиска в ширину, но с некоторыми определяющими уточнениями. Наиболее общие из них, применимы для текущей задачи, классические: алгоритмы Дийкстры и Беллмана-Форда. Они оба определяют все оптимальные пути из 'одиночного источника' к всякой другой вершине. Алгоритм Дийкстры быстрее, но необходимо, чтобы не было никаких отрицательных издержек грани; которые мы имеем, как удостоверелись в разделе три. A* алгоритм эффективное эвристическое уточнение алгоритма Дийкстры, который имеет лучшую среднюю эффективность, когда надо найти оптимальный путь между двумя вершинами (и не от одной вершины до всех других). Потому что он обеспечивает хорошое, предсказуемое быстродействие без того, чтобы подвергать сомнению, этот алгоритм, выбран для нашей реализации теста; см. раздел 4.2.7.1.3
Еще по теме Релаксационные методы:
-
Автоматизация -
Гидрология -
Документоведение, делопроизводство -
Информационные системы -
Коммуникации -
Криптография -
Машиностроение -
Метрология -
Механика -
Микроэлектроника -
Нефтегазовое дело -
Пищевая промышленность -
Приборостроение -
Программирование -
Системный анализ, управление и обработка информации -
Строительство -
Технология и оборудование механической и физико-технической обработки -
Электрическая энергия -
Энергетика -
-
Архитектура и строительство -
Безопасность жизнедеятельности -
Библиотечное дело -
Бизнес -
Биология -
Военные дисциплины -
География -
Геология -
Демография -
Диссертации России -
Естествознание -
Журналистика и СМИ -
Информатика, вычислительная техника и управление -
Искусствоведение -
История -
Культурология -
Литература -
Маркетинг -
Математика -
Медицина -
Менеджмент -
Педагогика -
Политология -
Право России -
Право України -
Промышленность -
Психология -
Реклама -
Религиоведение -
Социология -
Страхование -
Технические науки -
Учебный процесс -
Физика -
Философия -
Финансы -
Химия -
Художественные науки -
Экология -
Экономика -
Энергетика -
Юриспруденция -
Языкознание -