Я очень новичок в Прологе и понятия не имею, как на самом деле начать это упражнение.
Советы и примеры будут очень признательны.
У нас есть сад с патио. В саду посажено случайное количество деревьев, и между каждым деревом и внутренним двориком проходит ровно одна дорожка. Кроме того, некоторые деревья связаны друг с другом ровно одним путем. Мы знаем длину каждого пути.
Примером такого сада являются следующие факты:
patio_to_tree(t1,4).
patio_to_tree(t2,4).
patio_to_tree(t3,1).
patio_to_tree(t4,6).
patio_to_tree(t5,12).
tree_to_tree(t1,t2,4).
tree_to_tree(t2,t3,7).
tree_to_tree(t2,t4,2).
Задача состоит в том, чтобы написать предикатную прогулку / 2, которая вычисляет список P кратчайшего пути вокруг сада, чтобы вы использовали каждый путь только один раз и посетили каждое дерево. Прогулка всегда начинается и заканчивается во внутреннем дворике.
Пример для сада, описанного выше:
walk(P,L).
P = [t, b1, b2, b4, t, b3, t, b5, t].
L = 42.
Предикат должен работать только с двумя переменными, например, ему не нужно вычислять путь для заданной длины L.
Мой опыт работы с Прологом ограничен простым списком и арифметическими примерами, поэтому я не уверен, с чего начать. Я подумал, что findall / 3 может быть полезен для получения списка всех деревьев в саду, так как их может быть любое количество. Возможно, мне придется рекурсивно просмотреть этот список, чтобы получить дополнительную информацию о деревьях, но каким должен быть мой базовый вариант? Самая простая прогулка - это когда в саду нет деревьев, так что это будет просто P = [t], L = 0. Так это подходящий базовый случай?
Я предполагаю, что кратчайший путь, который отвечает требованиям, - это просто посещение каждого дерева, которое не связано с другим деревом, и возвращение во внутренний дворик, а затем посещение каждого дерева, которое связано с другим деревом по порядку. Нужен ли мне аккумулятор для хранения общей длины посещенных путей или есть более простой способ получить это?
Я заметил, что это очень похоже на проблему, называемую проблемой коммивояжера, за исключением того, что есть центральный момент, к которому можно вернуться, но я не уверен, что должен решить эту проблему аналогичным образом.
Заранее спасибо за помощь.