Программирование на языке ПРОЛОГ для искуственного интеллекта

       

Списковое представление множества кандидатов


В нашей первой реализации этой идеи мы будем использовать следующее представление для множества

line();

        решить( Старт, Решение) :-
                вширину( [ [Старт] ], Решение).

        вширину( [ [Верш | Путь] | _ ], [Верш | Путь] ) :-
                цель( Верш).

        вширину( [ [В | Путь] | Пути], Решение ) :-
                bagof( [B1, В | Путь ],
                ( после( В, В1), not  принадлежит( В1, [В | Путь])),
                НовПути),

                        % НовПути - ациклические продолжения пути [В | Путь]
                конк( Пути, НовПути, Пути1),  !,
                вширину( Путь1, Решение);


                вширину( Пути, Решение).

                                % Случай, когда у В нет преемника

line();

Рис. 11. 10.  Реализации поиска в ширину.

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

        [ [СтартВерш] ]

Общие принципы поиска в ширину таковы:

Для того, чтобы выполнить поиск в ширину при заданном множестве путей-кандидатов, нужно:

  • если голова первого пути - это целевая вершина, то взять этот путь в качестве решения, иначе
  • удалить первый путь из множества кандидатов и породить множество всех возможных продолжений этого пути на один шаг; множество продолжений добавить в конец множества кандидатов, а затем выполнить поиск в ширину с полученным новым множеством.
В случае примера рис.11.9 этот процесс будет развиваться следующим образом:

line();         решить( Старт, Решение) :-
                вширь( [ [Старт] | Z ]-Z, Решение).


        вширь( [ [Верш | Путь] | _ ]-_, [Верш | Путь] ) :-
                цель( Верш).


        вширь( [ [В | Путь] | Пути]-Z, Решение ) :-
                bagof( [B1, В | Путь ],
                            ( после( В, В1),
                               not принадлежит( В1, [В | Путь]) ),
                            Нов ),
                конк( Нов, ZZ, Z),  !,
                вширь( Пути-ZZ, Решение);


                Пути \== Z,
            % Множество кандидатов не пусто
                вширь( Пути-Z, Решение).

line(); Рис. 11. 11.  Программа поиска в ширину более эффективная, чем
программа рис.11.10. Усовершенствование основано на разностном
представлении списка путей-кандидатов.

(1)        Начинаем с начального множества кандидатов:

                    [ [а] ]

(2)        Порождаем продолжения пути [а]:

                    [ [b, а], [с, а] ]

            ( Обратите внимание, что пути записаны в обратном порядке.)

(3)        Удаляем первый путь из множества кандидатов и порождаем его продолжения:

                    [ [d, b, a], [e, b, а] ]

            Добавляем список продолжений в конец списка кандидатов:

                    [ [с, а], [d, b, a], [e, b, а] ]

(4)        Удаляем  [с, а],   а затем добавляем все его продолжения в конец множества кандидатов. Получаем:

                    [ [d, b, a], [e, b, а], [f, c, a], [g, c, a] ]

Далее, после того, как пути [d, b, a] и [e, b, а] будут продолжены, измененный список кандидатов примет вид



                    [[f, c, a], [g, c, a], [h, d, b, a], [i, e, b, a], [j, e, b, a]]

В этот момент обнаруживается путь [f, c, a], содержащий целевую вершину f. Этот путь выдается в качестве решения.

Программа, порождающая этот процесс, показана на рис. 11.10. В этой программе все продолжения пути на один шаг генерируются встроенной процедурой bagof. Кроме того, делается проверка, предотвращающая порождение циклических путей. Обратите внимание на то, что в случае, когда путь продолжить невозможно, и цель bagof терпит неудачу, обеспечивается альтернативный запуск процедуры вширину. Процедуры принадлежит и конк реализуют отношения принадлежности списку и конкатенации списков соответственно.

Недостатком этой программы является неэффективность операции конк. Положение можно исправить, применив разностное представление списков (см. гл. 8). Тогда множество путей-кандидатов будет представлено парой списков Пути и Z, записанной в виде

        Пути-Z

При введении этого представления в программу рис. 11.10 ее можно постепенно преобразовать в программу, показанную на рис. 11.11. Оставим это преобразование читателю в качестве упражнения.


Содержание раздела