Окулов.Программирование.в.алгоритмах. По вопросам приобретения обращаться
 Скачать 5.46 Mb.
|
|
Пусть это будет массив В Of Boole- an). Элемент B[i,j], равный True, говорит о том, что ребро графа принадлежит каркасу. Общая логика. Begin описания - матрица расстояний; инициализация данных. *} Solve;{*Решение задачи. *} Out;{*Вывод *} End. Процедуры Init и Out очевидны (должны создаваться «на ав- томате»). Уточняем процедуру Solve. Первый «набросок». Procedure Solve; Var не знаем.*} и функции>; Begin переменных процедуры Solve. *} каркаса. *} эйлерова цикла. *} пути *} End; Прежде чем продолжать уточнение, необходимо определить структуры данных этой части логики и взаимодействие ее со- ставных частей. Во-первых, при построении каркаса необходи- мо иметь список ребер, отсортированный в порядке возраста- ния их весов (алгоритмы Краскала и Прима). Следовательно, на входе процедуры FindTree матрица расстояний А, на выхо- де — В, рабочие структуры — массив для хранения списка ре- бер. Внутренние процедуры: формирование списка ребер и сор- 200 4, Алгоритмы на графах Продолжим рассмотрение. Эйлеров цикл необходимо где-то хранить. Пусть это будет массив St Div 2] Of Byte). Количество ненулевых элементов в St — зна- чение переменной Count. Эти величины описываются в разделе переменных процедуры Solve, их инициализация — в процеду- ре InitSolve. Процедуру поиска эйлерова цикла сделаем рекур- сивной, поэтому первый вызов изменится — EilerWay(l). Вы- бор начальной вершины при поиске эйлерова цикла не имеет значения. Итак, классическая логика поиска эйлерова цикла. Приво- дится с целью показа работы процедуры ибо по- следняя не есть поиск гамильтонова цикла в обычной трактов- ке. Procedure (v:Byte); Var j Begin For j :=1 To N Do If B[v,j] Then Begin B[j ,v] : /EilerWay (j) ;End; номер вершины в эйлеров цикл. *} End; Procedure KommWay; Var s:Set Of Begin For To Count повторяющиеся номера вершин из эйлерова цикла. *} If Not In s) Then Begin Inc (i) ; Nay[i] :=St[j] ; s:=s+[St[j]]; End; End; 4.10.3. Алгоритм Кристофидеса Отличается от предыдущего логикой построения маршрута из каркаса минимального веса. Неравенство треугольника вы- полняется. Шаг 1. Строится каркас минимального веса (алгоритм При- ма или 4. Алгоритмы на графах 201 Шаг 2. На множестве вершин каркаса (обозначим их через V), имеющих нечетное число ребер каркаса, находится паросо- четание минимального веса. Таких вершин в любом каркасе четное число. Метод поиска — чередующиеся цепочки. Шаг 3. Каркас преобразуется в эйлеров граф путем присое- динения ребер, соответствующих найденному паросочетанию. Шаг 4. В построенном графе находится эйлеров маршрут. Шаг 5. Эйлеров маршрут преобразуется в маршрут коммиво- яжера: Маршрут Эйлера: 1-7-5-10-6-4-3-1-8-9-2-1 Итак, данный метод отличается от предыдущего только ша- гами 2 и 3. Все этапы реализуются за полиномиальное время. Известно [16], что для этого метода оценка приближенного ме- тода имеет вид и эта оценка является луч- шей для приближенных полиномиальных алгоритмов решения задачи о коммивояжере с неравенством треугольника. На дан- ных из предыдущего параграфа на рисунке показан пример каркаса («жирными» линиями) и паросочетание минимального веса («тонкими» линиями), построенное на вершинах каркаса с нечетными степенями (вершинах 1, 2, 4, 6). Подграф имеет следующую матрицу расстояний. 1 0 0 32 41 2 32 0 0 58 42 4 33 58 0 0 37 6 41 42 37 Путь коммивояжера имеет стоимость CostAp, равную В логику Solve (см. предыдущий алгоритм) добавляется про- цедура построения паросочетания минимального веса (Р). На- зовем ее Pair. Ее входными данными является матрица В (опи- 202 4. Алгоритмы на графах сывает каркас), выходными — новая матрица С (элементы логического типа), соответствующая графу, получаемому до- бавлением к каркасу ребер Р. Procedure Pair; Var не знаем.*} ; и функции, вложенные в Pair>; Begin переменных процедуры, формирование массива с номерами вершин, имеющих нечетную степень. *} {*Поиск первого *} Р. *} Ad; ребер, образующих Р, к каркасу - матрица С.*} End; 4.11. Задачи 1. Дан ориентированный граф с N вершинами (N=<50). Вер- шины и дуги окрашены в цвета с номерами от 1 до М Указаны две вершины, в которых находятся фишки игрока и конечная вершина. Правило перемещения фишек: игрок мо- жет передвигать фишку по дуге, если ее цвет совпадает с цве- том вершины, в которой находится другая фишка; ходы можно делать только в направлении дуг графа; поочередность ходов необязательна. Игра заканчивается, если одна из фишек дости- гает конечной вершины. Написать программу поиска кратчайшего пути до конечной вершины, если он существует. 2. Некоторые школы связаны компьютерной сетью. Между школами заключены соглашения: каждая школа имеет список школ-получателей, которым она рассылает программное обес- печение всякий раз, получив новое бесплатное программное обеспечение (извне сети или из другой школы). При этом, если школа В есть в списке получателей школы А, то школа А мо- жет не быть в списке получателей школы В. Требуется написать программу, определяющую минималь- ное количество школ, которым надо передать по экземпляру нового программного обеспечения, чтобы распространить его по всем школам сети в соответствии с соглашениями. Кроме того, надо обеспечить возможность рассылки нового программного обеспечения из любой школы по всем остальным школам. Для этого можно расширять списки получателей не- которых школ, добавляя в них новые школы. Требуется найти Алгоритмы на графах 203 минимальное суммарное количество расширений списков, при которых программное обеспечение из любой школы достигло бы всех остальных школ. Одно расширение означает добавле- ние одной новой школы-получателя в список получателей од- ной 3. Задан неориентированный граф. При прохождении по не- которым ребрам отдельные (определенные заранее) ребра могут исчезать или появляться. Найти кратчайший путь из вершины с номером q в вершину с номером 4. Заданы два числа N и М где N — количе- ство точек на плоскости. Требуется построить дерево из М то- чек так, чтобы оно было оптимальным. Дерево называется оп- тимальным, если сумма всех его ребер минимальна. Все ребра — это расстояния между вершинами, заданными коорди- натами точек на плоскости. 5. Даны два числа N и М. Построить граф из N вершин и М ребер. Каждой вершине ставится в соответствие число ребер, входящих нее. Граф должен быть таким, чтобы сумма квад- ратов этих чисел была минимальна. 6. Задан ориентированный граф с N вершинами, каждому ребру которого приписан неотрицательный вес. Требуется най- ти простой цикл, для которого среднее геометрическое весов его ребер было бы минимально. Примечание Цикл называется простым, если через каждую вершину он прохо- дит не более одного раза, петли в графе отсутствуют. 7. Компьютерная сеть* состоит из связанных между собой двусторонними каналами связи N компьютеров (N не превосхо- дит 50, а количество каналов N+5), номера которых от 1 до N. Эта сеть предназначена для распространения сообщения от цен- трального компьютера всем остальным. Компьютер, по- лучивший сообщение, вла- деет им и может распро- странять его дальше по сети. Запрещается переда- вать сообщения одному и тому же компьютеру дваж- ды. Время передачи сооб- Задача предложена Антоном Александровичем Сухановым для Всероссий- ской олимпиады школьников в 1993 году. 204 4. Алгоритмы на графах щения по каналу связи занимает одну секунду, при этом пере- дающий и принимающий компьютеры заняты на все время передачи данного сообщения. На рисунке приведен возможный вариант такой сети. В начальный момент времени центральный компьютер мо- жет передать сообщение одному из непосредственно связанных с ним компьютеров, т. е. соседу. После окончания передачи этим сообщением будут владеть оба компьютера. Каждый из них может передать сообщение одному из своих соседей и так далее, пока все компьютеры не будут владеть сообщением. Для сети, показанной на рисунке, возможный порядок распростра- нения сообщения от центрального компьютера с номером 6 имеет вид: Секунда 1: Секунда 2: Секунда 3: Секунда 4: Написать программу определения и вывода порядка переда- чи сообщения за минимальное время. 8. Внутрь квадрата с координатами левого нижнего угла (0,0) и координатами верхнего правого угла (100, 100) помести- ли N (l=<N=<30) квадратиков. Необходимо найти кратчайший путь из точки (0,0) в точку (100,100), который бы не пересекал ни одного из этих квадратиков. Ограничения: • длина стороны каждого квадратика равна 5; • стороны квадратиков параллельны осям координат; • координаты всех углов квадратиков — целочисленные; • квадратики не имеют общих точек. Указание. Строится граф из начальной, конечной точек и вершин квадратиков (ребра не должны пересекать квадраты). Затем ищется кратчайший путь, например, с помощью алго- ритма Дейкстры. 9. Задан неориентированный граф с N вершинами, пронуме- рованными целыми числами от 1 до N. Написать программу, которая последовательно решает следующие задачи: • выясняет количество компонент связности графа; • находит и выдает все такие ребра, что удаление любого из них ведет к увеличению числа компонент связности; • определяет, можно ли ориентировать все ребра графа та- ким образом, чтобы получившийся граф оказался сильно связным; 4. Алгоритмы на графах 205 • ориентирует максимальное количество ребер, чтобы полу- чившийся граф оказался сильно связным; • определяет минимальное количество ребер, которые сле- дует добавить в граф, чтобы ответ на третий пункт был 10. Задан ориентированный граф с N (l Ребенок нарисовал кружки и некоторые из них соединил отрезками. Кружки он пометил целыми числами от 1 до N (l=<N=<30), а на каждом отрезке поставил стрелочку. Затем он приписал каждому кружочку вес в виде некоторого целого чис- ла и определил начальный и конечный кружочки. Из первого он должен выйти, а во второй попасть. Ребенок решил для себя следующее: • набрать максимально возможное суммарное количество очков; • по каждому отрезку пройти ровно один раз; • если в кружок он попадает при движении по направлению стрелки, то к суммарному количеству очков вес этого кружка прибавляется; • если в кружок он попадает при движении против направ- ления стрелки, то из суммарного количества очков вес этого кружка вычитается. Написать программу, которая бы помогла ребенку построить путь, удовлетворяющий всем этим требованиям. 12. Имеется поисковая система, состоящая из броневика и нескольких разведчиков. Эта система была направлена для по- исков сейфа с секретной документацией противника. В лаби- ринте один из посланных разведчиков обнаружил цель поис- ков — сейф. Сам разведчик вывезти сейф не в состоянии, но броневик, с которого были посланы разведчики, может это сде- лать. Разведчик составил план своего пути в виде списка команд U (вверх), D (вниз), L (влево), R (вправо). Путь развед- чика не обязательно является кратчайшим, но он точно безопа- сен (в лабиринте есть мины). Броневик поедет по пути, прохо- дящему по пути разведчика (причем из квадрата А в соседний квадрат В он может ехать только в том случае, если разведчик тоже проходил из в В, а проход разведчика из в не обес- печивает безопасности) так, чтобы истратить как можно мень- ше топлива. Требуется определить, сколько топлива нужно броневику, чтобы доехать до сейфа. 206 4. Алгоритмы на графах Входные данные. В первой строке входного файла записаны целые числа М и T (М — сколь- ко топлива нужно на дви- жение на 1, Т — сколько топлива нужно на поворот на 90°). 1=<М, T=<100. Во второй строке записано це- лое число N В третьей — строка из N символов, задающая дви- жение разведчика, каж- дый символ которой — один из четырех символов U, D, L, R. Выходные данные. Вы- ведите в выходной файл минимальное количество топлива, не- обходимое броневику для того, чтобы доехать до сейфа. Примеры. g.in 2 1 51 DRRRRDRRDDLU 44 g.in 10 1 9 RULDRUDUL 32 Указание. Упростим задачу. Пусть нет стоимостей поворота. Так как путь описывается строкой не более чем из 100 символов, то по нему можно построить ориентиро- ванный граф, в котором будет мак- симум 100 вершин. Стоимость дуг известна, и она постоянна в этом случае. Осталось с помощью извест- ного алгоритма Дейкстры (поиск пути с минимальным весом) найти 4. Алгоритмы на графах 207 решение. Что изменяется при введении стоимости поворота? Рассмотрим пример, приведенный на рисунке. Из точки А до- шли до точки В, затем вернулись в точку и другим путем сно- ва пришли в точку В. Таким образом, из точки А в точку В можно попасть двумя способами. Верхний путь содержит 7 пе- ремещений и 4 поворота, нижний — 9 перемещений и 3 пово- рота. Пусть стоимость перемещения равна 2, а стоимость пово- рота — 3. Тогда верхний путь имеет общую стоимость 26, а нижний — 27. Казалось бы, что следует выбирать верхний путь. Однако, если оценить стоимости перемещений до точки С, то окажется, что верхний путь имеет стоимость 30, а ниж- ний — 28. Из этого следует, что для каждой вершины необхо- димо хранить не одну минимальную стоимость ее достижения, а четыре стоимости — по каждому направлению, строить соот- ветствующий граф и применять алгоритм Дейкстры. В этом за- ключается «изюминка» задачи. 13. «Химическая Произошло радиоактивное зара- жение местности. Составлена карта зараженности. Она пред- ставляет собой прямоугольную таблицу NxM, в клетках которой записана зараженность соответствующего участка. Требуется найти путь из левой верхней клетки таблицы в правую нижнюю клетку с минимальной суммарной дозой радиации. Входные данные. В первой строке входного файла (input.txt) записаны чис- ла N и М, а в следующих N строках — по М чисел — карта зараженности местнос- ти. Числа в строке разделяются одним или несколькими пробелами. l=<N=<30, зараженность участка — целое число от 0 до 100. Выходные данные. В файл записывается одно число — суммарная доза радиации. Указание. В явном виде динамическую схему применить не- льзя, ибо даны не два направления движения, как в классиче- ских задачах о Черепашке, а четыре. Однако если клетки таб- лицы рассматривать как вершины графа с ребрами, означающими возможность перехода из одной клетки в дру- гую, то задача сводится к поиску пути в графе между заданны- ми вершинами с минимальной стоимостью. Так как стоимости положительные, то применим алгоритм Дейкстры. Данная схе- ма в чистом виде неприменима. Например, при описании графа с использованием матрицы смежности потребуется использо- вать двумерный массив 900*900 байт. Оперативной памяти 208 4. Алгоритмы на графах 1 2 3 1 -2 -3 -4 2 -102 -103 -4 3 -7 -7 -7 4 -107 -7 -107 5 -7 -7 -9 явно не хватит. Следует идти другим путем. Доста- точно ограничиться мас- сивом оценок достижения каждой клетки таблицы (Мп). На каждом шаге об- работки находим элемент Мп с минимальной оценкой. Соглас- но алгоритму Дейкстры эта оценка окончательна. Вычисляем стоимости достижения клеток, соседних с найденной, помеча- ем клетку как обработанную (знак минус у значения оценки стоимости достижения данной клетки), и находим следующий элемент из Мп. Для примера из текста формулировки задачи окончательный вид массива Мп. Ответ задачи — значение Abs(Mn[N,M]). 14. Дана доска 8x8. На ней размещены один король и N ко- ней (0 Входные данные. Файл input.txt содержит одну строку символов без пробелов, описыва- ющую начальное расположение фигур на до- ске. Строка содержит последовательность клеток доски, первая из которых — клетка короля, остальные — клетки коней. Каждая клетка описывается парой буква-цифра. Выходные данные. Файл output.txt должен содержать одно число — минимальное количество перемещений, за которое все фигуры можно собрать в одной клетке доски. Указание. Представим доску в виде графа (рисунок). Клетки (вершины) соединены ребром, если из одной в другую можно попасть ходом коня (матрица смежности графа). Расстояние между двумя вершинами — это количество ходов, которые тре- буется сделать коню, чтобы попасть из одной клетки в другую. С помощью стандартного алгоритма находим кратчайшие пути между всеми парами вершин (алгоритм Флойда). Предполо- жим, что пока решается задача только для коней. Для ответа на вопрос задачи необходимо найти клетку, до которой рассто- яние от всех клеток с конями минимально. При известных |