Задача: "Три подружжя". Пролог vs Гаскелл

Описание: Задача "Три подружжя"

Задача про три подружжя (відоміша як Jealous Husbands problem) є класичною логічною задачею з обмеженнями. У ній три подружні пари мають переправитися через річку за допомогою човна, який може перевозити одну або дві людини. Основне обмеження полягає в тому, що жодна жінка не може залишатися на одному березі з чужими чоловіками, якщо її власного чоловіка на цьому березі немає.

З формальної точки зору задача полягає в пошуку послідовності допустимих станів, що переводить систему з початкової конфігурації (усі люди та човен на лівому березі) у цільову (усі люди на правому березі), не порушуючи заданих умов безпеки на жодному з кроків.

Історичний контекст
Задача має давнє походження і зустрічається ще в середньовічних збірниках логічних задач, зокрема у працях Алкуїна Йоркського (VIII століття). У різних варіаціях вона відома також як задача про братів і сестер або ревнивих чоловіків. У сучасному контексті ця задача часто використовується як навчальний приклад для демонстрації пошуку в просторі станів, формалізації обмежень та застосування алгоритмів BFS і DFS.

Можливі підходи до реалізації та вибір BFS
Задачу можна реалізувати різними способами та різними мовами програмування:
декларативно (наприклад, у Prolog), задаючи правила і дозволяючи системі автоматично шукати розв’язок;
імперативно або функціонально, явно моделюючи стани, переходи між ними та алгоритм пошуку;
із застосуванням пошуку в глибину (DFS) або пошуку в ширину (BFS).

У цій роботі було обрано пошук у ширину (BFS), оскільки він гарантує знаходження найкоротшого розв’язку за кількістю кроків. Для даної задачі це принципово важливо, адже кожен крок відповідає реальній переправі човна, і оптимальність рішення є чітко визначеною.

Опис BFS і його використання в роботі
Алгоритм BFS розглядає задачу як граф станів, де:
вершини — це допустимі конфігурації (стани) системи;
ребра — це допустимі переходи між станами за один крок.

У реалізації кожен стан описується типом State, який містить:
положення човна;
списки людей на лівому та правому берегах.

Пошук починається з початкового стану і поступово розширюється рівень за рівнем. Для уникнення зациклення використовується множина вже відвіданих станів (Set). Для коректного відновлення шляху застосовується parent-map, який зберігає для кожного нового стану батьківський стан та набір пасажирів, що був перевезений на відповідному кроці.

Після досягнення цільового стану шлях відновлюється у зворотному напрямку — від цілі до старту — і формується впорядкована послідовність кроків.

Особливості та сильні сторони реалізації
Ключовою особливістю цієї роботи є чітке розділення логічних компонентів задачі:
Явне представлення станів Стани моделюються окремим типом з семантичними полями, що робить модель зрозумілою та типобезпечною.
Окрема функція neighbors Вона формалізує поняття одного кроку — генерацію всіх допустимих наступних станів з поточного. Це дозволяє розглядати задачу саме як пошук у графі.
Канонізація станів Списки людей на берегах сортуються, що гарантує унікальність представлення однакових конфігурацій і коректну роботу множини visited.
Ефективні структури даних Використання Set для відвіданих станів і Sequence як черги відповідає класичній реалізації BFS і покращує ефективність алгоритму.
Чистота та відсутність побічних ефектів Уся логіка побудована у функціональному стилі, без мутабельного стану.

Результат роботи програми
У результаті виконання програма знаходить коректний та найкоротший розв’язок задачі. Вивід містить покроковий опис:
номер кроку;
положення човна;
списки людей на кожному березі;
пасажирів, які були перевезені на даному кроці.
Фінальний стан підтверджує, що всі шість людей успішно переправлені на правий берег без порушення умов безпеки.

Джерела
1. Bratko, I. "Prolog Programming for Artificial Intelligence" — Chapter 11-12: Planning and Search
2. Nilsson, N. "Principles of Artificial Intelligence" — Chapter 2: Problem Solving
3. Clocksin, W., Mellish, C. "Programming in Prolog" — Chapter 7: More Example Programs

НаУКМА, ф-т Інформатики
Студенти:
© Дем`янік Катерина (https://github.com/logic-programming-...) Пролог + Гаскелл
© Самсоненко Катерина (kate-lp-three-couples/ at main · Kate-Samsonenko/kate-lp-three-couples) Гаскелл
© Шалаєв Андрій (https://github.com/logic-programming-...) Python
© Ющенко Юрій Олексійович - доцент, к.ф.-м.н.