Многие задачи, которые порой приходится решать в реальной жизни и в программировании, можно представить в виде графа, являющегося множеством состояний с переходами («дугами»), ведущими из одного состояния в другое. Например, планирование маршрута путешествия в действительности является замаскированной задачей поиска на графе — состояния представляют те места, где вы хотите побывать, а дуги представляют транспортные маршруты между ними. Программа, отыскивающая оптимальный маршрут путешествия, решает задачу поиска на графе. По сути, таковыми являются великое множество программ, осуществляющих обход гиперссылок в Веб.
В этом разделе представлены простые программы на языке Python, осуществляющие поиск путей в направленном циклическом графе между начальным и конечным состоянием. Графы являются более общими конструкциями, чем деревья, потому что ссылки смогут указывать на произвольные узлы — даже на уже посещавшиеся (отсюда название цик ли че ский). Кроме того, в Python нет никакой встроенной поддержки этого типа данных. Несмотря на то, что программы поиска на графах могут, в конечном счете, использовать встроенные типы, тем не менее, конкретные процедуры поиска являются достаточно специфическими, чтобы имело смысл создавать собственные реализации.
Граф, используемый для тестирования программ поиска, представленных в этом разделе, изображен на рис. 18.1. Стрелки на концах дуг указывают разрешенные маршруты (например, из A можно попасть в B, E и G). Алгоритмы поиска будут выполнять обход этого графа методом поиска в глубину, не допуская возврата в ту же точку, чтобы избежать зацикливания. Если вообразить, что это карта, на которой узлы представляют города, а дуги представляют дороги, то этот пример может показаться более осмысленным.
 |
|
