Исследовательский потенациал молодых ученых: взгляд в будущее - 2017

«Исследовательский потенциал молодых ученых: взгляд в будущее» 195 2017 В одном из классических вариантов задача о построении мини‐ мального остовного дерева формулируется следующим образом: име‐ ется N городов, в каждом из которых расположена всего одна теле‐ фонная станция; от нее может отходить любое количество проводов, ведущих в другие города. Расстояние между любыми двумя городами считается известным. Требуется соединить города телефонной сетью так, чтобы расходы на провода были бы минимальны. Для решения данной задачи можно использовать алгоритм Прима‐Краскала, основная идея которого заключается в постепенном расширении существующего подграфа за счет добавления минималь‐ ных ребер, которые не будут образовывать циклов. То есть на каждом шаге алгоритма выбирается ребро минимального веса и, если оно не образует цикл с уже встроенными в подграф, то оно включается в со‐ став подграфа. Выбранные таким образом ребра образуют искомое минимальное остовное дерево. Чтобы на каждом шаге выбирать ребро с минимальным весом, достаточно их отсортировать. Расширение подграфа можно организо‐ вать при помощи перебора с возвратом. Перебор с возвратом (backtracking) – метод решения задачи, ис‐ пользующий полный перебор всех возможных вариантов. В контексте решаемой задачи, это означает, что мы будем пытаться добавить в подграф каждое из имеющихся ребер, учитывая их порядок после сортировки. Если на каком‐то шаге ребро будет образовывать цикл, то переходим к следующему по весу и пытаемся добавить его. Добавлен‐ ные ребра следует исключать из рассмотрения, уменьшая с каждым шагом количество рассматриваемых вариантов. Реализация перебора с возвратом в большинстве случаев явля‐ ется довольно непростой задачей – необходимо явным образом опи‐ сать порядок действий, связанный с переходом от одного варианта к другому. Но вместе с тем языки логического программирования (на‐ пример, Planner и Prolog) позволяют достаточно просто организовать перебор с возвратом в силу того, что данный механизм является од‐ ним из главных инструментов языка. Перед описанием реализации рассматриваемого алгоритма на одном из таких языков, определим основную идею и сущность логического программирования. В. М. Зюзьков отмечает, что « логическое программирование яв‐ ляется, пожалуй, наиболее впечатляющим примером применения идей и методов математической логики (точнее, одного из ее разде‐ лов – теории логического вывода) в программировании» [1]. Данный подход базируется на принципах логического вывода информации на основе заданных фактов и правил вывода и автоматическом доказа‐ тельстве теорем. В основе систем логического программирования ле‐