Это не дает мне такой вывод, и я не знаю почему.
Ваш код дает правильный ответ, как отмечено в моем предыдущем ответе .
?- solve(a,S).
S = [g, b, a] ;
Проблема не в том ответе, который дает код, но я верю в ваше понимание того, как работает алгоритм, или компоновки графика на основе фактов.
Использование бумагии ручка для работы над проблемой перед преобразованием ее в код является мудрым решением.
Вот график в визуальной форме с корнем (a) вверху.
a Level 0
/ \
b c Level 1
/ \ / \
g f r e Level 2
Обратите внимание, что кратчайший путь от a до g равен a, b, g, а не a, b, c, g, как вы ожидаете.Даже если c подключен к a, он не находится на пути от a до g и поэтому не является частью решения.
Вы правы в том, что с помощью Breadth First Search (BFS) вы начинаете с Level 0, затем обрабатываете ALL подключенных к нему узлов, которые отображаются на Level 1.Затем сделайте то же самое для каждого узла в Level 1, создав Level 2, прежде чем повторять снова для каждого нового уровня.
При обработке каждого узла BFS просто ищет любой узел, подключенный к этому текущему узлу, который он еще не посещал, и записывает любую необходимую ему информацию в таблицу или другую структуру данных.Если в вашем примере включены весовые коэффициенты для каждой вершины, то стоимость перехода к текущему обрабатываемому узлу будет записана с текущим узлом в структуре данных.Посещение узла для обработки узла - это не то же самое, что посещение узла как части кратчайшего пути от одного узла к другому.
Еще один способ подумать об этом заключается в том, что оба BFS и Поиск в глубину (DFS) должны давать одинаковые ответы, разница в алгоритме.Если вы используете DFS для этого, вы получите тот же ответ a, b и g, без c.
dfs_1(N,N,[N]).
dfs_1(Start,End,[Start|Rest] ) :-
s(Start,Next),
dfs_1(Next,End,Rest).
?- dfs_1(a,g,Path).
Path = [a, b, g] ;
false.
Из комментария:
Хорошо, я вижу, что фактическая работа алгоритма такая, как я его напечатал, включая c, но потом, когда он захочетвыведите окончательный путь, он исключит c, поскольку его нет на пути.
Я не согласен с этим.
При запуске запроса с трассировкой в SWI-Prolog
line 1 [trace] 133 ?- solve_1(a,S).
line 2 Call: (8) solve_1(a, _12870)
line 3 Call: (9) breadthfirst_1([[a]], _12870)
line 4 Call: (10) goal_1(a)
line 5 Fail: (10) goal_1(a)
line 6 Redo: (9) breadthfirst_1([[a]], _12870)
line 7 ^ Call: (10) bagof([_13076, a], (s(a, _13076), \+member(_13076, [a])), _13134)
line 8 Call: (17) s(a, _13076)
line 9 Exit: (17) s(a, b)
line 10 Call: (17) lists:member(b, [a])
line 11 Fail: (17) lists:member(b, [a])
line 12 Redo: (17) s(a, _13076)
line 13 Exit: (17) s(a, c)
line 14 Call: (17) lists:member(c, [a])
line 15 Fail: (17) lists:member(c, [a])
line 16 ^ Exit: (10) bagof([_13076, a], user:(s(a, _13076), \+member(_13076, [a])), [[b, a], [c, a]])
line 17 Call: (10) lists:append([], [[b, a], [c, a]], _13216)
line 18 Exit: (10) lists:append([], [[b, a], [c, a]], [[b, a], [c, a]])
line 19 Call: (10) breadthfirst_1([[b, a], [c, a]], _12870)
line 20 Call: (11) goal_1(b)
line 21 Fail: (11) goal_1(b)
line 22 Redo: (10) breadthfirst_1([[b, a], [c, a]], _12870)
line 23 ^ Call: (11) bagof([_13198, b, a], (s(b, _13198), \+member(_13198, [b, a])), _13256)
line 24 Call: (18) s(b, _13198)
line 25 Exit: (18) s(b, g)
line 26 Call: (18) lists:member(g, [b, a])
line 27 Fail: (18) lists:member(g, [b, a])
line 28 Redo: (18) s(b, _13198)
line 29 Exit: (18) s(b, f)
line 30 Call: (18) lists:member(f, [b, a])
line 31 Fail: (18) lists:member(f, [b, a])
line 32 ^ Exit: (11) bagof([_13198, b, a], user:(s(b, _13198), \+member(_13198, [b, a])), [[g, b, a], [f, b, a]])
line 33 Call: (11) lists:append([[c, a]], [[g, b, a], [f, b, a]], _13350)
line 34 Exit: (11) lists:append([[c, a]], [[g, b, a], [f, b, a]], [[c, a], [g, b, a], [f, b, a]])
line 35 Call: (11) breadthfirst_1([[c, a], [g, b, a], [f, b, a]], _12870)
line 36 Call: (12) goal_1(c)
line 37 Fail: (12) goal_1(c)
line 38 Redo: (11) breadthfirst_1([[c, a], [g, b, a], [f, b, a]], _12870)
line 39 ^ Call: (12) bagof([_13338, c, a], (s(c, _13338), \+member(_13338, [c, a])), _13396)
line 40 Call: (19) s(c, _13338)
line 41 Exit: (19) s(c, r)
line 42 Call: (19) lists:member(r, [c, a])
line 43 Fail: (19) lists:member(r, [c, a])
line 44 Redo: (19) s(c, _13338)
line 45 Exit: (19) s(c, e)
line 46 Call: (19) lists:member(e, [c, a])
line 47 Fail: (19) lists:member(e, [c, a])
line 48 ^ Exit: (12) bagof([_13338, c, a], user:(s(c, _13338), \+member(_13338, [c, a])), [[r, c, a], [e, c, a]])
line 49 Call: (12) lists:append([[g, b, a], [f, b, a]], [[r, c, a], [e, c, a]], _13490)
line 50 Exit: (12) lists:append([[g, b, a], [f, b, a]], [[r, c, a], [e, c, a]], [[g, b, a], [f, b, a], [r, c, a], [e, c, a]])
line 51 Call: (12) breadthfirst_1([[g, b, a], [f, b, a], [r, c, a], [e, c, a]], _12870)
line 52 Call: (13) goal_1(g)
line 53 Exit: (13) goal_1(g)
line 54 Exit: (12) breadthfirst_1([[g, b, a], [f, b, a], [r, c, a], [e, c, a]], [g, b, a])
line 55 Exit: (11) breadthfirst_1([[c, a], [g, b, a], [f, b, a]], [g, b, a])
line 56 Exit: (10) breadthfirst_1([[b, a], [c, a]], [g, b, a])
line 57 Exit: (9) breadthfirst_1([[a]], [g, b, a])
line 58 Exit: (8) solve_1(a, [g, b, a])
line 59 S = [g, b, a] ;
line 60 Redo: (12) breadthfirst_1([[g, b, a], [f, b, a], [r, c, a], [e, c, a]], _12870)
line 61 ^ Call: (13) bagof([_13484, g, b, a], (s(g, _13484), \+member(_13484, [g, b, a])), _13542)
line 62 Call: (20) s(g, _13484)
line 63 Fail: (20) s(g, _13484)
line 64 ^ Fail: (13) bagof([_13484, g, b, a], user:(s(g, _13484), \+member(_13484, [g, b, a])), _13548)
line 65 Redo: (12) breadthfirst_1([[g, b, a], [f, b, a], [r, c, a], [e, c, a]], _12870)
line 66 Call: (13) breadthfirst_1([[f, b, a], [r, c, a], [e, c, a]], _12870)
line 67 Call: (14) goal_1(f)
line 68 Fail: (14) goal_1(f)
line 69 Redo: (13) breadthfirst_1([[f, b, a], [r, c, a], [e, c, a]], _12870)
line 70 ^ Call: (14) bagof([_13484, f, b, a], (s(f, _13484), \+member(_13484, [f, b, a])), _13542)
line 71 Call: (21) s(f, _13484)
line 72 Fail: (21) s(f, _13484)
line 73 ^ Fail: (14) bagof([_13484, f, b, a], user:(s(f, _13484), \+member(_13484, [f, b, a])), _13548)
line 74 Redo: (13) breadthfirst_1([[f, b, a], [r, c, a], [e, c, a]], _12870)
line 75 Call: (14) breadthfirst_1([[r, c, a], [e, c, a]], _12870)
line 76 Call: (15) goal_1(r)
line 77 Fail: (15) goal_1(r)
line 78 Redo: (14) breadthfirst_1([[r, c, a], [e, c, a]], _12870)
line 79 ^ Call: (15) bagof([_13484, r, c, a], (s(r, _13484), \+member(_13484, [r, c, a])), _13542)
line 80 Call: (22) s(r, _13484)
line 81 Fail: (22) s(r, _13484)
line 82 ^ Fail: (15) bagof([_13484, r, c, a], user:(s(r, _13484), \+member(_13484, [r, c, a])), _13548)
line 83 Redo: (14) breadthfirst_1([[r, c, a], [e, c, a]], _12870)
line 84 Call: (15) breadthfirst_1([[e, c, a]], _12870)
line 85 Call: (16) goal_1(e)
line 86 Fail: (16) goal_1(e)
line 87 Redo: (15) breadthfirst_1([[e, c, a]], _12870)
line 88 ^ Call: (16) bagof([_13484, e, c, a], (s(e, _13484), \+member(_13484, [e, c, a])), _13542)
line 89 Call: (23) s(e, _13484)
line 90 Fail: (23) s(e, _13484)
line 91 ^ Fail: (16) bagof([_13484, e, c, a], user:(s(e, _13484), \+member(_13484, [e, c, a])), _13548)
line 92 Redo: (15) breadthfirst_1([[e, c, a]], _12870)
line 93 Call: (16) breadthfirst_1([], _12870)
line 94 Fail: (16) breadthfirst_1([], _12870)
line 95 Fail: (15) breadthfirst_1([[e, c, a]], _12870)
line 96 Fail: (14) breadthfirst_1([[r, c, a], [e, c, a]], _12870)
line 97 Fail: (13) breadthfirst_1([[f, b, a], [r, c, a], [e, c, a]], _12870)
line 98 Fail: (12) breadthfirst_1([[g, b, a], [f, b, a], [r, c, a], [e, c, a]], _12870)
line 99 Fail: (11) breadthfirst_1([[c, a], [g, b, a], [f, b, a]], _12870)
line 100 Fail: (10) breadthfirst_1([[b, a], [c, a]], _12870)
line 101 Fail: (9) breadthfirst_1([[a]], _12870)
line 102 Fail: (8) solve_1(a, _12870)
line 103 false.
При
line 7 ^ Call: (10) bagof([_13076, a], (s(a, _13076), \+member(_13076, [a])), _13134)
показывает результат посещения начального узла a, который является просто путем a и в списке известных путей равен [a].
при
line 16 ^ Exit: (10) bagof([_13076, a], user:(s(a, _13076), \+member(_13076, [a])), [[b, a], [c, a]])
для пути [a] новый список создается с использованием элемента в начале списка и посещения одного из его соседей, которые не были посещены, и добавления этого нового пути в новый список.
То же самое спуть [a] и, используя элемент в начале списка a, посетите одного из его соседей s(a,b) и добавьте этот новый путь в новый список [[b,a]].
с путем [a] и использованием элемента в начале списка a, посетите одного из его соседей s(a, c). и добавьте этот новый путь в новый список, [[b,a],[c,a]].
в
line 32 ^ Exit: (11) bagof([_13198, b, a], user:(s(b, _13198), \+member(_13198, [b, a])), [[g, b, a], [f, b, a]])
для пути [b, a] новый список создается с использованием элемента в начале списка и посещения одного из его соседей, которые не были посещены, и добавления этогоновый путь в новый список.
То есть с путем [b, a] и использованием элемента в начале списка b посетите одного из его соседей s(b, g). и добавьте этот новый путь в новый список[[g, b, a]].
с путем [b, a] и использованием элемента в начале списка b, посетите одного из его соседей s(b, f). и добавьте этот новый путь в новый список, [[g, b, a], [f, b, a]].
Обратите внимание, что ответ [g, b, a] теперь находится в новом списке, но у него нет c в пути.
При
line 50 Exit: (12) lists:append([[g, b, a], [f, b, a]], [[r, c, a], [e, c, a]], [[g, b, a], [f, b, a], [r, c, a], [e, c, a]])
всепути были созданы
[[g, b, a], [f, b, a]], [[r, c, a], [e, c, a]], [[g, b, a], [f, b, a], [r, c, a], [e, c, a]]
с использованием всех s/2 фактов, но путь с ответом [g, b, a] не содержит c.
Почему переход с conc / 3 на append / 3?
Даже если это не один из ваших вопросов, мне нужно ответить на него другим, кто читает этот вопрос, особенно тем, кто впервые изучает Пролог самостоятельно.
Это моя версия событий, связанных с conc/3 и append/3, если есть другая история об этом, расскажите;Я даже задам этот вопрос как вопрос для публикации.
Одной из лучших, если не лучшими книгами для начального обучения / преподавания Пролога является "Программирование пролога для искусственного интеллекта" Ивана Братко.( WorldCat ) ( Amazon ).
При первом изучении Пролога люди, как правило, проводят свою жизнь в структуре данных списка и получают здоровую диету append/3но в книге он решил, чтобы студенты создали свою собственную версию append/3, и назвал ее conc/3.Таким образом, во всей книге используется conc/3 и почти нет использования append/3.Теперь эти люди привыкли к conc/3 и начинают писать с ним код, публиковать его и т. Д., И это очень заразно, и вы случайно его поймали.Итак, я дал вашему коду исправление.
Проблема обращения к выводу.
Когда рекурсия используется для решения проблемы, она обычно сохраняет промежуточный результат встек.В зависимости от порядка в стеке результаты располагаются в правильном порядке или в обратном порядке.
Есть несколько способов получить результаты, которые будут возвращены из рекурсии в правильном порядке.
Для большинства новичков это получение результатов, а затем, если необходимо, просто сторнируйте результаты.Для Пролога, если результатом является список, тогда reverse / 2 работает.
?- reverse([g, b, a],R).
R = [a, b, g].
Предикаты для reverse / 2
?- listing(reverse/2).
lists:reverse(A, B) :-
reverse(A, [], B, B).
true.
?- listing(reverse/4).
lists:reverse([], A, A, []).
lists:reverse([B|A], C, D, [_|E]) :-
reverse(A, [B|C], D, E).
true.
Когда возникают большие проблемыпостоянное изменение результата даже между различными вызовами предикатов начинает увеличивать время.Это особенно верно в функциональном программировании.
Другой способ - передать аккумулятор.Чтобы продемонстрировать это, я буду использовать эту более простую версию реверса.
reverse_2(L,Result) :-
accumulator_reverse(L,[],Result).
accumulator_reverse([],A,A).
accumulator_reverse([H|T],A,Result) :-
accumulator_reverse(T,[H|A],Result).
Первое предложение инициализирует аккумулятор пустым списком [] для использования с accumulator_reverse/3
reverse_2(L,Result) :-
accumulator_reverse(L,[],Result).
два других пункта просто рекурсивно обрабатывают список, причем этот пункт является базовым регистром
accumulator_reverse([],A,A).
, то есть когда список ввода пуст ([]) и
этот пункт
accumulator_reverse([H|T],A,Result) :-
accumulator_reverse(T,[H|A],Result).
, чтобы разбить список на части [H|T] (деконструкция АКА) и добавить голову H к аккумулятору [H|A] (конструкция АКА).
Поскольку список обрабатывается с помощью
accumulator_reverse([H|T],A,Result) :-
accumulator_reverse(T,[H|A],Result).
исходный список становится все меньше и меньше, потому что голова всегда удаляется из списка, а аккумулятор растет, потому что голова из списка всегда добавляется в аккумулятор.Поскольку порядок, в котором распакован список, (спереди назад) и накопитель (спереди назад), список становится обратным.
Обычно, когда вы смотрите на измененный код Пролога, если вы видите рекурсию и базовый случай, который выглядит как
base([],A,A)
, где один из аргументов - пустой список или bottom и два других параметра одинаковы, но один связан, когда выполняется вызов, а другой не связан, когда выполняется вызов, посмотрите, не учитывается ли передача кода в код.