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

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

Начнем с внесения изменений в вычислительную модель. Будем считать, что каждая ячейка абстрактной вычислительной машины может содержать только 0 или 1, и целые числа рассматриваются в двоичной системе счисления. В соответствии с этим всякое целое число a ≠ 0, 1 займет ]log |a|[ ячеек машинной памяти (]x[ – наименьшее целое, не меньшее чем x). Рациональное число, не являющееся целым, будем рассматривать в виде несократимой дроби и представлять в машине как упорядоченную пару целых чисел – числитель и знаменатель этой дроби. Время выполнения каждой элементарной операции примем равным сумме длин записей ее операндов в двоичной системе счисления.

Далее будем рассматривать каждую задачу в так называемом распознавательном варианте, когда решение задачи заключается в получении ответа «да» или «нет». Всякий алгоритм решения такой задачи, будучи примененным к соответствующему входу, работает какое-то время и затем, сообщив ответ «да» или «нет», останавливается. Для некоторых задач их «естественные» постановки уже являются распознавательными. Таковы, например, задачи распознавания изоморфизма, гамильтоновости, планарности, эйлеровости графов. Однако чаще (а на практике – как правило) исходная постановка задачи является оптимизационной. В оптимизационной задаче требуется выбрать из множества допустимых решений X такое решение x, вес (или стоимость) которого w(x) минимален. В рассмотренных вами оптимизационных задачах в качестве X фигурировали множества остовов, путей с заданной начальной вершиной или паросочетаний данного графа. Каждой оптимизационной задаче сопоставим ее распознавательный вариант, который выглядит следующим образом. По данным множеству X, весовой функции w и числу k требуется определить, существует ли элемент xÎX такой, что w(x)£k. Очевидно, что имея полиномиальный алгоритм решения оптимизационной задачи, легко получить полиномиальный алгоритм решения соответствующей ей распознавательной задачи. Можно показать. Что при довольно необременительных предположениях относительно функции w верно и обратное. Мы не будем на этом останавливаться, поскольку для дальнейшего нам достаточно только знать, что оптимизационная задача «не проще» соответствующей распознавательной.

Итак, далее рассматриваются только распознавательные задачи. Определим P как класс распознавательных задач, каждая из которых может быть решена некоторым алгоритмом за полиномиальное время. Мы уже знаем, что в этот класс входят задачи о минимальных остовах, кратчайших путях и наибольших паросочетаниях (имеются в виду распознавательные постановки этих задач, как было установлено). В то же время было названо несколько задач, принадлежность которых к классу P не установлена и считается сомнительной.

Теперь сделаем следующее важное наблюдение. Все задачи, с которыми мы сталкивались до сих пор, независимо от того, установлена их принадлежность классу P или нет, обладают одним общим свойством: если вход задачи таков, что имеет место ответ «да», то существует полиномиальный алгоритм, доказывающий этот факт. Поясним сказанное на примере. Пусть задача состоит в выяснении, является ли граф гамильтоновым, и пусть поступающий на вход граф G гамильтонов, т. е. в графе G имеется гамильтонов цикл C. Тогда доказательство гамильтоновости графа G заключалось бы в проверке включения CÍG. Если, например, граф G задан матрицей смежности, то эту проверку можно выполнить с помощью очевидного алгоритма, затратив O(n) операций. Подчеркнем, что речь идет лишь о существовании полиномиального доказательства – чтобы иметь это доказательство в своем распоряжении, надо знать цикл C. Положение иное, если граф G не является гамильтоновым. В этом случае нельзя утверждать даже, что полиномиальное доказательство этого факта существует. Можно, конечно, перебрать все (|G|-1)! простых циклов длины |G| полного графа, проверяя каждый раз, содержится ли цикл в графе G. Однако подобное доказательство требует времени по крайней мере O((|G|-1)!), и, следовательно, не является полиномиальным.

Теперь мы хотим определить еще один класс распознавательных задач, включив в него все задачи, обладающие тем свойством, что если вход задачи имеет ответ «да», то существует полиномиальный алгоритм, проверяющий (доказывающий) этот факт. С этой целью дополним множество обычных операторов, из которых мы составляли алгоритмы, одним особым. Пусть A=A₁, A₂,…, A_m – последовательность, элементами которой служат обычные операторы и один особый, запись которого имеет вид B(l₁, l₂), l₁, l₂Î{1, 2, …, m}. Пусть, далее, Q=q₁, q₂, …, q_p – такой список, что q_i=l₁ либо q_i=l₂ (i=1, p). После того, как A и Q заданы, действие особого оператора B(l₁, l₂) определим так: в результате k-го (k£p) выполнения этого оператора управление передается оператору А_l, если q_k=l₁, и A_l, если q_k=l₂, а при k>p вычисления прекращаются. Итак, последовательности операторов A и списку Q ставится в соответствии обычный (детерминированный) алгоритм. Этот алгоритм будем обозначать через A_Q, чтобы подчеркнуть наличие двух компонент A и Q. Список Q будем при этом называть угадывающей последовательностью, а последовательность A – недетерминированным алгоритмом. Подчеркнем особо, что недетерминированный алгоритм не является алгоритмом, а представляет собой чисто абстрактную конструкцию.

Будем говорить, что недетерминированный алгоритм А решает распознавательную задачу за полиномиальное время, если найдется такой полином р(п), что выполняется следующее условие: каждый вход длины п этой задачи имеет ответ «да» тогда и только тогда, когда для него существует такая угадывающая последовательность Q, что алгоритм A_Q, будучи примененным к этому входу, останавливается, сообщив ответ «да», и время его работы не превосходит р{п). Заметим, что согласно этому определению каждому входу с ответом «да» должен ставиться в соответствие свой алгоритм A_Q. От этого алгоритма не требуется ничего иного, кроме правильной реакции на свой вход. Поведение алгоритма на всех других входах для нас безразлично.

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

Определим теперь NР как класс всех распознавательных задач, недетерминированно разрешимых за полиномиальное время.

Нетрудно видеть, что Р ^Í NР. Действительно, полиномиальный алгоритм решения всякой задачи из Р можно превратить в полиномиальный алгоритм вида A_Q, добавив оператор В (l₁, l₂) так, чтобы он ни разу не срабатывал. При этом в качестве Q можно взять произвольную последовательность, например, состоящую из одного элемента. Класс NР чрезвычайно широк. Например, большинству задач, встречающихся в предыдущих главах, можно «естественным» образом сопоставить распознавательные задачи. При этом окажется, что почти все они принадлежат NР.

В качестве примера доказательства принадлежности задачи к NР рассмотрим задачу об изоморфном подграфе, которую здесь сформулируем в следующем виде.

Даны два графа G₁ и G₂, причем VG₁ = VG₂ = V. Установить, существует ли такая подстановка s: V → V, для которой истинна импликация

(uv Î EG₁) Þ (s(u)s(v)Î EG₂).

Удобно рассматривать эту задачу в матричной постановке. Пусть V={1, 2, ..., п}, А₁ и А₂, – матрицы смежности графов G₁ и G₂ соответственно. Обозначим через S матрацу подстановки s. Теперь задачу об изоморфном подграфе можно сформулировать так: определить, существует ли такая матрица подстановки S, что все единицы матрицы SA₁S^-1 содержатся среди единиц матрицы А₂, т. е. что матрица (А₂—SА₁S^-1) неотрицательна.

Недетерминированный алгоритм A для решения этой задачи выглядит следующим образом.

1. Выполнить пп. 2 – 4 для всех k = и перейти к п. 5.

2. B(3,4).

3. t_k=0.

4.t_k=1.

5. S_ij := t_i₍_n-1)+_j для всех i, j = .

6. А':=SA₁S^-1.

7. Если матрица А₂– А' неотрицательна, то конец и ответ «да». Иначе – конец.

Напомним, что S_ij – элемент матрицы S, занимающий позицию (i, j).

Покажем теперь, как выбирать угадывающую последовательность Q. Рассмотрим произвольный вход задачи, имеющий ответ «да». Это – пара симметрических (0,1)-матриц А₁ и А₂, для которой существует такая матрица подстановки S, что А₂– SA₁S^-1–неотрицательная матрица. Заменим в матрице S 0 на 3 и 1 на 4 и в качестве Q возьмем последовательность элементов этой новой матрицы, выписанных по строкам.

Работа алгоритма A_Q состоит из двух этапов. На первом этапе (пп. 1 – 5) с помощью Q строится матрица подстановки, обеспечивающая изоморфное вложение. Содержанием второго этапа (пп. 6, 7) является проверка того, что матрица S обладает нужным свойством. Полиномиальность алгоритма A_Q очевидна.

Напомним, что частными случаями задачи об изоморфном подграфе являются задачи об изоморфизме графов, о существовании в графе гамильтонова цикла или клики заданного размера и ряд других. Таким образом, попутно установлена принадлежность всех этих задач к классу NР. Доказательство этого свойства для других графовых задач проводится, как правило, столь же просто. При этом работа алгоритма A_Q, так же как и в предыдущем случае, распадается на два этапа: 1) построение некоторого варианта, 2) проверка того, что этот вариант подходящий. Например, в задаче о k-раскраске вершин графа такой алгоритм сначала припишет вершинам графа нужные цвета, а затем проверит, что любые две вершины одного цвета не смежны.

Тот факт, что большинство «естественных» задач входит в класс NР, свидетельствует о чрезвычайной важности вопроса: совпадают ли классы Р и NP? Эта не решенная до сих пор проблема считается важнейшей в науке о вычислениях. Большинство исследователей склоняется к мнению, что Р≠NР. На первый взгляд ситуация Р≠NР не лишает нас возможности получить в будущем полиномиальный алгоритм решения какой-либо из задач, названных нами «трудными». Однако это не так. Как оказалось, из Р≠NР следует, что ни одна из этих «трудных» задач не имеет полиномиального алгоритма, а из существования такого алгоритма для одной из них следует, что Р = NР.

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

Пусть существует полиномиальный алгоритм F, который, будучи примененным ко всякому входу I задачи А, строит некоторый вход F(I) задачи В. Если при этом вход I имеет ответ «да» тогда и только тогда, когда ответ «да» имеет вход F(I), то говорят, что задача А полиномиально сводится к задачеВ, и пишут А µ В. Поскольку сводимостей, отличных от полиномиальной, мы не рассматриваем, то слово «полиномиально» в дальнейшем будем опускать и говорить просто «А сводится к B».

Нетрудно показать, что если задача А сводится к задаче В и В Î P, то и А Î Р. Действительно, пусть A – алгоритм решения задачи В и полиномы р₁(п), р₂(п) таковы, что 0(р₁{п)) и 0(р₂(п))–сложности алгоритмов F и Aсоответственно. Рассмотрим теперь алгоритм A’ решения задачи А, состоящей из двух этапов. На первом этапе вход I задачи А преобразуется алгоритмом F во вход F (I) задачи В. На втором этапе алгоритм Aприменяется ко входу F(I). Согласно определению F, алгоритм Aсообщит ответ «да» тогда и только тогда, когда вход I имеет ответ «да», т. е. алгоритм A' действительно решает задачу А. Выясним теперь его сложность. Если длина I равна n, то F(I) будет построен за время 0(р₁(п)), и его длина – О (p₁ (n)). При этом алгоритм A, будучи примененным ко входу F(I), затратит время 0(p₂(p₁(n))). Таким образом, сложность алгоритма A' есть 0(p₁(n)+р₂(р₁(п)}). Поскольку суперпозиция и сумма полиномов также являются полиномами, то A' — полиномиальный алгоритм.

Точно так же можно показать, что из А µ В и B µ С следует Аµ С.

Задачу А назовем NP-полной, если A Î NP и любая задача из NP сводится к А.

Из этого определения и предыдущих рассмотрении сразу следует, что Р=NP, если хотя бы одна NP-полная задача входит в Р.

Говоря неформально, каждая NP-полная задача «не проще», чем любая задача из NP. Поэтому, доказав NP-полноту некоторой задачи, мы получаем веские основания считать ее трудной. Для доказательства NP-полноты задачи достаточно установить ее принадлежность к NP и показать, что к ней сводится некоторая NP-полная задача. Чтобы воспользоваться этой схемой, надо иметь в распоряжении хотя бы одну NP-полную задачу.

Первой задачей, относительно которой было показано, что она является NP-полной, была задача о выполнимости. Пусть х₁, x₂, х₃, ...— булевы переменные, принимающие значения «истина» или «ложь», и , , ,… –их отрицания. Те и другие в совокупности называются литералами. Пусть символы V и Λ обозначают булевы операции дизъюнкции и конъюнкции соответственно. Формула и₁ V u₂ V ... V u_m называется элементарной дизъюнкцией, если и₁, u₂, ..., u_m – литералы. Пусть С₁, С₂, ... ..., С_p– элементарные дизъюнкции. Тогда выражение вида С₁ Λ С₂Λ ... Λ С_p называется булевым выражением в конъюнктивной нормальной форме. Булево выражение называется выполнимым, если входящим в него переменным можно так присвоить значения «истина» или «ложь», что значением выражения будет «истина». Не все выражения являются выполнимыми. Например, булево выражение

(x₁V x₂) Λ ( V x₃) Λ ( V )

выполнимо, а выражение (x₁Vx₂)Λ( V )Λ(x₁ V )Λ ( \/x₂) не выполнимо. Задача, о выполнимости (ВЫПОЛНИМОСТЬ) состоит в определении, является ли данное булево выражение в конъюнктивной нормальной форме выполнимым.

Следующая теорема, приводимая здесь без доказательства, лежит в основе теории NP-полноты.

Теорема 5.1(С. Кук, 1971 г.). Задача ВЫПОЛНИМОСТЬ является NP-полной.

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

Некоторые NP-полные задачи.

КЛИКА: Даны граф G и натуральное число k. Определить, содержит ли граф G клику мощности k.

НЕЗАВИСИМОСТЬ: Даны граф G и натуральное число k. Определить, содержит ли граф G независимое k-элементное множество вершин.

ИЗОМОРФНЫЙ ПОДГРАФ: Даны два графа G₁ = (V, E₁) и G₂=(V, E₂). Определить, существует ли подстановка s: V→V, для которой истинна импликация (uvÎ E₁)Þ(s(u}s(v)ÎE₂).

ВЕРШИННОЕ ПОКРЫТИЕ: Даны граф G и натуральное число k. Определить, существует ли в графе G вершинное покрытие мощности не более k.

ДОМИНИРУЮЩЕЕ МНОЖЕСТВО: Даны граф G и натуральное число k. Определить, существует ли в графе G доминирующее множество мощности не менее k.

ГАМИЛЬТОНОВ ЦИКЛ: Дан граф G. Определить, содержит ли граф G гамильтонов цикл.

ЯДРО: Дан ориентированный граф G. Определить, содержит ли граф G ядро.

ВЕРШИННАЯ (РЕБЕРНАЯ) РАСКРАСКА: Даны граф G и натуральное число k. Определить, существует ли правильная k-раскраска вершин (ребер) графа G.

Рассмотрим в качестве примера доказательство NP-полноты задачи КЛИКА. Пусть L_k – граф, у которого некоторые k вершин образуют клику, а остальные п–k –изолированные вершины. Ранее мы установили, что задача ИЗОМОРФНЫЙ ПОДГРАФ принадлежит NP. Если в этой задаче положить G₂=G, где G – граф, фигурирующий в формулировке задачи КЛИКА, а в качестве G₁ выбрать граф L_k, то получим задачу КЛИКА. Следовательно, задача КЛИКА принадлежит NP.

Покажем теперь, что ВЫПОЛНИМОСТЬ µ КЛИКА. Пусть B= C₁V C₂ V... V C_m – произвольное булево выражение в конъюнктивной нормальной форме, {u₁, u₂, ..., u_p} – множество входящих в него литералов. Будем обозначать через C’_i множество литералов, входящих в элементарную дизъюнкцию C_i.

Поставим в соответствие выражению В граф G по следующему правилу:

VG={v_ij : u_i Î С'_i},

EG = {v_ij v_kl : u_i ¹ _i , j ¹ i }.

Таким образом, вершины графа G находятся во взаимно однозначном соответствии с вхождениями литералов в элементарные дизъюнкции. Две вершины смежны, если соответствующие вхождения не противоречат друг другу, т. е. элементарные дизъюнкции различны и оба литерала могут одновременно принять значение «истина».

Пусть в графе G имеется клика размера k = т. Этой клике соответствует набор таких т вхождений u_iÎ C’₁, и_iÎС’₂, ..., u_iÎC’_m, что u_i¹ _i. Поэтому после присвоения всем u_i(j= ) значения «истина» выражение В также примет это значение, т. е. В – выполнимое выражение.

Наоборот, предположим, что В – выполнимое выражение. Пусть переменным присвоены значения «истина» или «ложь» так, что выражение В получило значение «истина». Тогда каждая элементарная дизъюнкция C_l должна содержать литерал u_i, имеющий значение «истина». Ясно, что при этом u_i¹ _i.Следовательно, т вершин v₁_i, v₂_i, …, v_miпопарно смежны в графеG, т.е.образуют клику размера т. Таким образом, выражение В выполнимо тогда и только тогда, когда в графе G имеется клика размера k=т. Легко видеть, что построение графа G по выражению В можно выполнить за время O (р(п)), где р(п) – полином, а п – длина записи выражения В (длина входа задачи ВЫПОЛНИМОСТЬ).

Имеется ряд задач, входящих в NP, для решения которых досих пор не найдено полиномиальных алгоритмов и относительно которых неизвестно, являются ли они NP-полными. Наиболее заметной графовой задачей среди них является задача об изоморфизме графов.

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

Теория NP-полноты, помимо теоретического, представляет и чисто практический интерес. Доказав, что задача NP-трудна, разработчик алгоритмов получает достаточные основания, чтобы отказаться от поиска эффективного и точного алгоритма. Дальнейшие его усилия могут быть направлены, например, на получение приближенного решения, либо на получение решения в типичном случае (в большинстве случаев).

Предмет топографии и геодезии. Связь топографии и геодезии с другими науками

Слово «геодезия» образовано из греческих слов «ge» - земля и «dazomai» - разделяю, делю на части; если перевести его дословно, то получится «землеразделение». Это название соответствовало содержанию геодезии во времена ее зарождения и начального развития. Так, в Египте задолго до нашей эры измерялись размеры земельных участков, строились оросительные системы; все это выполнялось с участием геодезистов.

Усложнение и развитие геодезии привело к разделению ее на несколько научных дисциплин.

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

Топография («топос» - место, «графо» - пишу; дословно - описание местности) изучает методы топографической съемки мест ности с целью изображения ее на планах и картах.

Картография изучает методы и процессы создания и использования карт, планов, атласов и другой картографической продукции.

Фотограмметрия (фототопография и аэрофототопо графия) изучает методы создания карт и планов по фото- и аэрофотоснимкам.

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

Маркшейдерия (подземная геодезия) изучает методы проведения геодезических работ в подземных горных выработках.

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

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

Геодезия занимается изучением Земли в содружестве с другими «геонауками», то есть, науками о Земле. Физические свойства Земли в целом изучает наука «физика Земли», строение верхней оболочки нашей планеты изучают геология и геофизика, строение и характеристики океанов и морей - гидрология, океанография. Атмосфера - воздушная оболочка Земли - и процессы, происходящие в ней, являются предметом изучения метеорологии и климатологии. Растительный мир изучает геоботаника, животный мир - зоология. Кроме этого, есть еще география, геоморфология и другие. Среди всех наук о Земле геодезия занимает свое место: она изучает геометрию Земли в целом и отдельных участков ее поверхности, а также геометрию любых объектов (и естественного, и искусственного происхождения) на поверхности Земли и вблизи нее.

Геодезия, как и другие науки, постоянно впитывает в себя достижения математики, физики, астрономии, радиоэлектроники, автоматики и других фундаментальных и прикладных наук. Изобретение лазера привело к появлению лазерных геодезических приборов - лазерных нивелиров и светодальномеров; кодовые измерительные приборы с автоматической фиксацией отсчетов могли появиться только на определенном уровне развития микроэлектроники и автоматики. Что же касается информатики, то ее достижения вызвали в геодезии подлинную революцию, которая происходит сейчас на наших глазах.

<== предыдущая лекция	\|	следующая лекция ==>
РАЗРЕШИМЫЕ И НЕРАЗРЕШИМЫЕ ПРОБЛЕМЫ	\|

Дата добавления: 2015-04-10; просмотров: 1175;