4. Тестовый пример
Введем в качестве начальной и конечной клетки, клетки принадлежащие разным линиям (например, «c1» и «b6»). Введем несколько обязательных клеток, так, чтобы они влияли на построение оптимального маршрута.
Выбор маршрута передвижения в лабиринте с посещением обязательных клеток
Схему лабиринта можно найти в приложении пояснительной записки
Введите название начальной клетки = d1
Введите название конечной клетки = b6
Сколько обязательных клеток Вы хотите ввести: 2
Введите обязательную клетку: g1
Введите последнюю обязательную клетку: e5
Оптимальный маршрут:
d1 – d2 – e2 – f2 – g2 – g1 – h1 – h2 – h3 – h4 – g4 – g5 – f5 – e5 – d5 – d6 – c6 – b6
Количество шагов: 18
yes
5. Текст программы
DOMAINS
/* ОПИСАНИЕ ТИПОВ ДАННЫХ */
список_симв= symbol*
список_цел= integer*
PREDICATES
/* ОПИСАНИЕ ПРЕДИКАТОВ */
nondeterm линия (symbol, список_симв)
nondeterm мин_1 (real, список_цел)
nondeterm мин (real, список_цел)
nondeterm принадлежит (symbol, список_симв)
nondeterm посл (symbol, symbol, список_симв)
nondeterm соседние (symbol, symbol, symbol)
nondeterm переход (symbol, symbol, symbol)
nondeterm маршрут (symbol, symbol, список_симв, integer, symbol, список_симв, список_симв, integer)
nondeterm ввод_обяз (список_симв, integer)
nondeterm ввод_кол_обяз(integer)
nondeterm ввод_назв_обяз (integer, список_симв, список_симв)
nondeterm write_маршрут (список_симв, symbol)
nondeterm run
CLAUSES
/* ОПИИСАНИЕ ЛИНИЙ */
линия (линия_a, [a1, a2, a3, a4]).
линия (линия_a, [a7, a8]).
линия (линия_b, [b3, b4, b5, b6, b7, b8]).
линия (линия_d, [d1, d2, d3, d4, d5, d6]).
линия (линия_e, [e2, e3]).
линия (линия_ee, [e5, e6, e7, e8]).
линия (линия_f, [f5, f6]).
линия (линия_g, [g1, g2, g3, g4, g5, g6, g7, g8]).
линия (линия_h, [h1, h2, h3, h4]).
линия (линия_h, [h6, h7, h8]).
линия (линия_1, [a1, b1, c1, d1]).
линия (линия_11, [g1, h1]).
линия (линия_2, [d2, e2, f2, g2]).
линия (линия_3, [a3, b3, c3, d3, e3]).
линия (линия_33, [g3, h3]).
линия (линия_4, [a4, b4]).
линия (линия_44, [g4, h4]).
линия (линия_5, [d5, e5, f5, g5]).
линия (линия_6, [b6, c6, d6, e6, f6, g6, h6]).
линия (линия_7, [a7, b7]).
линия (линия_77, [g7, h7]).
линия (линия_8, [a8, b8, c8, d8, e8]).
линия (линия_88, [g8, h8]).
/* ПОИСК МИНИМАЛЬНОГО ЭЛЕМЕНТА В СПИСКЕ */
мин_1 (_, []).
мин_1 (Элемент, [X|Хвост]): – Элемент<=X, мин_1 (Элемент, Хвост).
мин (Элемент, [X|Хвост]): – Элемент=X, мин_1 (Элемент, Хвост),!; мин (Элемент, Хвост).
/* ПРОВЕРКА НА ПРИНАДЛЕЖНОСТЬ ЭЛЕМЕНТА СПИСКУ */
принадлежит (Элемент, [Элемент|_]).
принадлежит (Элемент, [_|Хвост]): – принадлежит (Элемент, Хвост).
/* ПРОВЕРКА ДВУХ ЭЛЕМЕНТОВ НА ПОСЛЕДОВАТЕЛЬНОЕ РАСПОЛОЖЕНИЕ В СПИСКЕ */
посл (Элемент1, Элемент2, [Элемент1, Элемент2|_]).
посл (Элемент1, Элемент2, [_|Хвост]): – посл (Элемент1, Элемент2, Хвост).
/* ПРОВЕРКА: ЯВЛЯЮТСЯ ЛИ КЛЕТКИ СОСЕДНИМИ */
соседние (Клетка1, Клетка2, Линия):-
линия (Линия, Список),
принадлежит (Клетка1, Список), принадлежит (Клетка2, Список),
посл (Клетка1, Клетка2, Список);
линия (Линия, Список),
принадлежит (Клетка1, Список), принадлежит (Клетка2, Список),
посл (Клетка2, Клетка1, Список).
/* ПРОВЕРКА КЛЕТКИ НА ВОЗМОЖНОСТЬ СОВЕРШЕНИЯ ПЕРЕСАДКИ */
переход (Клетка, Линия1, Линия2): – линия (Линия1, Список1), линия (Линия2, Список2),
принадлежит (Клетка, Список1), принадлежит (Клетка, Список2),
Линия1<>Линия2.
/* ПОИСК МАРШРУТА */
маршрут (Клетка, Клетка, [Клетка], 1, Линия,_, Обязательные, КолОбяз): – линия (Линия, Список), принадлежит (Клетка, Список), КолОбяз=0.
% нахождение следующей клетки в маршруте без перехода
маршрут (КлНачал, КлКонеч, [КлНачал, КлНачал2|Хвост], ВесМаршрута1, Линия, Недоступные, Обязательные, КолОбяз1):-
соседние (КлНачал, КлНачал2, Линия),
not (принадлежит (КлНачал2, Недоступные)),
маршрут (КлНачал2, КлКонеч, [КлНачал2|Хвост], ВесМаршрута2, Линия, [КлНачал2|Недоступные], Обязательные, КолОбяз1),
ВесМаршрута1 = ВесМаршрута2 + 1;
соседние (КлНачал, КлНачал2, Линия),
not (принадлежит (КлНачал2, Недоступные)),
принадлежит (КлНачал2, Обязательные),
КолОбяз2 = КолОбяз1 – 1,
маршрут (КлНачал2, КлКонеч, [КлНачал2|Хвост], ВесМаршрута2, Линия, [КлНачал2|Недоступные], Обязательные, КолОбяз2),
ВесМаршрута1 = ВесМаршрута2 + 1.
% нахождение следующей клетке в маршруте с переходом
маршрут (КлНачал, КлКонеч, [КлНачал, КлНачал2|Хвост], ВесМаршрута1, Линия, Недоступные, Обязательные, КолОбяз1):-
переход (КлНачал, Линия, Новая_Линия),
соседние (КлНачал, КлНачал2, Новая_Линия),
not (принадлежит (КлНачал2, Недоступные)),
маршрут (КлНачал2, КлКонеч, [КлНачал2|Хвост], ВесМаршрута2, Новая_Линия, [КлНачал2|Недоступные], Обязательные, КолОбяз1),
ВесМаршрута1 = ВесМаршрута2 + 1;
переход (КлНачал, Линия, Новая_Линия),
соседние (КлНачал, КлНачал2, Новая_Линия),
not (принадлежит (КлНачал2, Недоступные)),
принадлежит (КлНачал2, Обязательные),
КолОбяз2 = КолОбяз1 – 1,
маршрут (КлНачал2, КлКонеч, [КлНачал2|Хвост], ВесМаршрута2, Новая_Линия, [КлНачал2|Недоступные], Обязательные, КолОбяз2),
ВесМаршрута1 = ВесМаршрута2 + 1.
/* ВЫВОД МАРШРУТА */
% вывод последней клетки маршрута
write_маршрут([Клетка], Линия): – линия (Линия, Список),
принадлежит (Клетка, Список), write(Клетка).
% вывод клетки без перехода
write_маршрут([Клетка, Клетка2|Хвост], Линия):-
соседние (Клетка, Клетка2, Линия),
write (Клетка,» –»),
write_маршрут([Клетка2|Хвост], Линия).
% вывод клетки c переходом
write_маршрут([Клетка, Клетка2|Хвост], Линия):-
переход (Клетка, Линия, Новая_Линия),
соседние (Клетка, Клетка2, Новая_Линия),
write (Клетка,» –»),
write_маршрут([Клетка2|Хвост], Новая_Линия).
/* ВВОД ОБЯЗАТЕЛЬНЫХ СТАНЦИЙ */
ввод_назв_обяз (0, [], []): – !.
ввод_назв_обяз (1, Обязательные, ВведенныеОбяз):-
write («Введите последнюю обязательную клетку:»),
readln(Клетка),
not (принадлежит (Клетка, ВведенныеОбяз)),
Обязательные=[Клетка],!.
ввод_назв_обяз (КолОбяз, Обязательные, ВведенныеОбяз):-
КолОбяз>1,
write («Введите обязательную клетку:»),
readln(Клетка),
not (принадлежит (Клетка, ВведенныеОбяз)),
КолОбяз2=КолОбяз-1,
ввод_назв_обяз (КолОбяз2, Обязательные2, [Клетка|ВведенныеОбяз]),
Обязательные=[Клетка|Обязательные2],!;
write («Клетка с таким названием уже была введена»),
nl,
ввод_назв_обяз (КолОбяз, Обязательные, ВведенныеОбяз).
ввод_кол_обяз(КолОбяз):-
write («Сколько обязательных клеток Вы хотите ввести:»),
readln(Строка),
str_int (Строка, КолОбяз),!;
write («Необходимо ввести целое число. Пожалуйста, повторите ввод.»),
nl,
ввод_кол_обяз(КолОбяз).
ввод_обяз (Обязательные, КолОбяз): – ввод_кол_обяз(КолОбяз), ввод_назв_обяз (КолОбяз, Обязательные, []).
/* ЗАПУСК ПРОГРАММЫ */
run: – write («Выбор маршрута передвижения в лабиринте с посещением обязательных клеток»), nl,
write («Схему лабиринта можно найти в приложении пояснительной записки»), nl,
write («Введите название начальной клетки =»), readln(КлНачал),
write («Введите название конечной клетки =»), readln(КлКонеч),
ввод_обяз (Обязательные, КолОбяз),
findall (ВесМаршрута, маршрут (КлНачал, КлКонеч,_, ВесМаршрута,_, [КлНачал], Обязательные, КолОбяз), СписокВесМаршрута),
мин (ВесМаршрута, СписокВесМаршрута),
маршрут (КлНачал, КлКонеч, Маршрут, ВесМаршрута,_, [КлНачал], Обязательные, КолОбяз),
write («Оптимальный маршрут:»), nl,
write_маршрут (Маршрут,_), nl,
КолСт=round(ВесМаршрута),
write («Количество шагов:», КолСт), nl.
GOAL
run.
Приложение
Схема использованного в программе лабиринта
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
| A | X | X | ||||||
| B | X | |||||||
| C | X | X | X | X | ||||
| D | X | |||||||
| E | X | X | ||||||
| F | X | X | X | X | X | |||
| G | ||||||||
| H | X |
0 комментариев