Библиотека Рефераты Курсовые Дипломы Поиск
Библиотека Рефераты Курсовые Дипломы Поиск
сделать стартовой добавить в избранное
Кефирный гриб на сайте www.za4et.net.ru

Компьютеры, Программирование Компьютеры, Программирование

Алгоритмы на графах. Кратчайшие расстояния на графах

Чашка "Неваляшка".
Ваши дети во время приёма пищи вечно проливают что-то на ковёр и пол, пачкают руки, а Вы потом тратите уйму времени на выведение пятен с
222 руб
Раздел: Тарелки
Браслет светоотражающий, самофиксирующийся, желтый.
Изготовлены из влагостойкого и грязестойкого материала, сохраняющего свои свойства в любых погодных условиях. Легкость крепления позволяет
66 руб
Раздел: Прочее
Коврик для запекания, силиконовый "Пекарь".
Коврик "Пекарь", сделанный из силикона, поможет Вам готовить вкусную и красивую выпечку. Благодаря материалу коврика, выпечка не
202 руб
Раздел: Коврики силиконовые для выпечки

Министерство образования Республики Беларусь Учреждение образования &quo ;Гомельский государственный университет им. Ф. Скорины&quo ; Математический факультет Кафедра МПУ Алгоритмы на графах. Поиск в глубину Курсовая работа Исполнитель: Студентка группы М-43 Полякова А.Ю. Научный руководитель: Канд. физ-мат. наук, доцент Зверева Т.Е. Гомель 2006 Содержание Введение 1 Поиск в глубину 2 Задача &quo ;Дороги&quo ; 3 Задача &quo ;Перекрестки&quo ; 4 Задача &quo ;Скрудж Мак-Дак&quo ; Заключение Литература Введение Прежде всего, несколько слов о том, как возникает понятие графа из естественных условий задач. Приведем несколько примеров. Пусть мы имеем карту дорог, в которой для каждого города указано расстояние до всех соседних с ним. Здесь два города называются соседними, если существует дорога, соединяющая непосредственно эти два города. Аналогично, можно рассмотреть улицы и перекрестки внутри одного города. Заметим, что могут быть улицы с односторонним движением. Сеть компьютеров, соединенных проводными линиями связи. Набор слов, каждое из которых начинается на определенную букву и заканчивается на эту же или другую букву. Множество костей домино. Каждая кость имеет 2 числа: левую и правую половину кости. Устройство, состоящее из микросхем, соединенных друг с другом наборами проводников. Генеалогические деревья, указывающие родственные отношения между людьми. И, наконец, собственно графы, указывающие отношения между какими либо абстрактными понятиями, например, числами. Итак, неформально, граф можно определить как набор вершин (города, перекрестки, компьютеры, буквы, цифры кости домино, микросхемы, люди) и связей между ними: дороги между городами; улицы между перекрестками; проводные линии связи между компьютерами; слова, начинающиеся на одну букву и закачивающиеся на другую или эту же букву; проводники, соединяющие микросхемы; родственные отношения, например, Алексей - сын Петра. Двунаправленные связи, например, дороги с двусторонним движением, принято называть ребрами графа; а однонаправленные связи, например, дороги с односторонним движением, принято называть дугами графа. Граф, в котором вершины соединяются ребрами, принято называть неориентированным графом, а граф, в котором хотя бы некоторые вершины соединяются дугами, принято называть ориентированным графом. 1. Поиск в глубину Ниже приведен пример неориентированного графа с шестью вершинами. При компьютерной обработке граф может задаваться списком ребер (дуг) для каждой вершины. Например, для графа, приведенного на примере, этот список выглядит так Для хранения этой информации в памяти компьютера можно воспользоваться двумерным массивом G, где - число вершин в графе, M - максимально возможное число ребер (дуг) у одной вершины графа. Для удобства обработки этой информации можно также иметь одномерный массив kG - количества ребер (дуг) вершин графа. Тогда для обработки списка связей текущей вершины U можно написать for i:=1 o kG; e d; Тем самым, мы получаем обработку дуги, связывающей вершины U и V для всех вершин, непосредственно связанных с U. Для обработки ВСЕХ связей всех вершин можно использовать поиск в глубину (DFS - Dep h-Firs Search): for U:=1 o do Color=WHI E he DFS(U); Procedure DFS(U:lo gi ); var j : lo gi ; begi color); e d; Здесь Color = цвет вершины WHI E (константа=1) - белый, если мы еще не посещали эту вершину GRAY (константа=2) - серый, если мы посещали данную вершину DFS(U) - рекурсивная процедура, которая вызывает себя для всех вершин, потомков данной вершины.

То есть, для обеспечения поиска в глубину на заданном графе G, вначале мы устанавливаем всем вершинам цвет WHI E, а затем для всех вершин, которые еще не посещались (Color=WHI E) вызываем рекурсивную процедуру DFS. Таким способом формируются все возможные маршруты в графе. При этом нет ограничений на количество раз использования дуг и заходов в вершины. Если же по условиям задачи потребуется посещать каждую вершину не более одного раза, чтобы формировать маршруты из несовпадающих вершин, то это может быть обеспечено в процедуре DFS условным вызовом: Procedure DFS(U:lo gi ); var j : lo gi ; begi color=WHI E he DFS(G); e d; Если по условиям задачи требуется каждую дугу использовать не более одного раза, то можно ввести расцветку дуг: Color - со значениями FREE или DO E где, как и ранее - число вершин в графе, M - максимально возможное число ребер (дуг) у одной вершины графа. А процедура DFS формирования маршрутов так, что бы каждая дуга использовалась в маршруте не более одного раза, будет выглядеть следующим образом: procedure DFS(v:by e); var j : by e; begi for j:=1 o kG:=DO E; DFS(G:=FREE; e d; e d; Здесь вводятся пометки на дуги Color = FREE, если дуга еще не обработана, и DO E, если она включена в текущий путь. Если в задаче требуется вывести найденный путь, то для его хранения заводится специальный массив SLED , где Q - максимальное количество ребер в пути и вершины текущего пути заносятся в этот массив и удаляются из него в процессе обхода графа: procedure DFS(v:by e); var j : by e; begi for j:=1 o kG); dec(ks); e d; e d; Приведенная теоретическая информация иллюстрируется далее примерами решения конкретных задач. 2 Задача &quo ;Дороги&quo ; Республиканская олимпиада по информатике 1997г Дана система односторонних дорог, определяемая набором пар городов. Каждая такая пара (i,j) указывает, что из города i можно проехать в город j, но это не значит, что можно проехать в обратном направлении. Необходимо определить, можно ли проехать из заданного города А в заданный город В таким образом, чтобы посетить город С и не проезжать ни по какой дороге более одного раза. Входные данные задаются в файле с именем PA H.I следующим образом. В первой строке находится натуральное ( &l ;=50) - количество городов (города нумеруются от 1 до ). Во второй строке находится натуральное M(M&l ;=100) - количество дорог. Далее в каждой строке находится пара номеров городов, которые связывает дорога. В последней (M 3)-й строке находятся номера городов А, В и С. Ответом является последовательность городов, начинающаяся городом А и заканчивающаяся городом В, удовлетворяющая условиям задачи, который должен быть записан в файл PA H.OU в виде последовательности номеров городов по одному номеру в строке. Первая строка файла должна содержать количество городов в последовательности. При отсутствии пути записать в первую строку файла число -1. Кратко идея решения может быть изложена следующим образом: Поиск в глубину. Если встречаем вершину B, устанавливаем соответствующий флаг. Если встречаем вершину C и флаг B установлен - выводим результат и завершаем работу.

После завершения поиска (требуемый маршрут не найден) выводим -1. Изложим решение более подробно. Ввод исходных данных осуществляется следующим образом: read( ,M); for i:=1 o M do begi read(x,y); i c(kG:=FREE; e d; read(A,B,C); Здесь, как и прежде, kG - (для j от 1 до kG) - вершины, с которыми вершина i связана соответствующей дугой Кроме того, введен цвет дуги FREE - свободна (DO E - занята, FREE/DO E - константы) Главная программа фактически включает только следующие операторы: LabC:=0; { Установить метку - вершину C еще не посещали} DFS(A); { Поиск в глубину от вершины A } wri el (-1); { Вывод признака отсутствия требуемого пути} Рекурсивная процедура поиска в глубину от вершины V выглядит следующим образом: procedure DFS(v:by e); var j : by e; begi for j:=1 o kG=B) a d (LabC=1) he begi Ou Res; hal ; e d; if G:=DO E; i c(ks); sled:=FREE; sled=C he LabC:=0; e d; e d; То есть для всех еще необработанных (color=FREE) дуг от текущей вершины выясняем - если она ведет в конечный пункт, а город C уже проходили - вызов процедуры вывода результата и останов. Если текущая дуга ведет в город С, устанавливаем соответствующую метку (LabC=1). Помечаем дугу как обработанную, заносим ее в массив SLED, который содержит текущий обрабатываемый путь, KS - количество элементов в нем. Вызываем процедуру DFS от вершины (G), в которую ведет текущая дуга. Перед выходом из процедуры DFS восстанавливаем состояние, &quo ;исходное&quo ; перед ее вызовом: снимаем отметку обработки с дуги ( color:=FREE), удаляем ее из массива SLED (dec(ks), оператор sled:=0; делать необязательно, но он предоставляет удобства отладки - что бы в масcиве SLED ненулевыми были только реально входящие в путь элементы). И, наконец, процедура вывода результата: procedure Ou Res; begi wri el (ks 2); wri el (A); for i:=1 o ks do wri el (sled); wri el (B); e d; Поскольку по алгоритму построения начальный (A) и конечный (B) города не заносились в массив SLED, то они выводятся отдельно, а количество городов в пути (KS) перед выводом увеличивается на 2. Полный текст программы приводится ниже. program by97d2s3; co s FREE=1; DO E=2; var G,color : array of lo gi ; kG,sled : array of by e; Mi D,is : lo gi ; i,j,x,y,A,B,C, ,M,ks,LabC : by e; Yes : boolea ; procedure Ou Res; begi wri el (ks 2); wri el (A); for i:=1 o ks do wri el (sled); wri el (B); e d; procedure DFS(v:by e); var j : by e; begi for j:=1 o kG=B) a d (LabC=1) he begi Ou Res; hal ; e d; if G:=DO E; i c(ks); sled:=FREE; sled=C he LabC:=0; e d; e d; begi assig (i pu ,'pa h.i '); rese (i pu ); assig (ou pu ,'pa h.ou '); rewri e(ou pu ); read( ,M); for i:=1 o M do begi read(x,y); i c(kG:=FREE; e d; read(A,B,C); LabC:=0; DFS(A); wri el (-1); close(i pu ); close(ou pu ); e d. 3 Задача &quo ;Перекрестки&quo ; (Автор - Котов В.М.) Республиканская олимпиада по информатике 1998г Даны декартовы координаты перекрестков города, которые пронумерованы от 1 до . На каждом перекрестке имеется светофор. Некоторые из перекрестков соединены дорогами с двухсторонним (правосторонним) движением, которые пересекаются только на перекрестках.

ВЕДЕНИЕ РЕЕСТРА АКЦИОНЕРОВ 3.1. Ведение регистрационного журнала Реестра Запись в Регистрационном журнале предшествует внесению любой записи в Реестр. При получении регистратором документов, являющихся основанием для внесения записи в Реестр, вносится запись в Регистрационный журнал, отражающая тип операции с акциями (гр.З) и документ, на основании которого была сделана запись в Реестре (гр. 4), ссылки на раздел Реестра, в который вносится запись (гр.5, 6). Таким образом, Регистрационный журнал и каждый раздел Реестра имеют перекрестные ссылки. 3.2. Информация о дивидендах Раздел "Дивиденды" заполняется на основании документов, перечисленных в приложении 2 к настоящей Инструкции. В карточке выплаты дивидендов заполняются сначала графы 1-9. Графа 10 "Отметка о получении" заполняется после предоставления бухгалтерией сведений о выплаченных дивидендах, составленных на основе платежных ведомостей. 3.3. Особенности заполнения лицевых счетов акционеров Изменения в лицевые счета Реестра вносятся на основании документов, перечисленных в приложении 2 к настоящей Инструкции. "Сведения об акционерах Общества" (журнал 5) и "Картотека акционеров" (журнал 6) заполняются одновременно

1. Алгоритмы сортировки, поиска кратчайшего пути в графе и поиска покрытия, близкого к кратчайшему

2. Поиск кратчайшего пути в лабиринте

3. Поиск кратчайшего пути передвижения слона по шахматному полю

4. Алгоритмы поиска кратчайших покрытий булевых матриц

5. Нормальные Алгоритмы Маркова. Построение алгоритмов из алгоритмов.

6. Иван Грозный: поиск альтернативных путей социально-политического развития Руси
7. Кратчайший путь к сердцу потребителя
8. Нахождение кратчайшего пути

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

10. Алгоритмы на графах. Независимые и доминирующие множества

11. Алгоритм раскраски графа (точный)

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

13. Максимальное ускорение алгоритма поиска

14. Поиск клик в графах

15. Алгоритмы поиска подстроки в строке

16. Оптимизация алгоритмов поиска

Рюкзак для средней школы "Рассвет", 46x34x18 см.
Рюкзак для средней школы. 2 основных отделения, 4 дополнительных кармана. Формоустойчивая спинка. Ремни регулировки объема. Материал:
978 руб
Раздел: Без наполнения
Этажерка для обуви "Комфорт-3".
Выполнена из металлических трубок с антикоррозионным напылением. Пластиковые колпачки на ножках защищают поверхность пола от царапин.
1111 руб
Раздел: Полки напольные, стеллажи
Чайная пара "Loraine" (чашка 180 мл + блюдце).
Чайная пара, выполненная из костяного фарфора, состоит из 1 чашки и 1 блюдца. Изделия оформлены ярким изображением. Изящный дизайн и
328 руб
Раздел: Кружки, чашки, блюдца

17. Разработка алгоритмов контроля и диагностики системы управления ориентацией космического аппарата

18. Алгоритмы экономической (кадастровой) оценки городских земель и территориально-экономического зонирования

19. Министр просвещения граф С. С. Уваров. Самодержавие, Православие, Народность

20. Оптимальное управление вычислениями в распределенных вычислительных системах на основе графа потоков данных

21. Распределенные алгоритмы

22. Принцип программного управления. Микропроцессор. Алгоритм работы процессора
23. Алгоритм Кнута-Морриса-Пратта
24. Постановка лабораторной работы по теории графов

25. Циклические алгоритмы

26. Понятие алгоритма, его свойства. Описание алгоритмов с помощью блок схем на языке Turbo Pascal

27. Разработка системы задач (алгоритмы-программы) по дискретной математике

28. Работа с графами

29. Компьютерный файлово-загрузочный полиморфный стелс-вирус ONEHALF 3544, особенности алгоритма и методы борьбы с ним

30. Понятие об алгоритмах

31. Алгоритм компактного хранения и решения СЛАУ высокого порядка

32. Теория графов и её применение

Пивная кружка "Пиво утром, как известно, не так вредно, как полезно", 500 мл, 14 см.
Состав: керамика, ПМ. Мыть тёплой водой с применением нейтральных моющих средств.
720 руб
Раздел: Кружки
Средство для купания Bubchen, 400 мл.
Мягкое средство для купания младенцев c лекарственными травами стабилизирует кислотно-щелочной баланс кожи и поддерживает ее естественную
413 руб
Раздел: Экстракты, сборы
Папка для труда "Спортивное авто", 325х245 мм.
Размер: 325х245 мм. Материал: ткань.
322 руб
Раздел: Папки для труда

33. Алгоритмы и протоколы маршрутизации

34. Практика перевода числа из одной системы счисления в другую + блок-схема алгоритма определения наименьшего числа

35. Теория графов. Задача коммивояжера

36. Графы. решение практических задач с использованием графов (С++)

37. Расчет линейных цепей методом топологических графов

38. Алгоритмы и методы компоновки, размещения и трассировки радиоэлектронной аппаратуры
39. Алгоритм анализа финансовой устойчивости предприятия
40. Невольник чести (о графе Михаиле Воронцове)

41. Алгоритм Кнута-Морриса-Прата

42. Генетический алгоритм

43. Применение рекурсии в алгоритмах с возвратом. Файловый тип. Ввод/вывод

44. Модель управления конфликтными потоками в классе алгоритмов

45. Методы и алгоритмы построения элементов систем статистического моделирования

46. Сравнительный анализ алгоритмов построения выпуклой оболочки на плоскости

47. Единый алгоритм эволюции вселенной

48. Алгоритмы декомпозиции и перебора L-классов для решения некоторых задач размещения

Швабра отжимная "Хозяюшка Мила", KF-08.
Отжимные швабры с PVA насадками подходят для влажной уборки и мытья полов из любых материалов: ламинат, паркет, линолеум, керамическая
371 руб
Раздел: Швабры и наборы
Коврик придверный, разноцветный (40x60 см).
Коврик придверный. Основа: резина. Размеры: 400x600 мм.
328 руб
Раздел: Коврики придверные
Игра-баланс "Лягушонок".
Это развивающая и увлекательная игра-баланс для детей в возрасте от 3-х лет. Такие игрушки развивают у детей мелкую моторику рук,
345 руб
Раздел: Игры на ловкость

49. Градиентный алгоритм для систем независимости с отрицательными весами

50. Обучение решению математических задач с помощью графов

51. Декларация или алгоритм новой школы

52. Современные алгоритмы антибактериальной терапии сепсиса

53. Алгоритм расчета стоимости оказания медицинской и фармацевтической помощи пациентам с хронической алкогольной интоксикацией

54. Единый алгоритм успешных продаж
55. Алгоритм развития для науки
56. Аллотропные видоизменения углерода: графит и алмаз

57. Алгоритмы инопланетной геометрии

58. Системный подход и алгоритм управления подготовкой студентов к духовно-просветительской деятельности

59. Алгоритмы трассировки

60. Математическое моделирование высокочастотных радиоцепей на основе направленный графов

61. Алгоритм создания сценария рекламного радиоролика

62. Составление алгоритма расчета расхода сырья верхних трикотажных изделий

63. Образ государства как алгоритм политического поведения

64. Типовой алгоритм составления бюджета

Бассейн "Жираф".
Оригинальный надувной бассейн для детей "Веселый Жираф" создан для детей до 3 лет. Высота бортиков всего 13 см, но этого будет
608 руб
Раздел: Батуты, надувные центры
Машинка "Бибикар (Bibicar)", розовая.
Детская машинка «Бибикар» станет идеальным источником не только развлечения, но и развития для любого ребёнка, которому уже исполнилось 3
2650 руб
Раздел: Каталки
Автомобиль со звуковым сигналом "Джип-каталка с ручкой", красный.
Отличная мини-машинка белорусского производства, выполненная по лицензии испанской компании Molto — настоящая находка для энергичных
2126 руб
Раздел: Каталки

65. СППР фінансового аналізу на базі алгоритмів нечіткої логіки

66. Штеффи Граф

67. Альфьери Витторио, граф д’Асти

68. Постановка и разработка алгоритма решения задачи Учёт основных средств

69. Графічний планшет Wacom Graphire

70. Алгоритм и программа
71. Генетический алгоритм глобальной трассировки
72. Генетические алгоритмы

73. Алгоритм определения динамических характеристик гидроупругих систем для управления гидросооружениями

74. Формализация понятия алгоритма

75. AGraph: библиотека классов для работы с помеченными графами

76. Алгоритмы нейрокибернетики

77. Быстрые алгоритмы сортировки

78. Конфигурирования программного обеспечения алгоритма OSPF на маршрутизаторе

79. Разработка алгоритмов и диалоговых программ автоматизированного формирования

80. Эйлеровы и гамильтоновы графы

Каталка "Утёнок" с ручкой.
Каталка имеет звук трещотки. Длина ручки: 50 см.
551 руб
Раздел: На палочке
Переносная люлька-кокон Фея, цвет: красная, арт: ФЕЯ_0005605-2.
Переносная люлька-кокон — это комфортная переноска для малыша. Модель с жестким дном и съемным капюшоном защитит ребенка от холода и
910 руб
Раздел: Переноски
Наклейка "Дерево", 190x180 см.
Интерьерная наклейка обязательно станет украшением вашей квартиры. Придайте яркий и оригинальный вид комнате вашего ребенка с новым
324 руб
Раздел: Интерьерные наклейки

81. Алгоритм сжатия "Unbuffered RLE"

82. Алгоритм сжатия видео: рецепторы как кодировщики

83. Методика и алгоритмы контроля работоспособности и диагностики сейсмометрических каналов

84. Варианты алгоритма возведения в степень: повышение точности и ускорение

85. Алгоритм нисходящего разбора. Нисходящие распознаватели

86. Сравнительные характеристики трёх наиболее эффективных алгоритмов рисования отрезка
87. Циклические алгоритмы
88. Разработка программы, реализующей алгоритм шифрования ГОСТ 28147-89

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

90. Антуан Гамильтон. Мемуары графа де Грамона

91. Граф Л.Н. Толстой: путь к «Войне и миру»

92. Юмор и сатира в поэзии графа А.К. Толстого

93. Генетический алгоритм

94. Методы и алгоритмы построения элементов систем статистического моделирования

95. Математическая логика и теория алгоритмов

96. Применение рекурсии в алгоритмах с возвратом. Файловый тип. Ввод/вывод

Настольная игра "Эволюция".
Разнообразие живых организмов, населяющих нашу планету, поистине поражает. Теория эволюции объясняет это различием способов, которые
1090 руб
Раздел: Карточные игры
Доска магнитная для рисования, со штампиками.
Магнитная доска предназначена для рисования; у доски стирающееся поле для создания рисунков при помощи специального маркера. На
347 руб
Раздел: Магнитные доски
Уничтожь меня! Уникальный блокнот для творческих людей. Смит К.
Перед вами книга-сенсация, проданная миллионными тиражами по всему миру. Поздравляем, теперь и вы сможете приобщиться к разрушительному
336 руб
Раздел: Блокноты оригинальные, шуточные

97. Типовой расчет графов

98. Алгоритм действий по управлению конфликтом

99. Алгоритм разработки и реализации федеральных целевых программ по развитию проблемных регионов России


Поиск Рефератов на сайте za4eti.ru Вы студент, и у Вас нет времени на выполнение письменных работ (рефератов, курсовых и дипломов)? Мы сможем Вам в этом помочь. Возможно, Вам подойдет что-то из ПЕРЕЧНЯ ПРЕДМЕТОВ И ДИСЦИПЛИН, ПО КОТОРЫМ ВЫПОЛНЯЮТСЯ РЕФЕРАТЫ, КУРСОВЫЕ И ДИПЛОМНЫЕ РАБОТЫ. 
Вы можете поискать нужную Вам работу в КОЛЛЕКЦИИ ГОТОВЫХ РЕФЕРАТОВ, КУРСОВЫХ И ДИПЛОМНЫХ РАБОТ, выполненных преподавателями московских ВУЗов за период более чем 10-летней работы. Эти работы Вы можете бесплатно СКАЧАТЬ.