Уроки, алгоритмы, программы, примеры

Вход на сайт

Материалы по разделам

Построения
на плоскости (2D)
Графика
в пространстве (3D)
Вычислительная
геометрия
Физическое
моделирование
Фрактальная
графика

Новые комментарии

Men dating men savoir faire out of, connection, and the beauty of relationships in their own unique way. https://analxxx... In a life that embraces distinctiveness and inclusivity, same-sex relationships keep found their place. Men who ancient men...
Пиривет сайт с работой закладчиком Работа ежедневные выплаты Если у вас небольшой доход или его вообще нет, то стоит обратить внимание на возможность подработки курьером. Это простая и хорошо оплачиваемая работа.
Последнее из блога https://fkmed.r... Оплата и доставка Условия возврата Гарантия качества https://fkmed.r... Медицинская одежда в розницу https://fkmed.r... Красота и свобода выбора https://fkmed.r... Как купить медицинский костюм в сети магазинов
Фамилия автора Вичек -- венг. Vicsek Tamás. Висекк это двойная не правильная транскрипция с венгерского на английски и с английского на русский. Поправьте пожалуйста.
Men dating men experience love, consistency, and the dream of relationships in their own unmatched way. https://voyeurp... In a superb that embraces diversity and inclusivity, same-sex relationships suffer with develop their place. Men who obsolete...

Счетчики и рейтинг

Рейтинг@Mail.ru Яндекс.Метрика

Жадный алгоритм — алгоритм, заключающийся в принятии локально оптимальных решений на каждом этапе, допуская, что конечное решение также окажется оптимальным.

Алгоритм жадной триангуляции заключается в следующем:

  1. Генерируется список всех возможных отрезков, соединяющих пары исходных точек, и сортируется по длине.
  2. Начиная с самого короткого, в триангуляцию последовательно вставляются отрезки из множества отсортированных по длине отрезков. Если отрезок не пересекается с другими ранее вставленными отрезками, то он вставляется, иначе он отбрасывается.

Если все возможные отрезки имеют разную длину, то результат работы этого алгоритма однозначен, иначе он зависит от порядка вставки отрезков одинаковой длины.

Алгоритм корректно работает как для множества точек на плоскости, так и для выпуклых многоугольников.

В случае с невыпуклым многоугольником алгоритм добавит несколько лишних отрезков снаружи.

Трудоемкость работы жадного алгоритма в среднем составляет ~O(N2logN), поэтому на практике он практически не применяется, однако является очень простым для понимания.