С учетом этих фактов
connection(philly,nyc,no).
connection(nyc,philly,no).
connection(philly,harrisburg,no).
connection(harrisburg,philly,no).
connection(paris,nyc,yes).
connection(nyc,paris,yes).
passport(harrisburg).
, где connection имеет аргументы from, to, passport needed
и эти контрольные примеры
:- begin_tests(travel).
travel_test_case_generator( harrisburg ,harrisburg ,no ,[harrisburg] ).
travel_test_case_generator( harrisburg ,harrisburg ,yes ,[harrisburg] ).
travel_test_case_generator( harrisburg ,philly ,no ,[harrisburg,philly] ).
travel_test_case_generator( harrisburg ,philly ,yes ,[harrisburg,philly] ).
travel_test_case_generator( harrisburg ,nyc ,no ,[harrisburg,philly,nyc] ).
travel_test_case_generator( harrisburg ,nyc ,yes ,[harrisburg,philly,nyc] ).
travel_test_case_generator( harrisburg ,paris ,yes ,[harrisburg,philly,nyc,paris] ).
travel_test_case_generator( harrisburg ,paris ,no ,[harrisburg,philly,nyc,philly,harrisburg,passport,philly,nyc,paris] ).
travel_test_case_generator( philly ,philly ,no ,[philly] ).
travel_test_case_generator( philly ,philly ,yes ,[philly] ).
travel_test_case_generator( philly ,nyc ,no ,[philly,nyc] ).
travel_test_case_generator( philly ,nyc ,yes ,[philly,nyc] ).
travel_test_case_generator( philly ,paris ,yes ,[philly,nyc,paris] ).
travel_test_case_generator( philly ,paris ,no ,[philly,nyc,philly,harrisburg,passport,philly,nyc,paris] ).
travel_test_case_generator( nyc ,paris ,yes ,[nyc,paris] ).
travel_test_case_generator( nyc ,paris ,no ,[nyc,philly,harrisburg,passport,philly,nyc,paris] ).
test(001,[forall(travel_test_case_generator(Start,End,Passport,Expected_route))]) :-
route(Start,End,Passport,Route),
assertion( Route == Expected_route ).
:- end_tests(travel).
Вот решение с использованием пролог . Этот код был написан как подтверждение концепции, чтобы увидеть, как ответить на вопрос. Он не был записан в спецификации вопроса, поэтому, если вы знаете Пролог, вы найдете очевидные места, где его можно улучшить или не реализовать алгоритм, как ожидалось.
route(Start,End,Passport,Route) :-
route(Start,End,Passport,[],Route_reversed),
reverse(Route_reversed,Route), !.
route(City,City,_,Route0,Route) :-
visit(City,Route0,Route).
route(A,C,yes,Route0,Route) :-
connection(A,B,_),
\+ member(B,Route0),
visit(A,Route0,Route1),
route(B,C,yes,Route1,Route).
route(A,C,no,Route0,Route) :-
connection(A,B,Need_passport),
\+ member(B,Route0),
(
(
Need_passport == yes,
\+ member(passport,Route0)
)
->
(
get_passport_shortest(A,Route1),
route(B,C,yes,[],Route2),
reverse(Route0,Route0_reversed),
append([Route0_reversed,[A],Route1,Route2],Route_reversed),
reverse(Route_reversed,Route)
)
;
(
visit(A,Route0,Route1),
route(B,C,no,Route1,Route)
)
).
route_no(A,A,no,Route,Route).
route_no(A,C,no,Route0,Route) :-
connection(A,B,no),
\+ member(B,Route0),
visit(B,Route0,Route1),
route_no(B,C,no,Route1,Route).
get_passport(A,Route) :-
passport(B),
route_no(A,B,no,[],Route1),
route_no(B,A,no,[],Route2),
reverse(Route1,Route1_reversed),
reverse(Route2,Route2_reversed),
append([Route1_reversed,[passport],Route2_reversed],Route).
visit(City,Route0,Route) :-
(
Route0 = [City|_]
->
Route = Route0
;
Route = [City|Route0]
).
get_passport_shortest(A,Shortest_route) :-
findall(Route,get_passport(A,Route),Routes),
select_shortest(Routes,Shortest_route).
select_shortest([H|T],Result) :-
length(H,Length),
select_shortest(T,Length,H,Result).
select_shortest([],_Current_length,Result,Result).
select_shortest([Item|T],Current_length0,Current_shortest0,Result) :-
length(Item,Item_length),
(
Item_length < Current_length0
->
(
Current_length = Item_length,
Current_shortest = Item
)
;
(
Current_length = Current_length0,
Current_shortest = Current_shortest0
)
),
select_shortest(T,Current_length,Current_shortest,Result).
Когда тестовый пример запустите
?- make.
% c:/so_question_159 (posted) compiled 0.00 sec, 0 clauses
% PL-Unit: travel ................ done
% All 16 tests passed
true.
Весь тестовый проход.
Причина, по которой паспорт находится в Гаррисберге, а не в Филадельфии, заключается в том, что при тестировании кода код работал, когда паспорт находился в Филадельфии. , Затем, добавив Harrisburg и протестировав снова, проблема была обнаружена в коде и исправлена. Если изменить passport(harrisburg). на passport(philly)., код будет работать, но для этого потребуются дополнительные тестовые случаи.
Дополнительные вопросы размещены в комментариях и перенесены сюда.
Из гродзи
В ваших тестах строка (третья от конца) philly, paris, no, почему philly,nyc,philly, harrisbug..., когда вы можете просто сделать philly,harrisburg,philly..., чтобы получить паспорт? Это намеренная или какая-то незначительная ошибка?
Приятно видеть, что кто-то обращает внимание. Это не ошибка, и это был один из тестов, которые выявили ошибку, когда паспорт был в Гаррисберге. То, как я интерпретирую проблему, как указано в OP, случай путешествия - просто более понятная версия его реальной проблемы, связанной с динамическим c FSA с входом и выходом из системы. Так что зная, что вам нужен паспорт, неизвестно, пока вы не попытаетесь совершить поездку с nyc до paris. На данный момент вам нужен паспорт, если его нет в руке, и вам нужно вернуться к harrisbug, чтобы получить его.
Так что да, это выглядит странно с обычной проблемой решающего путешествия, и мы, люди, можем легко посмотрите на оптимизацию, либо из-за опыта, либо из-за превосходных способностей, либо из заглядывания вперед и знания, что нам нужен паспорт, чтобы добраться до paris, но система не знает, что ему нужен паспорт, пока он не понадобится. Я могу добавить к этому больше правил и условий, но в настоящее время есть только паспорт. Однако, если ОП добавляет больше условий, тогда я задам новый вопрос, потому что этот вопрос должен был быть более конкретным c.
Из OP
Что касается условий глубиной в несколько слоев, как ваш пример показывает это?
На данный момент это не так, потому что не было никаких правил, необходимых для этого. Он был задан как вопрос для тех, кто имеет или планирует ответить на него, так как это будет выбор, который им придется сделать при написании кода.
Из OP
Ваш пример с окном пароля пытается увидеть, как FSM обрабатывает ошибку пользователя?
Нет, я только посмотрел на ваши основные идеи в опубликованном вопросе.
Этот вопрос относится к ОП код , размещенным на GitHub
Ссылки на значение
Грамматика атрибутов ( Википедия )
Автоматическое планирование и планирование ( Википедия ) ( Пример пролога )
RosettaCode Алгоритм Дейкстры
Разрешение SLD
Выполнение таблицы (разрешение SLG)
Декларативное программирование - 3: logi c программирование и пролог