Пролог - Помогите исправить правило

Question

У меня есть база данных, полная фактов, таких как:

overground(newcrossgate,brockley,2).
overground(brockley,honoroakpark,3).
overground(honoroakpark,foresthill,3).
overground(foresthill,sydenham,2).
overground(sydenham,pengewest,3).
overground(pengewest,anerley,2).
overground(anerley,norwoodjunction,3).
overground(norwoodjunction,westcroydon,8).
overground(sydenham,crystalpalace,5).
overground(highburyandislington,canonbury,2).
overground(canonbury,dalstonjunction,3).
overground(dalstonjunction,haggerston,1).
overground(haggerston,hoxton,2).
overground(hoxton,shoreditchhighstreet,3).

пример: newcrossgate to brockley занимает 2 минуты.

Затем я создал правило, так что если я введу запрос istime(newcrossgate, honoroakpark, Z).тогда пролог должен дать мне время, необходимое для путешествия между этими двумя станциями.(Правило, которое я сделал, предназначено для расчета расстояния между любыми двумя станциями, а не только соседними).

istime(X,Y,Z):- istime(X,Y,0,Z); istime(Y,X,0,Z).
istime(X,Y,T,Z):- overground(X,Y,Z), T1 is T + Z.
istime(X,Y,Z):- overground(X,A,T), istime(A,Y,T1), Z is T + T1.
istime(X,Y,Z):- overground(X,B,T), istime(B,X,T1), Z is T + T1.

кажется, что он идеально подходит для новых перекрестных врат на первые пару станций, например, новых перекрестных в лесной или лесной холм.Однако, после тестирования newcrossgate на westcroydon, которое занимает 26 минут, я попробовал newcrossgate to crystalpalace и пролог сказал, что это займет 15 минут ... несмотря на то, что это следующая станция после westcroydon.Ясно, что здесь что-то не так, однако это работает для большинства станций, время от времени появляясь со случайной ошибкой во времени, может кто-нибудь сказать мне, что не так?: S

Answer 1

Это, по сути, та же проблема, что и ваш предыдущий вопрос, с той лишь разницей, что вам нужно накапливать время по ходу дела.

Одна вещь, которую я вижу, это то, что ваш "публичный" предикат, istime/3 пытается сделать слишком много Все, что он должен сделать, это заполнить аккумулятор и вызвать рабочий предикат istime/4. Поскольку вы ищете маршрут / время в обоих направлениях, общедоступный предикат должен быть просто

istime( X , Y , Z ) :- istime( X , Y , 0 , Z ) .
istime( X , Y , Z ) :- istime( Y , X , 0 , Z ) .

Выше приведено первое предложение вашего предиката istime/3

istime(X,Y,Z):- istime(X,Y,0,Z); istime(Y,X,0,Z).

Остальные пункты istime/3, рекурсивные:

istime(X,Y,Z):- overground(X,A,T), istime(A,Y,T1), Z is T + T1.
istime(X,Y,Z):- overground(X,B,T), istime(B,X,T1), Z is T + T1.

должен быть частью istime/4 и иметь аккумулятор. Вот где твоя проблема.

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

Некоторые подсказки

1. Ваш предикат "работника", скорее всего, будет очень похож на ваше предыдущее упражнение "найти маршрут между двумя станциями", но у него будет дополнительный аргумент, накопитель за истекшее время.

2. Есть два особых случая. Если вы используете подход, который вы использовали в своем решении «найти маршрут между двумя станциями», особые случаи:

   • A и B находятся в непосредственной близости.
   • A и B подключены через хотя бы один промежуточный упор.

Существует также другой подход, который можно описать как использование lookahead, в этом случае особые случаи

• A и B одинаковы, и в этом случае вы прибыли.
• A и B не связаны и соединены нулем или несколькими промежуточными остановками.

FWIW, Вы не обязательно должны ожидать, что маршрут с самым коротким истекшим временем или минимальным количеством прыжков будет первым найденным решением. При обратном отслеживании будут получены все маршруты, но порядок, в котором они находятся, связан с порядком, в котором факты хранятся в базе данных. Минимальная стоимость поиска графика - это еще один котелок рыбы.

Answer 2

Для того, чтобы это сработало, вам нужно выполнить в обратном порядке обе поездки, указанные в вашем последнем пункте. Сохраните предикат как есть, istime (X, Y, Z) и просто сделайте еще одно предложение, содержащее обратные путешествия. Таким образом, он работает со всеми станциями. (Испытано и проверено)

Answer 3

Вы пробовали циклически проходить ответы с ;?26 минут - это , а не самое короткое время между Ньюкроссгейтом и Весткройдоном ...

Редактировать : плохо!По-видимому, более короткие результаты были вызваны ошибкой в ​​вашем коде (см. Мой комментарий о четвертом предложении).Тем не менее, ваш код верен, 15 минут - самый короткий путь между newcrossgate и crystalpalace.Только потому, что существует маршрут, который идет от Ньюкроссгейта до Весткройдона, а затем от Crystalpalace, это не означает, что это маршрут кратчайший или маршрут, который ваша программа выдаст первой.

Обновление : если у вас возникают проблемы с поиском ответов на некоторые маршруты, я бы предложил изменить 3-е предложение на:

istime(X,Y,_,Z):- overground(X,A,T), istime(A,Y,T1), Z is T + T1.

Причина проста: ваше первое предложение заменяет X на YЭто хорошо, так как вы говорите, что маршруты симметричны.Тем не менее, третье предложение не приносит пользы, потому что оно никогда не вызывается замененным.Игнорирование 3-го аргумента (который вы в любом случае не используете) и, таким образом, позволение 1-му предложению вызывать 3-е может решить вашу проблему, поскольку некоторые действительные маршруты, которые ранее не использовались, будут теперь.согласен с ответом Николая Кэри, лучше использовать третий аргумент в качестве накопителя, но, как я уже сказал, игнорирование его на данный момент может сработать)