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




Пример отношений, определяющих конкретную задачу: поиск маршрута


Давайте теперь сформулируем задачу нахождения маршрута как задачу поиска в И / ИЛИ-графе, причем сделаем это таким образом, чтобы наша формулировка могла бы быть непосредственно использована процедурой и_или рис. 13.12. Мы условимся, что карта дорог будет представлена при помощи отношения

        связь( Гор1, Гор2, Р)

означающего, что между городами Гор1 и Гор2

существует непосредственная связь, а соответствующее расстояние равно Р.   Далее, мы допустим, что существует отношение

        клпункт( Гор1-Гор2, Гор3)

имеющее следующий смысл: для того, чтобы найти маршрут из Гор1 в Гор2, следует рассмотреть пути, проходящие через Гор3

( Гор3 - это "ключевой пункт" между Гор1

и Гор2). Например, на карте рис. 13.1  f

  и  g  - это ключевые пункты между  а

  и  z:

        клпункт( a-z, f).                 клпункт( a-z, g).

Мы реализуем следующий принцип построения маршрута:

Для того, чтобы найти маршрут между городами   X  и  Z,  необходимо:

    (1)        если между   X  и  Z  имеются ключевые пункты  Y1,   Y2,  ...,  то найти один из путей:

  • путь из  X  в  Z  через  Y1,  или
  • путь из  X  в  Z  через  Y2,  или

    ...

  •     (2)        если между   X  и  Z  нет ключевых пунктов, то найти такой соседний с  X   город  Y,  что существует маршрут из  Y  в  Z.

    Таким образом, мы имеем два вида задач, которые мы будем представлять как

        (1)        X-Z

                                найти маршрут из  X  в  Z




    Содержание  Назад  Вперед