Prolog — База данных — расписание движения самолетов

Прикладное программирование Помощь с решением задач на Prolog Работа с базами данных в Prolog Prolog — База данных — расписание движения самолетов

  • Эта тема пуста.
Просмотр 0 веток ответов
  • Автор
    Сообщения
    • #6498
      @admin

      Задание
      Создать базу данных о заданной предметной области в виде множества фактов языка Пролог (не менее 5 фактов). Информацию о каждом компоненте БД представить в виде структуры.

      Разработать набор предикатов, осуществляющих поиск по запросам. Найденные решения записать в виде фактов внутренней базы данных Пролога. Предусмотреть проверку факта, являющегося ответом на запрос в БД. Если такой факт существует, то выдать его в качестве ответа на запрос. Если такого факта не существует в базе данных, то запустить запрос на выполнение и записать результат в БД.

      Предметная область – расписание движения самолетов. Каждый рейс может быть описан структурой: название авиакомпании, номер рейса, пункт отлета, пункт прилета, время отлета, время прилета, список пунктов промежуточных посадок, список тарифов. Тариф может быть описан структурой: тип класса салона, цена.
      Реализовать следующие типы запросов:

      1. Подсчитать число рейсов, совершающих промежуточную посадку в заданном пункте;
      2. Найти все авиакомпании, у которых есть билеты бизнес класса;
      3. Найти все рейсы, летающие по заданному маршруту.

      1 Описание типов данных и БД

      В разделе domains опишем типы данных в соответствии с предметной областью. Для удобства представления времени добавим тип time, список промежуточных (вынужденных) посадок — опишем как список строк (названий пункта посадки). Тариф опишем как пару — строка (задает тип — премиум, обычный, …) и число — стомость билета.

      domains
        % time(hh, mm)
        d_time = time(integer, integer)
        d_intermediate_stops = string*
        
        % tariff(name, cost)
        d_tariff = tariff(string, integer)
        d_tariffs = d_tariff*
        
        % flight(company_name, number, from, to, from_time, 
                 to_time, intermediate_stops, tariffs)
        flight_d = flight(string, integer, string, string, d_time, 
                          d_time, d_intermediate_stops, d_tariffs)
        
        numbers = integer*
        names = string*

      В строках 8, 15 и 16 описаны типы данных для списков — такие списки возникают в ходе выполнения предикатов (при выполнении задания) и Visual Prolog требует чтобы все такие типы были описаны явно.
      По заданию, в базе данных помимо рейсов нужно хранить результаты выполнения предикатов — наверное с целью «кэширования», для этих результатов также нужно описать формат записи БД:

      database flight_db
        db_flight(flight_d)
        
        % name, count of intermediate
        db_intermediate_in(string, integer)
        
        db_has_tariff(string, names)

      В строке 7 описан тип записи для выполнения пункта 2 задания. Вместо хранения информации о «бизнес классе» можно хранить информацию об авиакомпаниях «имеющих такой тариф» — например, бизнес класс, или обычные билеты.

      Теперь в разделе clauses опишем несколько фактов для нашей базы данных:

      clauses
        db_flight(flight("company 1", 123, "Msk", "Spb", time(12, 00), time(13, 30), [], [tariff("common", 2000), tariff("premium", 3000)])).
        db_flight(flight("company 1", 123, "Spb", "Msk", time(14, 10), time(15, 40), [], [tariff("common", 2000), tariff("premium", 3000)])).
        db_flight(flight("company 1", 33, "Novosibirsk", "Krasnoyarsk", time(12, 10), time(13, 20), [], [tariff("premium", 6000)])).
        db_flight(flight("company 2", 747, "Msk", "Novosibirsk", time(12, 00), time(15, 55), ["Ekaterinburg"], [tariff("common", 12000)])).
        db_flight(flight("company 2", 747, "Novosibirsk", "Msk", time(17, 00), time(21, 30), ["Ekaterinburg"], [tariff("common", 11999)])).
        db_flight(flight("company 3", 56, "Chelyabinsk", "Spb", time(12, 00), time(14, 00), [], [tariff("common", 5500)])).

      Добавим в раздел goal что-то типа hello-world и убедимся что программа компилируется.

      В разделах 2-4 не приводится содержимое раздела prediacates, его можно увидеть в разделе 5.

      2 Подсчет рейсов с промежуточной посадкой в Х

      Наша функция count, очевидно, должна принимать строку (задающую пункт промежуточной посадки) и возвращать количество. Чтобы определить это количество — нужно:

      • проверить нет ли в базе уже вычисленного результата для этого запроса;
      • получить все записи в базе, имеющие такой пункт посадки — с помощью встроенного предиката findall, в результате будет получем список;
      • определить длину найденного списка;
      • записать результат в базу с помощью предиката assert.

      count(In, Count):-
        db_intermediate_in(In, Count), !;
          
        findall(Name,  has_intermediate_in(In, _Company, Name), Names),
        length(Names, Count),
        assert(db_intermediate_in(In, Count)).

      Чтобы этот код заработал нам не хватает двух предикатов — has_intermediate_in, который должен возвращать из базы по очереди все маршруты, имеющие заданный промежуточный пункт посадки (механизм поиска с возвратами) и предиката length, который подсчитает длину нашего списка.

      Предикат has_intermediate_in должен брать очередную запись в базе, выделять из нее список промежуточных посадок и проверять наличие в этом списке заданного пункта:

      has_intermediate_in(In, Company, Number):-
        db_flight(flight(Company, Number, _From, _To, _TimeFrom, _TimeTo, Intermediate, _Tariffs)),
        member(In, Intermediate).

      Видно, что для проверки наличия элемента в списке тут используется предикат member, а для вычисления длины списка — предикат length.

      Теперь можно записать цель — например, найдем количество рейсов, имеющих промежуточную посадку в Екатеринбурге:

      goal
        count("Ekaterinburg", CountEkb).

      Результат:

      CountEkb=2
      1 Solution

      3 Запрос к БД — авиакомпании с бизнес-классом

      Чтобы получить компании с бизнес классом мы, как и в предыдущем пункте должны перебрать все записи в БД и проверить соблюдение условия. Так тарифы заданы списком, то для проверки того, что у компании есть бизнес-класс — вызывается предикат member, описанный выше:

        has_tariff(Tariff, Company):-
          db_flight(flight(Company, _Number, _From, _To, _TimeFrom, _TimeTo, _Intermediate, Tariffs)),
          member(tariff(Tariff, _Cost), Tariffs).

      Если мы вызовем такой предикат, то на экране одна и таже компания будет повторяться столько раз, сколько у них есть рейсов с этим классом. Чтобы убрать из этого списка повторы:

      Функция, приведенная ниже помимо этого пытается найти готовый результат в БД и (если были вычисления) — то записывает результат в БД:

        has_tariff_unique(Tariff, Comanies):-
          db_has_tariff(Tariff, Comanies), !;
              
          findall(Company, has_tariff(Tariff, Company), AllPremium),
          убрать_повторы(AllPremium, [], Comanies),
          
          assert(db_has_tariff(Tariff, Comanies)).

      В качестве цели — найдем все компании имеющие места премиум класса и (отдельно) все компании с обычными местами:

      goal
        has_tariff_unique("premium", Premium),
        has_tariff_unique("common", Common),
        nl,nl,write("\tMsk to Spb:"), nl.

      Результат:

      Premium=["company 1"], Common=["company 3","company 2","company 1"]
      1 Solution

      4 Запрос к БД — рейсы на заданном маршруте

      Для поиска рейсов на заданном маршруте будем последовательно перебирать все рейсы и сравнивать их пункты отправления и прибытия. Сохранять такие рейсы в БД смысла нет, так как эта информация фактически будет дублировать уже существующую базу:

        print_flights_in_route(From, To):-
          db_flight(Flight), Flight = flight(_Company, _Number, From, To, _TimeFrom, _TimeTo, _Intermediate, _Tariffs),
          
          write(Flight),nl.

      С помощью этого предиката запросим рейсы между Москвой и Санкт-Петербургом, а также все рейсы из Москвы (пункт назначения зададим в виде анонимной переменной):

      goal
        nl,nl,write("\tMsk to Spb:"), nl,
        print_flights_in_route("Msk", "Spb"),
        nl,nl,write("\tMsk to Any:"), nl,
        print_flights_in_route("Msk", _Any).

      Результаты:
      	Msk to Spb:
      flight("company 1",123,"Msk","Spb",time(12,0),time(13,30),[],[tariff("common",2000),tariff("premium",3000)])
      
      
      	Msk to Any:
      flight("company 1",123,"Msk","Spb",time(12,0),time(13,30),[],[tariff("common",2000),tariff("premium",3000)])
      _Any=Spb
      flight("company 2",747,"Msk","Novosibirsk",time(12,0),time(15,55),["Ekaterinburg"],[tariff("common",12000)])
      _Any=Novosibirsk
      2 Solutions

      5 Раздел predicates и недостающие предикаты

      predicates
        count(string, integer)
        
        length(numbers, integer)
        nondeterm member(string, d_intermediate_stops)
        nondeterm member(d_tariff, d_tariffs)
        nondeterm member(string, names)
      
        nondeterm has_intermediate_in(string, string, integer)
        
        nondeterm has_tariff(string, string)
        убрать_повторы(names, names, names)
        
        has_tariff_unique(string, names)
        
        nondeterm print_flights_in_route(string, string)

      Предикат убрать_повторы описан тут, а предикаты length и memberтам.

Просмотр 0 веток ответов
  • Для ответа в этой теме необходимо авторизоваться.