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