Грокаем а Иллюстрированное пособие для программистов и любопытствующих



Download 3,16 Mb.
bet37/79
Sana19.02.2022
Hajmi3,16 Mb.
#457977
1   ...   33   34   35   36   37   38   39   40   ...   79
Bog'liq
Грокаем алгоритмы ( PDFDrive )

15 СЕНТЯБРЯ



В этой главе
✓ Вы научитесь моделировать сети при помощи новой абстрактной структуры данных — графов.

  • Вы освоите поиск в ширину — алгоритм, который при­меняется к графам для получения ответов на вопросы вида «Какой кратчайший путь ведет к X?»

  • Вы узнаете, чем направленные графы отличаются от ненаправленных.

  • Вы освоите топологическую сортировку — другой алго­ритм сортировки, раскрывающий связи между узлами.

Эта глава посвящена графам. Сначала вы узнаете, что такое граф. Затем я покажу первый алгоритм, работающий с графами. Он называется поиском в ширину (BFS, Breadth-First Search).
Поиск в ширину позволяет найти кратчайшее расстояние между двумя объ­ектами. Однако сам термин «кратчайшее расстояние» может иметь много разных значений! Ь1апример, с помощью поиска в ширину можно:
□ написать программу для игры в шашки, которая вычисляет кратчайший путь к победе;

  • реализовать проверку правописания (минимальное количество измене­ний, преобразующих ошибочно написанное слово в правильное, напри­мер АЛГОРИФМ -> АЛГОРИТМ — одно изменение);

  • найти ближайшего к вам врача.

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

Предположим, вы находитесь в Сан-Франциско и хотите добраться из Твин-Пикс к мосту Золотые Ворота. Вы намереваетесь доехать на автобусе с минимальным количеством пересадок. Возможные варианты;



Какой алгоритм вы бы использовали для поиска пути с наименьшим коли­чеством шагов?


Можно ли сделать это за один шаг? На следующем рисунке выделены все места, в которые можно добраться за один шаг.

Мост на этой схеме не выделен; до него невозможно добраться за один шаг. А можно ли добраться до него за два шага?



И снова мост не выделен, а значит, до него невозможно добраться за два шага. Как насчет трех шагов?



Ага! На этот раз мост Золотые Ворота выделен. Следовательно, чтобы до­браться из Твин-Пикс к мосту по этому маршруту, необходимо сделать три шага.





Есть и другие маршруты, которые приведут вас к мосту, но они длиннее (четыре шага). Алгоритм обнаружил, что кратчайший путь к мосту состоит из трех шагов. Задача такого типа называется задачей поиска кратчайшего пути. Часто требуется найти некий кратчайший путь: путь к дому вашего друга, путь к победе в шахматной партии (за наименьшее количество ходов) и т. д. Алгоритм для решения задачи поиска кратчайшего пути называется поиском в ширину.
Чтобы найти кратчайший путь из Твин-Пикс к мосту Золотые Ворота, нам пришлось выполнить два шага:

  1. Смоделировать задачу в виде графа.

  2. Решить задачу методом поиска в ширину.

В следующем разделе я расскажу, что такое графы. Затем будет рассмотрен более подробно поиск в ширину.
Что такое граф?
Г


раф моделирует набор связей. Пред­ставьте, что вы с друзьями играете в по­кер и хотите смоделировать, кто кому сейчас должен. Например, условие «Алекс должен Раме» можно смодели­ровать так:
А

Download 3,16 Mb.

Do'stlaringiz bilan baham:
1   ...   33   34   35   36   37   38   39   40   ...   79




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish