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

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

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

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

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

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

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


    Скачать 5.46 Mb.
    НазваниеПо вопросам приобретения обращаться
    АнкорОкулов.Программирование.в.алгоритмах.pdf
    Дата26.04.2017
    Размер5.46 Mb.
    Формат файлаpdf
    Имя файлаОкулов.Программирование.в.алгоритмах.pdf
    ТипДокументы
    #5718
    страница15 из 26
    1   ...   11   12   13   14   15   16   17   18   ...   26
    4. Алгоритмы на графах
    209
    кратчайших расстояниях это поиск мини- мального значения по массиву. Количество ходов для короля из клетки (i, j) в
    z) рав- но
    Abs(j-z)).
    Рассмотрим случай, когда конь может
    «подвозить» короля. Пусть клетка (i,j)
    место встречи фигур и sc — оценка количе- ства ходов коней до этой клетки. Необходи- мо найти коня и клетку доски, в которой он подхватит короля, причем вклад в общую оценку ходов при этом должен быть мини- мальным.
    15. Задан ориентированный граф с N вер- шинами, пронумерованными целыми числа- ми от 1 до N. Написать программу, которая подсчитывает количество различных путей между всеми парами вершин графа.
    Входные данные. Входной файл содержит количе- ство вершин графа N
    и список дуг графа, заданных номерами начальной и конечной вершин.
    Выходные данные. Вывести в выходной файл матрицу N*N, элемент (i,j) которой равен числу различных пу- тей, ведущих из вершины i в вершину j или -1, если существует бесконечно много таких путей.
    Пример
    Указание. В алгоритмах на гра- фах есть очень изящный метод опре- деления кратчайших путей между всеми парами вершин — алгоритм
    Флойда. Используем его идею для решения нашей задачи. Пусть в мат- рице F[1..N,1..N] в текущий момент времени хранится количество путей длины г между всеми парами вер- шин, и нам необходимо найти количество путей длины r+1. Что делать? При между вершинами i и k есть какое-то ко- личество путей длины r и если при этом то между вершинами i и j есть пути длины r+1. Просчитывая для всех значений k, мы получаем количество путей между всеми парами вершин длины
    Второе соображение касается циклов в гра- фе, ибо они определяют значение бесконечности (число путей)
    задачи. Очевидно, что если выявлен цикл, то до всех вершин этого цикла существует бесконечно много путей. Выявленный

    210
    4. Алгоритмы на графах
    цикл — это ненулевой элемент на главной диагонали матрицы F
    при какой-либо из N итераций. Почему N? Да очень просто,
    N — это длина максимального цикла в графе.
    16. Дано прямоугольное клетчатое поле M*N клеток. Каж- дая клетка поля покрашена в один из шести цветов, причем верхняя левая и нижняя правая имеют различный цвет. В ре- зультате поле разбивается на некоторое количество одноцвет- ных областей: две клетки одного цвета, имеющие общую сторо- ну, принадлежат одной области.
    Правила игры. За первым игроком закреплена область,
    включающая левую верхнюю клетку, за вторым — правую нижнюю. Игроки ходят по очереди. Делая ход, игрок перекра- шивает свою область по своему выбору:
    • в любой из шести цветов;
    • в любой из шести цветов, за исключением цвета своей об- ласти и цвета области противника.
    В результате хода к области игрока присоединяются все прилегающие к ней области выбранного цвета, если такие име- ются. Если после очередного хода окажется, что области игро- ков соприкасаются, то игра заканчивается.
    Написать программу, которая определяет минимально воз- можное число ходов, по прошествии которых игра может за- вершиться.
    Входные данные. Цвета пронумерованы цифра- ми от 1 до 6. Первая строка входного файла (in-
    put.txt) содержит М и N — размеры поля
    N=<50). Далее следует описание раскраски поля —
    М строк
    N цифр (от 1 до 6) в каждой без пробе- лов. Первая цифра файла соответствует цвету ле- вой верхней клетки игрового поля. Количество од- ноцветных областей не превосходит 50.
    Выходные данные. В выходной файл
    put.txt) необходимо вывести искомое количество ходов для каждого из пунктов.
    Указание. Сведем задачу к некоторой графовой модели. Рассмотрим идею решения на примере, при- веденном в формулировке задачи. Преобразуем ис- ходную матрицу (Г) в матрицу областей (Ob), опреде- лим цвет каждой области (массив С) и подсчитаем их количество
    Для примера будет выглядеть следующим образом. Массив С — (1, 2, 1, 1, 4, 3, 3, 2), k равно 8. А затем по этой матрице построим матрицу смежности графа (G), опре- деляющего связи между областями.

    4. Алгоритмы на графах
    211
    После этих замечаний решение первого пункта задачи сводится к поиску кратчай- шего пути, точнее количества ребер в пути,
    между вершинами 1 и 8. Для этого можно использовать алгоритм Дейкстры или об- ход графа в ширину. Ответ задачи — значе- ние уровня вершины 8 (при обходе в шири- ну) минус единица.
    Чем отличается решение по второму пункту задачи? Нельзя окрашивать область в цвета своей области и области противни- ка. Это приводит к тому, что мы можем остаться в той же вер- шине графа областей. Опишем состояние игры корте- жем где х — номер области первого игрока, у — номер области второго игрока, play
    номер игрока и color — номер цвета, в который игрок окрашивает область. Как выполнить такой просмотр состояний игры? Да опять же традиционным обходом в ширину в пространстве со- стояний. Завершением обхо- да будет или просмотр всей очереди, или достижение од- ного из конечных состоя- ний. Принцип обхода в ши- рину дает минимальное возможное ходов, по прошествии которых игра заверша- ется.
    17. Корпоративная сеть состоит из N компьютеров, некото- рые из них соединены прямыми двусторонними каналами свя- зи. В целях повышения секретности при проектировании сети количество каналов связи было сокращено до минимума с тем условием, чтобы любые два компьютера имели возможность об- мена информацией либо непосредственно, либо через другие компьютеры сети.
    Хакер хочет прослушивать все передаваемые в сети сообще- ния. Для этого он разработал вирус, который, будучи установ- ленным на какой-либо из компьютеров, передает ему всю ин- формацию, проходящую через этот компьютер. Оказалось, что материальные затраты, необходимые для установки вируса на конкретный компьютер, различны. Требуется определить на- бор компьютеров, которые хакер должен заразить вирусом,
    чтобы минимизировать общие материальные затраты.

    212
    4. Алгоритмы на графах
    Входные данные. Первая строка входного фай- ла содержит N — количество компьюте- ров в сети (l= i-й из последующих N
    строк содержатся номера компьютеров, с которы- ми непосредственно связан компьютер с номером
    i. Далее следует N целых чисел из диапазона
    [1,1000] — материальные затраты, связанные с установкой вируса на каждый из компьютеров.
    Выходные данные. В выходной файл
    put.txt) требуется вывести минимально возмож- ные суммарные затраты и список номеров компь- ютеров, которые необходимо инфицировать,
    упорядоченный по возрастанию.
    Указание. В условии задачи в «сверхзавуалированной» фор- ме сказано о том, что связи компьютеров описываются некото- рой древовидной структурой, ибо в противном случае «сокра- щение до минимума» каналов связи невозможно. Итак, мы имеем какое-то дерево (связное), описывающее связи между компьютерами. Это ограничение дает возможность решать за- дачу и для 500 компьютеров. При связях компьютеров, описы- ваемых произвольным связным графом, вероятно, ничего дру- гого, кроме перебора с некоторыми эвристиками, не остается делать. А это уже достаточно безнадежно. Идея решения. Рас- сматриваем вершины дерева по принципу обхода в ширину.
    Мы находимся в вершине с номером и нам требуется оценить
    (с учетом требования задачи — все связи между компьютерами должны быть под контролем):

    — стоимость заражения компьютеров из поддерева,
    при условии, что и компьютер с номером k заражается;

    — то же самое, только компьютер с номером k не за- ражается.
    Так как используется обход в ширину, то оценки В W для всех компьютеров с номерами k
    1
    ...,
    уже получены. В первом слу- чае — при оценке B[k] — компью- теры мы можем как заражать, так и не заражать,
    т. е. необходимо найти
    Во втором случае — не заражаем компьютер k — компьютеры
    ...,
    необходимо заражать, в противном будет нарушено

    4. Алгоритмы на графах
    213
    условие задачи, т. е.
    Ответом на первый задачи будет значение min(B[j],W[j]), где j
    номер вершины, с которой начинается обход в ширину.
    18. Дан ориентированный граф. Вершинам приписаны веса.
    Требуется найти путь между начальной и конечной вершинами
    (они заданы) с максимально возможным суммарным весом.
    Путь должен удовлетворять следующим условиям:
    • по каждой дуге разрешается пройти один раз;
    • если в вершину попадаем по входящей дуге, то к суммар- ному весу вес этой вершины прибавляется;
    • если в вершину попадаем по выходящей дуге, то из суммарного веса вес этой вер- шины вычитается.
    Входные данные. Входной файл (input.txt)
    содержит данные в следующей последователь- ности:
    N
    — количество вершин графа и их веса (1=<N=<30,
    b, е — номера начальной и конечной вер- шин;
    М — количество дуг;

    — номера вершин, соединяемых пер- вой дугой;
    i
    2
    j
    2
    номера вершин, соединяемых вто- рой дугой;
    • ...

    — номера вершин, соеди- няемых дугой с номером
    Выходные данные. В выходной файл (output.txt) требуется вывести максимальный вес пути и путь, на котором он достигается. В случае,
    если решение не существует, выход- ной файл должен содержать единст- венную строку
    solution».
    Указание. Задача на поиск эйле- рова пути в графе между заданными вершинами. Так как требуется най- ти не просто путь, а путь с наилуч- шей оценкой, то перебор вариан- тов, — это, наверное, единственный способ решения задачи. Эйлеров путь между вершинами b и е существует (теорема Эйлера) в связном графе в том и только
    2
    5
    2
    2
    3
    0
    3
    5
    0
    2
    0
    1
    0
    0
    0
    0
    4
    0
    0
    о
    0
    0
    0
    0
    о

    214
    4. Алгоритмы на графах
    том случае, если вершины Ъ и е имеют нечетные степени, а все остальные — четные степени. Следовательно, на стадии предва- рительной обработки требуется выяснить существует ли в принципе путь между заданными вершинами. Для сокращения перебора разумно ввести дополнительную структуру данных, в которой для каждой вершины определена последовательность просмотра остальных вершин графа. Для нашего примера она может иметь следующий вид. Так, из вершины 2 очередность просмотра вершин — 5,
    1, 4. Вероятность того, что при этом на первых шагах перебора получается оценка, близкая к опти- мальной, возрастает, если не рассматривать специально подо- бранные тесты. Кроме того, следует ввести оперативную про- верку связности непросмотренной части графа. Пусть мы идем по ветке перебора 1-4-6, как показано на рисунке. В процессе поиска решения — эйлерова пути — пройденные ребра «выбра- сываются». Перечеркнутые ребра удалены, они пройдены,
    и мы находимся в 6-й вершине.
    Может оказаться, во-первых,
    что появятся изолированные вершины и, во-вторых, что на- рушится связность оставшейся части графа. Например, так,
    как это показано на рисунке.
    Необходимо попасть из 1-й вер- шины в 7-ю. Очевидно, что вер- шины 2, 3, 4 уже никак не попадут в путь, поэтому дальней- ший поиск пути в этом варианте решения не имеет смысла.
    Поиск эвристик, сокращающих перебор, можно продолжить.
    19. «Стены»* . В некоторой стране стены построены таким образом, что каждая стена со- единяет ровно два города, и стены не пересекают друг дру- га. Таким образом, страна раз- делена на отдельные области.
    Чтобы добраться из одной об- ласти в другую, необходимо либо пройти через город, либо пересечь стену. Два любых го- рода А и могут соединяться не более чем одной стеной
    Задача с Международной олимпиады школьников по информатике
    2000 года.

    4. Алгоритмы на графах 215
    (один конец стены в городе А, а другой — в городе В). Более того,
    всегда существует путь из города
    А в город В, проходящий каких-либо стен и через города.
    Существует клуб, члены кото- рого живут в городах. В каждом городе может жить либо один член клуба, либо вообще ни одно- го. Иногда у членов клуба возникает желание встретиться внутри одной из областей, но не в городе. Чтобы попасть в нуж- ную область, каждый член клуба должен пересечь какое-то ко- личество стен, возможно равное нулю. Члены клуба путешест- вуют на велосипедах. Они не хотят въезжать ни в один город из-за интенсивного движения на городских улицах. Они также хотят пересечь минимально возможное количество стен, так как пересекать стену с велосипедом довольно трудно. Исходя из этого, нужно найти такую оптимальную область, чтобы сум- марное количество стен, которые требуется пересечь членам клуба, называемое суммой пересечений, было минимальным из всех возможных.
    Города пронумерованы целыми числами от 1 до N , где N
    количество городов. На первом рисунке (с. 214) пронумерован- ные вершины обозначают города, а линии, соединяющие вер- шины, обозначают стены. Предположим, что членами клуба являются три человека, которые живут в городах с номерами
    3, 6 и 9. Тогда оптимальная область и соответствующие марш- руты движения членов клуба показаны на втором рисунке выше. Сумма пересечений равняется 2, так как членам клуба следует пересечь две стены: человеку из города 9 требуется пе- ресечь стену между городами 2 и 4, человеку из города 6 требу- ется пересечь стену между городами 4 и 7, а человек из города
    3 не пересекает стен вообще.
    Требуется написать программу, которая по заданной информа- ции о городах, областях и местах проживания членов клуба нахо- дит оптимальную область и минимальную сумму пересечений.
    Входные данные. Файл имеет имя walls.in. Первая строка содержит одно целое число: количество областей М,
    Вторая строка содержит одно целое число: количество городов
    N, 3 Третья строка содержит одно целое число: количе- ство членов клуба L,
    L Четвертая строка содержит
    L различных целых чисел в возрастающем порядке: номера го- родов, где живут члены клуба.

    216
    4. Алгоритмы на графах
    Оставшаяся часть файла содержит строк,
    по паре строк для каждой из М областей. Пер- вые две строки из них описывают первую об- ласть, вторые две строки — вторую область, и т. д. В каждой паре первая строка содержит ко- личество городов на границе области; вторая строка содержит номера этих I городов в поряд- ке обхода границы области по часовой стрелке.
    Единственным исключением является послед- няя область — это находящаяся снаружи (внеш- няя) область, окружающая все города и другие области, и для нее порядок следования городов на границе задается против часовой стрелки. По- рядок описания областей во входном файле зада- ет целые номера этим областям. Область, опи- санная первой во входном файле, имеет номер 1,
    описанная второй — номер 2, и т. д. Обратите внимание, что входной файл содержит описание всех областей, образованных городами и стена- ми, включая находящуюся снаружи (внешнюю)
    область.
    Выходные данные. Файл имеет имя
    Первая строка этого файла содержит одно целое число: минимальную сумму пересечений. Вторая строка содержит одно целое число: номер оптима- льной области. Если существует несколько раз- личных решений, вам необходимо выдать лишь
    Указание. В формулиров- ке задачи содержится под- сказка решения. Описание исходного графа, а это явная задача на графовые алгорит- мы, дано (например) не в виде матрицы смежности, а заданием областей. Требует- ся построить граф, вершина- ми которого являются облас- ти, а ребрами — стены между областями. Естественно, что должна быть вершина и для внешней области. Выше изображен граф областей для дан- ных, представленных на рисунках в условии задачи. После формирования графа областей находим кратчайшие расстоя-

    4. Алгоритмы на графах
    217
    ния между всеми парами вершин (алгоритм Флойда). Для каж- дого члена клуба и каждой области определяем минимальное расстояние, за которое он добирается до этой области. Осталось просуммировать эти расстояния по всем членам клуба и вы- брать минимум.
    20. Два графа и
    называются изоморф- ными, если существует взаимно однозначное соответствие такое, что сохраняется отношение смежности между вершинами графа, т. е. тогда и только тогда, когда
    Даны два графа. Определить, изоморфны ли они. На рисунке приведены примеры изоморфных графов.
    Рекомендации. Прямой метод решения, заключающийся в генерации всех возможных перестановок N!, где N — мощ- ность множеств и
    и проверке сохранения отношения смежности для каждого случая работоспособен для небольших значений N
    Несколько сократить перебор позволяет введение массивов для хранения степеней вершин (число ребер,
    инцидентных вершине) и установка соответствия только между вершинами, имеющими одну степень. Для графов, приведен- ных на рисунке и имеющих одно значение степени, это сокра- щение не работает.
    21. Максимально полный подграф графа G называется кли- кой. В клике между каждой парой вершин существует ребро.
    Число клик в графе может рас- ти экспоненциально относите- льно числа вершин. Так, в гра- фах с 3*N
    вершинами вершины разбиты на триады (1, 2, 3), (4, 5, 6), ...
    (3*N-2, 3*N-1, 3*N). Ребер между вершинами любой триа- ды нет. Однако вершины триа- ды связаны ребрами со всеми вершинами, не принадлежащи- ми данной триаде. На предыду-

    218 4. Алгоритмы на графах
    щем рисунке приведен граф Муна-Мозера при N=2, на этом рисунке при iV=3.
    Графы Муна — Мозера имеют клик, каждая из которых содержит N вершин. Перечислить для небольших значений N
    клики в графах Муна-Мозера.
    Примечание
    В общем случае задача о поиске клик в графе G решается достаточ- но сложно. Однако понятие клики противоположно понятию мак- симально независимого множества. Строим дополнение графа G'.
    Находим в G' максимально независимые множества (это мы умеем делать) — они соответствуют кликам исходного графа.
    22. Рассмотрим четыре множества
    3],
    2, 4],
    4],
    3, 4]. Требуется выбрать такие различные че- тыре числа что i = l , 2, 3, 4. Этими числами могут быть они представляют данную систему множеств. Несложно привести пример множеств, для которых данное представление невозможно. Ф. Холлом дока- зана теорема о существовании системы различных представи- телей. Система
    ...,
    имеет систему различных представителей тогда и только тогда, когда для любой подсис- темы выполняется неравенство т.е. количество элементов в объединении любых к
    подмножеств должно быть не менее к.
    Пусть
    [1, 2, ..., N]. Определить, имеет ли систему различных представителей.
    Указание. По M(S) требуется построить двудольный граф.
    Система различных представителей существует тогда и только тогда, когда в двудольном графе есть максимальное паросочета- ние из iV ребер.
    23. Дан массив N*M, в клетках которого произвольным об- разом поставлены числа от 1 до N*M. Горизонтальным ходом называется такая перестановка любого числа элементов масси- ва, при которой каждый элемент остается в той строке, в кото- рой он был. Вертикальным ходом называется такая перестанов- ка любого числа элементов массива, при которой каждый элемент остается в том столбце, в котором он был. Разрешают- ся только горизонтальные и вертикальные ходы*.
    По мнению автора, это — одна из лучших олимпиадных задач Сергея Генна- дьевича Волченкова.

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


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