Главная страница
Навигация по странице:

  • 4.11.

  • Алгоритмы на графах 203

  • 204 4. Алгоритмы на графах

  • 4. Алгоритмы на графах 205

  • 4. Алгоритмы на графах

  • Окулов.Программирование.в.алгоритмах. По вопросам приобретения обращаться


    Скачать 5.46 Mb.
    НазваниеПо вопросам приобретения обращаться
    АнкорОкулов.Программирование.в.алгоритмах.pdf
    Дата26.04.2017
    Размер5.46 Mb.
    Формат файлаpdf
    Имя файлаОкулов.Программирование.в.алгоритмах.pdf
    ТипДокументы
    #5718
    страница14 из 26
    1   ...   10   11   12   13   14   15   16   17   ...   26
    Пусть это будет массив В
    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. Напишите про- грамму, которая подсчитывает количество различных путей между всеми парами вершин графа.
    Ребенок нарисовал кружки и некоторые из них соединил отрезками. Кружки он пометил целыми числами от 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 должен содержать одно число — минимальное количество перемещений, за которое все фигуры можно собрать в одной клетке доски.
    Указание. Представим доску в виде графа (рисунок). Клетки
    (вершины) соединены ребром, если из одной в другую можно попасть ходом коня (матрица смежности графа). Расстояние между двумя вершинами — это количество ходов, которые тре- буется сделать коню, чтобы попасть из одной клетки в другую.
    С помощью стандартного алгоритма находим кратчайшие пути между всеми парами вершин (алгоритм Флойда). Предполо- жим, что пока решается задача только для коней. Для ответа на вопрос задачи необходимо найти клетку, до которой рассто- яние от всех клеток с конями минимально. При известных

    1   ...   10   11   12   13   14   15   16   17   ...   26


    написать администратору сайта