Search     or:     and:
 LINUX 
 Language 
 Kernel 
 Package 
 Book 
 Test 
 OS 
 Forum 
 iakovlev.org 
 Languages
 С
 GNU С Library 
 Qt 
 STL 
 Threads 
 C++ 
 Samples 
 stanford.edu 
 ANSI C
 Libs
 LD
 Socket
 Pusher
 Pipes
 Encryption
 Plugin
 Inter-Process
 Errors
 Deep C Secrets
 C + UNIX
 Linked Lists / Trees
 Asm
 Perl
 Python
 Shell
 Erlang
 Go
 Rust
 Алгоритмы
NEWS
Последние статьи :
  Тренажёр 16.01   
  Эльбрус 05.12   
  Алгоритмы 12.04   
  Rust 07.11   
  Go 25.12   
  EXT4 10.11   
  FS benchmark 15.09   
  Сетунь 23.07   
  Trees 25.06   
  Apache 03.02   
 
TOP 20
 MINIX...3057 
 Solaris...2933 
 LD...2904 
 Linux Kernel 2.6...2470 
 William Gropp...2180 
 Rodriguez 6...2011 
 C++ Templates 3...1945 
 Trees...1937 
 Kamran Husain...1865 
 Secure Programming for Li...1792 
 Максвелл 5...1710 
 DevFS...1693 
 Part 3...1682 
 Stein-MacEachern-> Час...1632 
 Go Web ...1624 
 Ethreal 4...1618 
 Arrays...1606 
 Стивенс 9...1603 
 Максвелл 1...1592 
 FAQ...1538 
 
  01.01.2024 : 3621733 посещений 

iakovlev.org

Алгоритмы - Введение

Алгоритм - это процедура выполнения определенной задачи. Алгоритм является основополагающей идеей любой компьютерной программы. Каждый алгоритм обычно решает какую-то задачу.
Хороший алгоритм должен обладать тремя свойствами:
1. Корректность
2. Эффективность
3. Легкореализуемость.

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

Алгоритмы имеют три формы представления:
1. Обычный язык
2. Псевдокод
3. Язык программирования


Кроме описания алгоритма, нужно описывать задачу. Постановка задачи состоит из двух частей
1. Входные данные
2. Выходные данные


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

Большая часть представляющих интерес алгоритмов использует методы организации данных, применяемых в вычислениях. Созданные таким образом объекты называются структурами данных.
Основная причина изучения алгоритмов состоит в том, что знание этой предметной области позволяет обеспечить огромную экономию ресурсов, вплоть до получения решений задач, которые в противном случае были бы невозможны. В приложениях, в которых обрабатываются миллионы объектов, часто оказывается возможным ускорить работу программы в миллионы раз, используя хорошо разработанный алгоритм.

Комбинаторные обьекты

В реальных приложениях применяются реальные объекты. Большинство алгоритмов спроектировано для работы со строго определенными абстрактными структурами, такими как перестановки, графы или множества. Вам нужно научиться выполнять постановку задачи абстрактным образом, в терминах процедур над фундаментальными структурами.
К комбинаторным обьектам относятся следующие стандартные структуры:
1. Перестановки
2. Подмножества
3. Деревья
4. Графы
5. Точки
6. Многоугольники
7. Строки
Любой из перечисленных обьектов, в свою очередь, может быть рекурсивной структурой данных,

Модель вычислений RAM

Для большинства алгоритмов главным параметром является число n, которое оказывает существенное влияние на время их выполнения. Параметр n может быть степенью полинома, размером файла при сортировке или поиске, количеством символов в строке или некоторой другой абстрактной мерой размера рассматриваемой задачи: чаще всего, он прямо пропорционален величине обрабатываемого набора данных. Когда таких параметров существует более одного , мы часто сводим анализ к одному параметру, задавая его как функцию от других параметров или рассматривая одновременно только один параметр (считая остальные постоянными).

Компьютер с произвольным доступом к памяти (Random Access Machine) называется RAM-машиной. Согласно этой модели наш компьютер работает таким образом:
1. Для исполнения любой простой операции (+, *, -, =, if, call) требуется ровно один временной шаг
2. Циклы и подпрограммы не считаются простыми операциями, а состоят из нескольких простых операций.
3. Каждое обращение к памяти занимает один временной шаг.
Время исполнения алгоритма в RAM-модели вычисляется по общему количеству шагов, требуемых алгоритму для решения данного экземпляра задачи. Довольно трудно создать алгоритм, для которого RAM-модель выдаст существенно неверные результаты. Устойчивость RAM-модели позволяет анализировать алгоритмы машинно-независимым способом.
С помощью RAM-модели можно подсчитать количество шагов, требуемых алгоритму для исполнения любого экземпляра задачи.
Сложность алгоритма в наихудшем случае — это функция, определяемая максимальным количеством шагов, требуемых для обработки любого входного экземпляра размером n.
Сложность алгоритма в наилучшем случае — это функция, определяемая минимальным количеством шагов, требуемых для обработки любого входного экземпляра размером n.
Наиболее важной является оценка сложности алгоритма в наихудшем случае.
На практике работают не с функциями временной сложности, а с их асимтотическими приближениями. Формальные определения, связанные с асимптотическими обозначениями, выглядят таким образом:
1. f(n) = O(g(n)) означает, что функция f(n) ограничена сверху функцией g(n).
2. f(n) = Ω(g(п)) означает, что функция f(n) ограничена снизу функцией g(n).
Можно дать следующую оценку для некоторых констант:
1. Любой алгоритм с факториальным временем исполнения п! становится бесполезным для значений n > 20
2. Диапазон алгоритмов с показательным временем исполнения 2 в степени n несколько шире, но они также становятся непрактичными для значений п > 40
3. Алгоритмы с квадратичным временем исполнения п в квадрате применяются при п < 10 000, после чего их производительность начинает резко ухудшаться.
4. Алгоритмы с линейным и логарифмическим временем исполнения остаются полезными при обработке миллиарда элементов;
5. Алгоритм O(lg(n)) без труда обрабатывает любое вообразимое количество элементов.

Процесс базового анализа алгоритмов обычно порождает лишь небольшое количество классов временных функций, достаточное для покрытия почти всех алгоритмов:
1. Функции-константы, f(n) = 1
2. Логарифмические функции, f(n) = log(п)
3. Линейные функции, f(n) = п
4. Суперлинейные функции, f(n) = n*log(n)
5. Квадратичные функции, f(n) = n2
6. Кубические функции, f(n) = n3
7. Показательные (экспоненциальные) функции, f(n) = cn , константа с> 1.
8. Факториальные функции, f(n) = п!


Используя данные функции, можно оценить некоторые алгоритмы по времени выполнения:
1. Сортировка методом выбора - квадратичная сложность, т.е. если нужно отсортировать массив размером n, то время сортировки в данном случае будет пропорционально квадрату от n
При сортировке этим способом определяется наименьший неотсортированный элемент и помещается в конец отсортированной части массива.
2. Сортировка вставками - квадратичная сложность
3. Сравнение строк - n*m (поиск подстроки длиной m в строке длиной n)
4. Умножение матриц - кубическая сложность
5. Двоичный поиск - логарифмическая сложность
6. Вычисление НОД - квадратичная сложность
7. Открытие цифрового замка - экспоненциальная сложность. В данном случае имеется ввиду сейф, имеющий числовые диски с цифрами от 0 до 9.

Абстрактные типы данных

Процедура - неотъемлемый инструмент программирования, ее можно рассматривать как обобщенное понятие оператора. В отличие от ограниченных по своим возможновозможностям встроенных операторов языка программирования (сложения, умножения и т.п.), с помощью процедур программист может создавать собственные операторы и применять их к операндам различных типов, не только базовым. Примером такой процедуры- оператора может служить стандартная подпрограмма перемножения матриц.

Абстрактный тип данных (АТД) можно опопределить как математическую модель с совокупностью операторов, определенных в рамках этой модели. Простым примером АТД могут служить множества целых чисел с операторами объединения, пересечения и разности множеств. В модели АТД операторы могут иметь операндами не только данные, определенные АТД, но и данные других типов: стандартных типов языка программирования или определенных в других АТД. Результат действия оператора также может иметь тип, отличный от определенных в данной модели АТД.
АТД можно рассматривать как обобщение простых типов данных (целых и действительных чисел и т.д.), точно так же, как процедура является обобщением простых операторов.

Для АТД, реализующий например список, в ней должны быть операторы, выполняющие такие операции, как обнуление списка, выбор элемента списка по индексу, добавление элемента в список и т.д.

В языках пропрограммирования тип данных какой-то переменной обозначает множество значений, которые может принимать эта переменная. Например, переменная булевого (логического) титипа может принимать только два значения: значение true (истина) и значение false (ложь) и никакие другие.
Для представления АТД используются структуры данных, которые представляют собой набор переменных, возможно, различных типов данных, объединенных определенным образом.

Индукция и рекурсия

Имеется ряд натуральных чисел от 1 до n. Вычислить сумму этого ряда. Правильная формула:
S = n(n+1)/2
Доказать это можно следующим образом: сначала берем n=2, подставляем в формулу, проверяем результат, затем берем n=3, подставляем в формулу, проверяем результат, и вуаля: делаем вывод, что для любого сколь угодно большого n форула верна - это и есть математическая индукция, т.е. мы идем от частного к общему.
Программная рекурсия является реализацией математической индукции. Вообще алгоритмы можно разбить на две части:
1. Рекурсивные
2. Инкрементные (поэтапные)
Рекурсивные алгоритмы называются иногда «разделяй и властвуй», и их использование может оказаться очень эффективным.

Жизненный цикл программного обеспечения

Этот процесс начинается с первоначальной идеи, включает в себя написание и отладку программ и продолжается многие годы, в течение которых в исходное программное обеспечение вносятся изменения и улучшения. Мы выносим девять этапов жизненного цикла программного обеспечения. Это означает, что этапы представляют собой части некоторого умозрительного круга, а не простого линейного списка. Хотя все начинается с постановки задачи, обычно переход от одного этапа к другому не бывает последовательным. Например, тестирование программы может предполагать внесение изменений как в постановку задачи, так и сам проект.
1. Постановка задачи. В начале нужно ответить на следующие вопросы:
Каковы входные данные? Какие данные счита ются корректными, а какие — нет? Для кого предназначено программное обеспечение? Какой пользовательский интерфейс следует применить? Какие сообщения об ошибках следует предусмотреть? Какие ограничения накладываются на программу? Существуют ли особые ситуации? В каком виде следует представлять выходные данные? Какая документация должна сопровождать программу? Какие усовершенствования программного обеспечения предусмотрены в будущем?
2. Разработка. Лучше всего упростить процесс решения задачи, разбив большую задачу на несколько маленьких, которыми было бы легче управлять. В результате программа будет состоять из нескольких модулей (modules), представляющих собой самостоятельные единицы кода. Модуль может содержать одну или несколько функций, а также другие блоки кода. Следует стремиться к тому, чтобы модули были как можно более независимыми, или слабо связанными (loosely coupled) друг с другом. Разумеется, это не относится к их интерфейсам (interfaces), представляющим собой механизм их взаимодействия. Умозрительно модули можно считать изолированными друг от друга.
Каждый модуль должен выполнять свою, точно определенную задачу. Следовательно, он должен быть узкоспециализированным (highly cohesive). Таким образом, модульность (modularity) — это свойство программ, состоящих из слабо связанных и узко специализированных модулей.
На этапе проектирования важно точно указывать не только предназначение каждого модуля, но и поток данных (data flow) между модулями. Например, разрабатывая модуль, нужно ответить на следующие вопросы.
Какие данные доступны данному модулю во время его выполнения? В каких условиях можно выполнять данный модуль? Какие действия выполняет модуль и как изменяются данные после завершения его работы?
3. Оценка риска. Некоторые проблемы можно предсказывать и предотвращать.
4. Верификация. Для проверки правильности алгоритмов существуют формальные методы. Диагностическое утверждение (assertion) — это формальное высказывание, описывающее конкретные условия, которые должны выполняться в определенной точке программы. Пред- и постусловия представляют собой пример простых утверждений об условиях, которые должны выполняться в начале и в конце функции. Инвариант (invariant) — это условие, которое всегда должно быть истинным в конкретной точке алгоритма. Инвариант цикла (loop invariant) — это условие, которое должно выполняться до и после каждого выполнения цикла, являющегося частью алгоритма. Инварианты цикла оказываются полезными для создания правильных циклов. Используя инварианты, легче обнаруживать ошибки, следовательно, сокращается время отладки и тестирования программы. Инварианты позволяют сэкономить время.
5. Кодирование. Кодирование заключается в переводе алгоритма на конкретный язык программирования с последующим ис правлением синтаксических ошибок.
6. Тестирование. На этапе тестирования нужно выявить и исправить как можно больше логических ошибок.
7. Уточнение решения. Результатом выполнения этапов 1-6 является работающая программа, которую интенсивно тестировали и отлаживали. Если программа действительно решает поставленную задачу, возникает вопрос: зачем уточнять решение?
Лучше всего решать задачу при наиболее простых предположениях, постепенно услож няя программу. Например, можно предположить, что входные данные имеют определенный формат и являются правильными. Создав простейший вариант, можно дополнять его более сложными процедурами ввода и вывода данных, оснащать дополнительными возможностями и средствами для обнаружения ошибок.
8. Производство, После завершения разработки программного продукта он распространяется среди пользователей, инсталлируется на их компьютерах и применяется.
9. Сопровождение. Поддержка программы не имеет ничего общего с обслуживанием автомобиля. Программное обеспечение не износится, если за ним не ухаживать. Однако пользователи ваших программ могут обнару жить ошибки, оставшиеся незамеченными при тестировании. Кроме того, со временем программное обеспечение нужно совершенствовать, добавляя в него новые функциональные возможности или модифицируя его компоненты. Авторы программ занимаются этим довольно редко, тем важнее становится наличие хорошей документации.

Динамичекое программирование

Динамическое программирование решает задачу путем ее разделения на несколько более простых подзадач, которые решаются в определенном порядке. Она решает каждую из более мелких задач только один раз и сохраняет результаты для последующего использования, чтобы избежать ненужного пересчета. Затем этот метод решает задачи большего размера и объединяет в единое решение результаты решения меньших подзадач. Во многих случаях найденное решение является для поставленной задачи доказуемо оптимальным.

Ученые часто сравнивают последовательности ДНК для определения их сходства. Если вы представите такую последовательность ДНК как строку символов А, С, Т, G, то задачу можно переформулировать как вычисление минимального расстояния редактирования между двумя строками. Иначе говоря, для заданной базовой строки S1, и целевой строки S2 требуется определить наименьшее число операций редактирования, которые преобразуют S1 в S2, если вы можете:
• заменить символ S1 другим символом;
• удалить символ из S1;
• вставить символ в S1

Например, для строки S1, представляющей последовательность ДНК GCTAC, нужны только три операции редактирования данной базовой строки, чтобы преоб­ разовать ее в целевую строку S2, значение которой — СТСА:
• заменить четвертый символ А символом С;
• удалить первый символ G;
• заменить последний символ С символом А
Это не единственная последовательность операций, но вам нужно как минимум три операции редактирования для преобразования в S2. Для начала цель заключается в том, чтобы вычислить значение оптимального ответа, т.е. количество операций редактирования, а уже потом фактическую последовательность операций.

Задача коммивояжера

В качестве примера рассмотрим задачу, которая возникает на производстве.
Нам нужно запрограммировать роботизированный манипулятор, который применяется для припаивания контактов интегральной схемы к контактным площадкам на печатной плате.
Так как роботы являются дорогостоящими устройствами, мы хотим минимизировать время, затрачиваемое манипулятором на обработку платы.
Прежде чем приступать к программированию маршрута манипулятора, нам нужно разработать алгоритм решения этой задачи. На ум может прийти несколько подходящих алгоритмов. Но самым подходящим будет эвристический алгоритм блиэюайшего соседа (nearest-neighbor heuristic). Начиная с какой-либо точки р0, мы идем к ближайшей к ней точке (соседу) р1. От точки р1 мы идем к ее ближайшему еще не посещенному соседу, таким образом исключая точку р0 из числа кандидатов на посещение.

Алгоритм ближайшего соседа достаточно эффективен, т. к. в нем каждая пара точек (pi,pj) рассматривается, самое большее, два раза: первый раз при добавлении в маршрут точки pi , а второй — при добавлении точки pj. При всех этих достоинствах алгоритм имеет всего лишь один недостаток — он совершенно неправильный.

Задачу можно попробовать решить другим способом — соединяя пары самых близких точек, если такое соединение не вызывает никаких проблем, например, досрочного завершения цикла. Каждая вершина рассматривается как самостоятельная одновершинная цепочка. Соединив все вместе, мы получим одну цепочку, содержащую все точки. Соединив две конечные точки, мы получим цикл.
Можно выбрать такую исходную конфигурацию точек, что и второй алгоритм даст плохой, не оптимальный по времени результат.

Но каков же правильный алгоритм решения этой задачи? Можно попробовать перечислить все возможнее перестановки множества точек, а потом выбрать перестановку, сводящую к минимуму длину маршрута. В то же самое время он чрезвычайно медленный. Например, для 20 точек потребуется рассчитать 20! = 2 432 902 008 176 640 000 возможных перестановок. Если учесть, что на плате может оказаться тысяча точек, перебор вообще не работает.

Эффективный алгоритм решения этой задачи называется задачей коммивояжера - traveling salesman problem или TSP
Он относится к эвристическим алгоритмам , которые обычно выдают достаточно хорошие, но не гарантированные результаты.

Задача календарного планирования

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

Первый вариант - нужно брать роль в фильме, который начинается раньше других. Но это не работает в случае, если первый фильм является сериалом.
Второй вариант - брать роли в фильмах с самым коротким периодом сьемок. Но и этот вариант неоптимален.
Третий вариант - перебрать все варианты. Для n фильмов потребуется 2 в степени n перечислений. Например, для n=20 потребуется около милиона вариантов. Но для n=100 вычисление уже превращается в проблему.
Для этой задачи известен оптимальный вариант решения - для этого вам нужно брать роли только в фильмах с самым ранним окончанием съемок, т. е. выбрать такой временной интервал х, у которого правая конечная точка находится левее правых конечных точек всех прочих временных интервалов.

Задача связности

Предположим, что имеется последовательность пар целых чисел, в которой каждое целое число представляет объект некоторого типа, а пара p-q интерпретируется как р связано с q. Мы полагаем, что отношение связано с является транзитивным: если р связано с q, a q связано с г, то р связано с г. Задача состоит в написании программы, исключающей лишние пары из этого множества: когда программа вводит пару p-q, она должна выводить эту пару только в том случае, если из просмотренные на текущий момент множества пар не следует, что р связано с q. Если просмотренных ранее пар следует, что р связано с q, то программа должна игнорировать пару p-q и переходить к вводу следующей пары.

Задача состоит в разработке программы, которая может запомнить достаточный объем информации о просмотренных парах, чтобы решить, связана ли новая пара объектов. Достаточно неформально задачу разработки такого метода мы называем задачей связности (connectivity problem). Такая задача возникает в ряде важных приложений.

Например, целые числа могли бы представлять компьютеры в большой сети, а пары чисел могли бы представлять соединения в сети. Тогда такой программой можно воспользоваться для определения того, нужно ли устанавливать новое прямое соединение между р и q, чтобы они имели возможность обмениваться информацией, или же можно использовать существующие соединения, чтобы установить коммутируемый канал связи между ними.

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

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

Имеет смысл попытаться выявить базовые операции, использованные в алгоритме решения задачи связности и тем самым сделать любой алгоритм решения этой задачи полезным для решения ряда аналогичных задач. В частности, при получении каждой новой пары вначале необходимо определить, представляет ли она новое соединение, затем следует увязать информацию о том, что это соединение было просмотрено, в общую картину связности объектов таким образом, чтобы эта пара учитывалась при проверке последующих соединений в будущем. Мы инкапсулируем эти две задачи в виде абстрактных операций (abstract operation), полагая, что вводимые целочисленные значения представляют элементы в абстрактных множествах, а затем разработаем такие алгоритмы и структуры данных, которые могут:
■ находить множество, содержащее заданный элемент,
■ замещать множества, содержащие два данных элемента, их объединением.

Задача связности легко решается посредством абстрактных операций find (поиск) и union (объединение). После считывания новой пары p-q из ввода мы выполняем операцию find для каждого элемента пары. Если элементы пары находятся в одном наборе, мы переходим к следующей паре; если нет, то выполняем операцию union и записываем эту пару. Множества представляют связные компоненты (connected component): это подмножества объектов, характеризующиеся тем, что любые два объекта в данной компоненте связаны. Этот подход сводит разработку алгоритмического решения задачи связности к задачам определения структуры данных, представляющей эти множества, и к разработке алгоритмов операций union и find, которые эффективно используют эту структуру данных.

Самый простой алгоритм решения этой задачи выглядит следующим образом. Мы берем числовой массив размеро a[10] и инициализируем его от 0 до 10. Затем мы берем два числа - например 3 и 4 - и проверяем, какие числа лежат в ячейках с индексом a[3] и a[4]. Они разные, и мы пишем в ячейку a[3] четверку. На следующем шаге мы проверяем пару 4 и 9. В результате этой проверки мы пишем в ячейки a[3] и a[4] девятки. Схематично это можно нарисовать так:
  р  q    0123456789
  3  4    0124456789
  4  9    0129956789
  8  0    0129956709
  2  3    0199956709
  ...
 
Проверка - операция find - в данном случае становится очень быстрой и заключается в сравнении двух ячеек массива - a[p] и a[q]. В свою очередь, вторая операция - union - требует просмотра всего массива. Общее время работы равно произведению m*n, где n - это размер массива, m - число пар.
При достаточно большом размере массива и числе пар этот алгоритм перестает работать. В этом случае нужно вместо массива использовать деревья.

Задача бинарного поиска

Предположим, вы ищете фамилию человека в телефонной книге. Она начинается с буквы «К». Конечно, можно начать с самого начала и перелистывать страницы, пока вы не доберетесь до буквы «К». Но скорее всего для ускорения поиска лучше раскрыть книгу на середине: ведь буква «К» должна находиться где­то ближе к середине телефонной книги.
Перед нами типичная задача поиска. И во всех этих случаях для решения задачи можно применить один алгоритм: бинарный поиск.

Бинарный поиск - это алгоритм; на входе он получает отсортированный список элементов. Если элемент, который вы ищете, присутствует в списке, то бинарный поиск возвращает ту позицию, в которой он был найден. В противном случае бинарный поиск возвращает null.

В игре "Угадай число" оптимальной стратегией также является алгоритм бинарного поиска. Если например загадывается число в диапазоне от 1 до 100, то мы начинаем отгадывание с 50, затем переходим на следуюшем шаге к делению пополам и выбираем либо 25, либо 75.
В случае линейного поиска нам потребуется время, пропорциональное диапазону загадываемого числа. В случае бинарного поиска нам потребуется меньшее время, которое пропорционально двоичному логарифму от 100.

Бинарный поиск - Python:

Бинарный поиск - Go:

Бинарный поиск - C:

Задача о выпуклой оболочке

В вычислительной геометрии есть такая задача: для данного набора точек двумерной плоскости Р представим резиновую ленту, которая растягивается так, чтобы охватить все точки, и отпускается. Полученная в результате фигура называется выпуклой оболочкой (она представляет собой наименьшую выпуклую фигуру, которая полностью охватывает все точки множества Р). Для выпуклой оболочки Р любой отрезок между любыми двумя точками Р пол­ ностью лежит внутри оболочки.

Простое решение: выберем любые три точки из исходного множества и образуем из них треугольник. Если какие-либо оставшиеся точки содержатся в этом треугольнике, они заведомо не могут быть частью выпуклой оболочки. Алгоритм на псевдокоде - здесь точки p0, p1, p2 образуют треугольник:
 
 slowHull (Р)
     foreach рО in Р do
         foreach pi in {Р-рО} do
             foreach р2 in {Р—pO-pl} do
                 foreach p3 in {P-p0-pl-p2} do
                     if рЗ содержится в Triangle(pO,pi,p2) then
                         Отметить рЗ как внутреннюю точку
 
 
Время выполнения - O(n4). Это самый простой и в то же время неэффективный алгоритм. Есть более эффективные алгоритмы, например, алгоритм Бентли-Фауста, который сначала разбивает множество точек на несколько вертикальных секций, в каждой из которой строится свой промежуточный выпуклый многоугольник. Другой алгоритм построен на основе т.н. диаграммы Вороного, являющейся геометрической структурой, которая делит набор точек на области, каждая из которых оказывается закрепленной за одной из исходных точек входного множества P.



Задача о рюкзаке

Задача. Пусть имеется N предметов, каждый из которых имеет объём Vi и стоимость Ci , предметы неделимы. Имеется рюкзак вместимостью V . Требуется поместить в рюкзак набор предметов максимальной стоимости, суммарный объём которых не превышает объёма рюкзака.

Задача не имеет решения с полиномиальной сложностью. Один из простых в реализации неполиномиальных по сложности алгоритмов заключается в следующем:
1. Перенумеруем все предметы.
2. Установим максимум достигнутой стоимости M в 0.
3. Составим двоичное число с N разрядами, в котором единица в разряде будет означать, что предмет выбран для укладки в рюкзак. Это число однозначно определяет расстановку предметов.
4. Рассмотрим все расстановки, начиная от 000 . . . 000 до 111 . . . 111. Для каждой из них подсчитаем значение суммарного объёма VM .
(a) Если суммарный объём расстановки VM не превосходит объёма рюкзака V , то подсчитывается суммарная стоимость WM и сравнивается с достигнутым ранее максимумом стоимости M .
(b) Если вычисленная суммарная стоимость превосходит максимум M , то максимум M устанавливается в вычисленную стоимость WM и запоминается текущая конфигурация.
Сложность задачи экспоненциальна и равна 2N , так как требуется перебрать все возможные перестановки.
Это — пример задачи, которая имеет решение не полиномиальной сложности (NP).







Оставьте свой комментарий !

Ваше имя:
Комментарий:
Оба поля являются обязательными

 Автор  Комментарий к данной статье