мета-данные страницы
  •  
Загрузка не удалась. Возможно, проблемы с правами доступа?

Различия

Показаны различия между двумя версиями страницы.

Ссылка на это сравнение

Предыдущая версия справа и слеваПредыдущая версия
Следующая версия		Предыдущая версия
Следующая версияСледующая версия справа и слева
links_other [12/10/2019 12:05] – [Разное] ocalinks_other [16/11/2019 11:03] – [Разное] oca
Строка 615: Строка 615:
 [[https://habr.com/ru/post/120343/]] Жадные алгоритмы [[https://habr.com/ru/post/120343/]] Жадные алгоритмы
  
-[[https://ru.wikipedia.org/wiki/%D0%96%D0%B0%D0%B4%D0%BD%D1%8B%D0%B9_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC]] Жадные алгоритмы+[[https://ru.wikipedia.org/wiki/%D0%96%D0%B0%D0%B4%D0%BD%D1%8B%D0%B9_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC | Жадный алгоритм 
 +(Материал из Википедии — свободной энциклопедии)]] 
  
-[[https://studfiles.net/preview/3276187/ |Тема № 8. Жадные алгоритмы, теоретические основы, применение.]]+[[https://studfiles.net/preview/3276187/ |Тема № 8. Жадные алгоритмы, теоретические основы, применение.]] (Есть проблемы)
  
  
Строка 623: Строка 624:
  
 [[https://tproger.ru/digest/sorting-algorithms-visualized/]] [[https://tproger.ru/digest/sorting-algorithms-visualized/]]
 +
 +
 +===== Комбинаторика =====
 +
 +=== Ссылки ===
 +
 +
 +===== Графы =====
 +
 +[[https://ru.wikipedia.org/wiki/%D0%9A%D0%B0%D1%82%D0%B5%D0%B3%D0%BE%D1%80%D0%B8%D1%8F:%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B_%D0%BD%D0%B0_%D0%B3%D1%80%D0%B0%D1%84%D0%B0%D1%85| Алгоритмы на графах]]
 +
 +=== Алгоритмы ===
 +
 +Компиляция (скромная форма плагиата) из Википедии.
 +
 +В связи с тем, что существует множество различных постановок данной задачи, есть наиболее популярные алгоритмы для решения задачи поиска кратчайшего пути на графе:
 +
 +  * Алгоритм Дейкстры находит кратчайший путь от одной из вершин графа до всех остальных. Алгоритм работает только для графов без рёбер отрицательного веса.
 +  * Алгоритм Беллмана — Форда находит кратчайшие пути от одной вершины графа до всех остальных во взвешенном графе. Вес рёбер может быть отрицательным.
 +  * Алгоритм поиска A* находит маршрут с наименьшей стоимостью от одной вершины (начальной) к другой (целевой, конечной), используя алгоритм поиска по первому наилучшему совпадению на графе.
 +  * Алгоритм Флойда — Уоршелла находит кратчайшие пути между всеми вершинами **взвешенного ориентированного графа**.
 +  * Алгоритм Джонсона находит кратчайшие пути между всеми парами вершин взвешенного ориентированного графа.
 +  * Алгоритм Ли (волновой алгоритм) основан на методе поиска в ширину. Находит путь между вершинами s и t графа (s не совпадает с t), содержащий минимальное количество промежуточных вершин (рёбер). Основное применение — трассировки электрических соединений на кристаллах микросхем и на печатных платах. Также используется для поиска кратчайшего расстояния на карте в стратегических играх.
 +  * Поиск кратчайшего пути на основе алгоритма Килдала.
 +
 +[[https://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%94%D0%B5%D0%B9%D0%BA%D1%81%D1%82%D1%80%D1%8B|Алгори́тм Де́йкстры (англ. Dijkstra’s algorithm)]] — алгоритм на графах, изобретённый нидерландским учёным Эдсгером Дейкстрой в 1959 году. Находит кратчайшие пути от одной из вершин графа до всех остальных. Алгоритм работает только для графов без рёбер отрицательного веса. Алгоритм широко применяется в программировании и технологиях, например, его используют протоколы маршрутизации OSPF и IS-IS.
 +
 +[[https://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%91%D0%B5%D0%BB%D0%BB%D0%BC%D0%B0%D0%BD%D0%B0_%E2%80%94_%D0%A4%D0%BE%D1%80%D0%B4%D0%B0|Алгоритм Беллмана — Форда]] — алгоритм поиска кратчайшего пути во взвешенном графе. Алгоритм находит кратчайшие пути от одной вершины графа до всех остальных. В отличие от алгоритма Дейкстры, алгоритм Беллмана — Форда допускает рёбра с отрицательным весом. Предложен независимо Ричардом Беллманом и Лестером Фордом.
 +
 +[[https://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9B%D0%B5%D0%B2%D0%B8%D1%82%D0%B0|Алгори́тм Левита (Levit’s algorithm)]] — алгоритм на графах, находит кратчайшее расстояние от одной из вершин графа до всех остальных. Алгоритм также работает для графов с рёбрами отрицательного веса. Алгоритм широко применяется в программировании и технологиях.
 +
 +[[https://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9B%D0%B8|Алгори́тм волново́й трассиро́вки (волновой алгоритм, алгоритм Ли)]] — алгоритм поиска пути, алгоритм поиска кратчайшего пути на планарном графе. Принадлежит к алгоритмам, основанным на методах поиска в ширину.
 +
 +В основном используется при компьютерной трассировке (разводке) печатных плат, соединительных проводников на поверхности микросхем. Другое применение волнового алгоритма — поиск кратчайшего расстояния на карте в компьютерных стратегических играх.
 +
 +Волновой алгоритм в контексте поиска пути в лабиринте был предложен Э. Ф. Муром. Ли независимо открыл этот же алгоритм при формализации алгоритмов трассировки печатных плат в 1961 году.
 +
 +[[https://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%94%D0%B6%D0%BE%D0%BD%D1%81%D0%BE%D0%BD%D0%B0|Алгоритм Джонсона]] — позволяет найти кратчайшие пути между всеми парами вершин взвешенного ориентированного графа. Данный алгоритм работает, если в графе содержатся рёбра с положительным или отрицательным весом, но отсутствуют циклы с отрицательным весом. Назван в честь Д. Б. Джонсона[en], опубликовавшего алгоритм в 1977 году.
 +
 +=== Методы обхода графа ===
 +
 +[[https://ru.wikipedia.org/wiki/%D0%9F%D0%BE%D0%B8%D1%81%D0%BA_%D0%B2_%D0%B3%D0%BB%D1%83%D0%B1%D0%B8%D0%BD%D1%83|Поиск в глубину (англ. Depth-first search, DFS)]] — один из методов обхода графа. Стратегия поиска в глубину, как и следует из названия, состоит в том, чтобы идти «вглубь» графа, насколько это возможно. Алгоритм поиска описывается рекурсивно: перебираем все исходящие из рассматриваемой вершины рёбра. Если ребро ведёт в вершину, которая не была рассмотрена ранее, то запускаем алгоритм от этой нерассмотренной вершины, а после возвращаемся и продолжаем перебирать рёбра. Возврат происходит в том случае, если в рассматриваемой вершине не осталось рёбер, которые ведут в нерассмотренную вершину. Если после завершения алгоритма не все вершины были рассмотрены, то необходимо запустить алгоритм от одной из нерассмотренных вершин[1].
 +
 +[[https://ru.wikipedia.org/wiki/%D0%9F%D0%BE%D0%B8%D1%81%D0%BA_%D0%B2_%D1%88%D0%B8%D1%80%D0%B8%D0%BD%D1%83|Поиск в ширину (англ. breadth-first search, BFS)]]) — метод обхода графа и поиска пути в графе. Поиск в ширину является одним из **неинформированных**(это не ругань, термин) алгоритмов поиска.
 +
 +Поиск в ширину был формально предложен Э. Ф. Муром в контексте поиска пути в лабиринте. Ли независимо открыл тот же алгоритм в контексте разводки проводников на печатных платах.
 +
 +Поиск в ширину может применяться для решения задач, связанных с теорией графов:
 +
 +  * Волновой алгоритм поиска пути в лабиринте
 +  * Волновая трассировка печатных плат
 +  * Поиск компонент связности в графе
 +  * Поиск кратчайшего пути между двумя узлами невзвешенного графа
 +  * Поиск в пространстве состояний: нахождение решения задачи с наименьшим числом ходов, если каждое состояние системы можно представить вершиной графа, а переходы из одного состояния в другое — рёбрами графа
 +  * Нахождение кратчайшего цикла в ориентированном невзвешенном графе
 +  * Нахождение всех вершин и рёбер, лежащих на каком-либо кратчайшем пути между двумя вершинами
 +  * Поиск увеличивающего пути в алгоритме Форда-Фалкерсона (алгоритм Эдмондса-Карпа)
 +
 +[[https://ru.wikipedia.org/wiki/A*|Поиск A* (произносится «А звезда» или «А стар», от англ. A star)]] — в информатике и математике, алгоритм поиска по первому наилучшему совпадению на графе, который находит маршрут с наименьшей стоимостью от одной вершины (начальной) к другой (целевой, конечной).
 +
 +Порядок обхода вершин определяется эвристической функцией «расстояние + стоимость» (обычно обозначаемой как f(x)). Эта функция — сумма двух других: функции стоимости достижения рассматриваемой вершины (x) из начальной (обычно обозначается как g(x) и может быть как эвристической, так и нет), и функции эвристической оценки расстояния от рассматриваемой вершины к конечной (обозначается как h(x)).
 +
 +Функция h(x) должна быть допустимой эвристической оценкой, то есть не должна переоценивать расстояния к целевой вершине. Например, для задачи маршрутизации h(x) может представлять собой расстояние до цели по прямой линии, так как это физически наименьшее возможное расстояние между двумя точками.
 +
 +Этот алгоритм был впервые описан в 1968 году Питером Хартом, Нильсом Нильсоном и Бертрамом Рафаэлем. Это по сути было расширение алгоритма Дейкстры, созданного в 1959 году. Новый алгоритм достигал более высокой производительности (по времени) с помощью эвристики. В их работе он упоминается как «алгоритм A». Но так как он вычисляет лучший маршрут для заданной эвристики, он был назван A*.
 +
 +[[https://neerc.ifmo.ru/wiki/index.php?title=%D0%A2%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%B3%D1%80%D0%B0%D1%84%D0%BE%D0%B2]]
 +
 +[[https://informatics.mccme.ru/course/view.php?id=6]]
 +
 +[[http://www.codenet.ru/progr/other/prbook/]]
 +
 +[[http://study-and-dev.com/blog/sda_theory_graphs/]]
 +
 +[[https://codeforces.com/blog/entry/5558]]
 +
 +[[https://www.yaklass.ru/p/informatika/11-klass/grafy-i-algoritmy-na-grafakh-40408]]
 +
 +[[http://neerc.secna.ru/Algor/algo_base.html]]
 +
 +[[http://e-maxx.ru/algo/]]
 +
 +[[https://tproger.ru/articles/pathfindings/|Алгоритмы поиска пути в графе]]
 +
 +
 +
 +===== Комбинаторика =====
 +
 +[[http://mathematichka.ru/school/combinatorics/combination.html|Формулы комбинаторики.]]
 +
 +[[https://math.ru/lib/363|Комбинаторика. Наум Яковлевич Виленкин]]
  
  
Строка 634: Строка 726:
  
 [[https://help.libreoffice.org/Writer/Instructions_for_Using_Writer/ru]] [[https://help.libreoffice.org/Writer/Instructions_for_Using_Writer/ru]]
 +
 +