мета-данные страницы
Загрузка не удалась. Возможно, проблемы с правами доступа?
Различия
Показаны различия между двумя версиями страницы.
Предыдущая версия справа и слеваПредыдущая версияСледующая версия | Предыдущая версияСледующая версияСледующая версия справа и слева | ||
links_other [19/02/2019 12:28] – [Алгоритмы] oca | links_other [16/11/2019 11:03] – [Разное] oca | ||
---|---|---|---|
Строка 615: | Строка 615: | ||
[[https:// | [[https:// | ||
- | [[https:// | + | [[https:// |
+ | (Материал из Википедии — свободной энциклопедии)]] | ||
+ | |||
+ | [[https:// | ||
+ | |||
+ | |||
+ | ===== Визуализация алгоритмов ===== | ||
+ | |||
+ | [[https:// | ||
+ | |||
+ | |||
+ | ===== Комбинаторика ===== | ||
+ | |||
+ | === Ссылки === | ||
+ | |||
+ | |||
+ | ===== Графы ===== | ||
+ | |||
+ | [[https:// | ||
+ | |||
+ | === Алгоритмы === | ||
+ | |||
+ | Компиляция (скромная форма плагиата) из Википедии. | ||
+ | |||
+ | В связи с тем, что существует множество различных постановок данной задачи, | ||
+ | |||
+ | * Алгоритм Дейкстры находит кратчайший путь от одной из вершин графа до всех остальных. Алгоритм работает только для графов без рёбер отрицательного веса. | ||
+ | * Алгоритм Беллмана — Форда находит кратчайшие пути от одной вершины графа до всех остальных во взвешенном графе. Вес рёбер может быть отрицательным. | ||
+ | * Алгоритм поиска A* находит маршрут с наименьшей стоимостью от одной вершины (начальной) к другой (целевой, | ||
+ | * Алгоритм Флойда — Уоршелла находит кратчайшие пути между всеми вершинами **взвешенного ориентированного графа**. | ||
+ | * Алгоритм Джонсона находит кратчайшие пути между всеми парами вершин взвешенного ориентированного графа. | ||
+ | * Алгоритм Ли (волновой алгоритм) основан на методе поиска в ширину. Находит путь между вершинами s и t графа (s не совпадает с t), содержащий минимальное количество промежуточных вершин (рёбер). Основное применение — трассировки электрических соединений на кристаллах микросхем и на печатных платах. Также используется для поиска кратчайшего расстояния на карте в стратегических играх. | ||
+ | * Поиск кратчайшего пути на основе алгоритма Килдала. | ||
+ | |||
+ | [[https:// | ||
+ | |||
+ | [[https:// | ||
+ | |||
+ | [[https:// | ||
+ | |||
+ | [[https:// | ||
+ | |||
+ | В основном используется при компьютерной трассировке (разводке) печатных плат, соединительных проводников на поверхности микросхем. Другое применение волнового алгоритма — поиск кратчайшего расстояния на карте в компьютерных стратегических играх. | ||
+ | |||
+ | Волновой алгоритм в контексте поиска пути в лабиринте был предложен Э. Ф. Муром. Ли независимо открыл этот же алгоритм при формализации алгоритмов трассировки печатных плат в 1961 году. | ||
+ | |||
+ | [[https:// | ||
+ | |||
+ | === Методы обхода графа === | ||
+ | |||
+ | [[https:// | ||
+ | |||
+ | [[https:// | ||
+ | |||
+ | Поиск в ширину был формально предложен Э. Ф. Муром в контексте поиска пути в лабиринте. Ли независимо открыл тот же алгоритм в контексте разводки проводников на печатных платах. | ||
+ | |||
+ | Поиск в ширину может применяться для решения задач, связанных с теорией графов: | ||
+ | |||
+ | * Волновой алгоритм поиска пути в лабиринте | ||
+ | * Волновая трассировка печатных плат | ||
+ | * Поиск компонент связности в графе | ||
+ | * Поиск кратчайшего пути между двумя узлами невзвешенного графа | ||
+ | * Поиск в пространстве состояний: | ||
+ | * Нахождение кратчайшего цикла в ориентированном невзвешенном графе | ||
+ | * Нахождение всех вершин и рёбер, лежащих на каком-либо кратчайшем пути между двумя вершинами | ||
+ | * Поиск увеличивающего пути в алгоритме Форда-Фалкерсона (алгоритм Эдмондса-Карпа) | ||
+ | |||
+ | [[https:// | ||
+ | |||
+ | Порядок обхода вершин определяется эвристической функцией «расстояние + стоимость» (обычно обозначаемой как f(x)). Эта функция — сумма двух других: | ||
+ | |||
+ | Функция h(x) должна быть допустимой эвристической оценкой, | ||
+ | |||
+ | Этот алгоритм был впервые описан в 1968 году Питером Хартом, | ||
+ | |||
+ | [[https:// | ||
+ | |||
+ | [[https:// | ||
+ | |||
+ | [[http:// | ||
+ | |||
+ | [[http:// | ||
+ | |||
+ | [[https:// | ||
+ | |||
+ | [[https:// | ||
+ | |||
+ | [[http:// | ||
+ | |||
+ | [[http:// | ||
+ | |||
+ | [[https:// | ||
+ | |||
+ | |||
+ | |||
+ | ===== Комбинаторика ===== | ||
+ | |||
+ | [[http:// | ||
+ | |||
+ | [[https:// | ||
+ | |||
+ | |||
+ | ===== Разное ===== | ||
+ | |||
+ | [[https:// | ||
+ | |||
+ | [[https:// | ||
+ | |||
+ | [[https:// | ||
+ | |||
+ | [[https:// | ||
+ | |||
+ | |||
- | [[https:// | ||