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

 

Общепринятой является точка зрения, согласно которой алгоритм считается эффективным, если он имеет полиномиальную сложность. Дело в том, что несмотря на усилия многих специалистов, для решения таких задач, как задачи отыскания в графе наибольшего независимого множества, гамильтонова цикла, 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=A1, A2,…, Am – последовательность, элементами которой служат обычные операторы и один особый, запись которого имеет вид B(l1, l2), l1, l2Î{1, 2, …, m}. Пусть, далее, Q=q1, q2, …, qp – такой список, что qi=l1 либо qi=l2 (i=1, p). После того, как A и Q заданы, действие особого оператора B(l1, l2) определим так: в результате k-го (k£p) выполнения этого оператора управление передается оператору Аl , если qk=l1, и Al , если qk=l2, а при k>p вычисления прекращаются. Итак, последовательности операторов A и списку Q ставится в соответствии обычный (детерминированный) алгоритм. Этот алгоритм будем обозначать через AQ, чтобы подчеркнуть наличие двух компонент A и Q. Список Q будем при этом называть угадывающей последовательностью, а последовательность Aнедетерминированным алгоритмом. Подчеркнем особо, что недетерминированный алгоритм не является алгоритмом, а представляет собой чисто абстрактную конструкцию.

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



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

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

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

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

Даны два графа G1 и G2, причем VG1 = VG2 = V. Установить, существует ли такая подстановка s: VV, для которой истинна импликация

(uv Î EG1) Þ (s(u)s(vEG2).

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

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

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

2. B(3,4).

3. tk=0.

4.tk=1.

5. Sij := ti(n-1)+j для всех i, j = .

6. А':=SA1S-1.

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

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

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

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

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

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

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

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

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

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

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

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

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

Первой задачей, относительно которой было показано, что она является NP-полной, была задача о выполни­мости. Пусть х1, x2, х3, ...— булевы переменные, прини­мающие значения «истина» или «ложь», и , , ,… –их отрицания. Те и другие в совокупности называются литералами. Пусть символы V и Λ обозначают булевы операции дизъюнкции и конъюнкции соответственно. Формула и1 V u2 V ... V um называется элементарной дизъ­юнкцией, если и1, u2, ..., um – литералы. Пусть С1, С2, ... ..., Сp – элементарные дизъюнкции. Тогда выражение вида С1 Λ С2Λ ... Λ Сp называется булевым выраже­нием в конъюнктивной нормальной форме. Булево выра­жение называется выполнимым, если входящим в него переменным можно так присвоить значения «истина» или «ложь», что значением выражения будет «истина». Не все выражения являются выполнимыми. Например, булево выражение

(x1V x2) Λ ( V x3) Λ ( V )

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Покажем теперь, что ВЫПОЛНИМОСТЬ µ КЛИКА. Пусть B= C1 V C2 V... V Cm – произвольное булево вы­ражение в конъюнктивной нормальной форме, {u1, u2, ..., up} – множество входящих в него литералов. Будем обозначать через C’i множество литералов, входящих в элементарную дизъюнкцию Ci.

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

VG={vij : ui Î С'i},

EG = {vij vkl : ui ¹ i , j ¹ i }.

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

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

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

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

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

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

 

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

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

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

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

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

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

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

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

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

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

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

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

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

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


Дата добавления: 2015-04-10; просмотров: 481; ЗАКАЗАТЬ НАПИСАНИЕ РАБОТЫ


Поиск по сайту:

При помощи поиска вы сможете найти нужную вам информацию, введите в поисковое поле ключевые слова и изучайте нужную вам информацию.

Поделитесь с друзьями:

Если вам понравился данный ресурс вы можете рассказать о нем друзьям. Сделать это можно через соц. кнопки выше.
helpiks.org - Хелпикс.Орг - 2014-2019 год. Материал сайта представляется для ознакомительного и учебного использования. | Поддержка
Генерация страницы за: 0.018 сек.