Решение задачи про козу, капусту и волка через конечный автомат

Постановка задачи
Есть река и надо перевести на другой берег козу, капусту и волка. В лодку помещается только крестьянин и что-то одно из груза: капуста, волк или коза. Если на одном берегу без присмотра крестьянина оставить козу и капусту, то коза съест капусту. Если оставить волка и козу, то волк съест козу. Как перевести груз без потерь?

Решение
Решать задачу буду через конечный автомат.

Фаза 1: Перечислить стостояния
Конфигурацию берегов можно представить в виде одного байта при помощи битов.

Таблицу надо заполнить бинарным кодом. Затем отсеять нереальные состояния
1) когда два волка на обоих берегах
2) когда ни одного волка на обоих берегах
3) когда две капусты на обоих берегах
4) когда ни одной капусты на обоих берегах
и т п

Перебор всех состояний с проверкой на валидность показывает, что у нас всего только 16 реальных состояний

N:1,Code:0x0f=15=0b0000_1111,Left:Right:goat,cabbage,wolf,peasant,
N:2,Code:0x1e=30=0b0001_1110,Left:wolf,Right:goat,cabbage,peasant,
N:3,Code:0x2d=45=0b0010_1101,Left:cabbage,Right:goat,wolf,peasant,
N:4,Code:0x3c=60=0b0011_1100,Left:cabbage,wolf,Right:goat,peasant,
N:5,Code:0x4b=75=0b0100_1011,Left:goat,Right:cabbage,wolf,peasant,
N:6,Code:0x5a=90=0b0101_1010,Left:goat,wolf,Right:cabbage,peasant, [!]
N:7,Code:0x69=105=0b0110_1001,Left:goat,cabbage,Right:wolf,peasant, [!]
N:8,Code:0x78=120=0b0111_1000,Left:goat,cabbage,wolf,Right:peasant, [!]
N:9,Code:0x87=135=0b1000_0111,Left:peasant,Right:goat,cabbage,wolf, [!]
N:10,Code:0x96=150=0b1001_0110,Left:wolf,peasant,Right:goat,cabbage, [!]
N:11,Code:0xa5=165=0b1010_0101,Left:cabbage,peasant,Right:goat,wolf, [!]
N:12,Code:0xb4=180=0b1011_0100,Left:cabbage,wolf,peasant,Right:goat,
N:13,Code:0xc3=195=0b1100_0011,Left:goat,peasant,Right:cabbage,wolf,
N:14,Code:0xd2=210=0b1101_0010,Left:goat,wolf,peasant,Right:cabbage,
N:15,Code:0xe1=225=0b1110_0001,Left:goat,cabbage,peasant,Right:wolf,
N:16,Code:0xf0=240=0b1111_0000,Left:goat,cabbage,wolf,peasant,Right:

Из этих 16-ти состояний есть 6 опасных состояния. Например, когда нельзя оставлять без присмотра волка и козу или козу и капусту на одном из берегов.

N:6,Code:0x5a=90=0b0101_1010,Left:goat,wolf,Right:cabbage,peasant, [!]
N:7,Code:0x69=105=0b0110_1001,Left:goat,cabbage,Right:wolf,peasant, [!]
N:8,Code:0x78=120=0b0111_1000,Left:goat,cabbage,wolf,Right:peasant, [!]
N:9,Code:0x87=135=0b1000_0111,Left:peasant,Right:goat,cabbage,wolf, [!]
N:10,Code:0x96=150=0b1001_0110,Left:wolf,peasant,Right:goat,cabbage, [!]
N:11,Code:0xa5=165=0b1010_0101,Left:cabbage,peasant,Right:goat,wolf, [!]

Суть задачи в том, чтобы найти легальный способ перейти из состояния 0xF0 в состояние 0x0F.

Фаза 2: Определить входные возденйствия
Входные воздействия это то, что меняет состояния. Из логики задачи входы -это действия крестьянина. Получается всего 8 входов:
1) Перевести козу с левого берега на правый.
2) Перевести капусту с левого берега на правый.
3) Перевести волка с левого берега на правый.
4) Переплыть без груза с левого берега на правый.
5) Перевести козу с правого берега на левый.
6) Перевести капусту с правого берега на левый.
7) Перевести волка с правого берега на левый.
8) Переплыть без груза с правого берега на левый.

Фаза 3: Определить действия КА
Действиями тут являются сами состояния. Это автомат Мура. Есть зеленые состояния (безопасные), а есть красные (опасные). В красные состояния нельзя заходить.

Фаза 4: Построить таблицу переходов

Таблица переходов тут получается весьма громоздкая. При этом многое переходы оказываются абсурдными для конкретных состояний. Лучше сразу рисовать граф.

Фаза 5: Построить граф переходов

По таблице переходов строится граф конечного автомата. Для визуализации можно построить граф кодом на языке Graphviz

digraph G {

splines=ortho
rankdir=TB
 
 node [shape=box];

St00001111lrTCWG->St11000011lTGrCW [label="RL_GOAT"] [color="red"] [fontcolor="red"]
St00001111lrTCWG->St10100101lCGrTWDanger [label="RL_CABBAGE"] [color="black"] [fontcolor="black"]
St00001111lrTCWG->St10010110lWGrTCDanger [label="RL_WOLF"] [color="blue"] [fontcolor="blue"]
St00001111lrTCWG->St10000111lGrTCWDanger [label="RL_ALONE"] [color="navy"] [fontcolor="navy"]
St00011110lWrTCG->St11010010lTWGrC [label="RL_GOAT"] [color="red"] [fontcolor="red"]
St00011110lWrTCG->St10110100lCWGrT [label="RL_CABBAGE"] [color="black"] [fontcolor="black"]
St00011110lWrTCG->St10010110lWGrTCDanger [label="RL_WOLF"] [color="blue"] [fontcolor="blue"]
St00011110lWrTCG->St10010110lWGrTCDanger [label="RL_ALONE"] [color="navy"] [fontcolor="navy"]
St00101101lCrTWG->St11100001lTCGrW [label="RL_GOAT"] [color="red"] [fontcolor="red"]
St00101101lCrTWG->St10100101lCGrTWDanger [label="RL_CABBAGE"] [color="black"] [fontcolor="black"]
St00101101lCrTWG->St10110100lCWGrT [label="RL_WOLF"] [color="blue"] [fontcolor="blue"]
St00101101lCrTWG->St10100101lCGrTWDanger [label="RL_ALONE"] [color="navy"] [fontcolor="navy"]
St00111100lCWrTG->St11110000lTCWGr [label="RL_GOAT"] [color="red"] [fontcolor="red"]
St00111100lCWrTG->St10110100lCWGrT [label="RL_CABBAGE"] [color="black"] [fontcolor="black"]
St00111100lCWrTG->St10110100lCWGrT [label="RL_WOLF"] [color="blue"] [fontcolor="blue"]
St00111100lCWrTG->St10110100lCWGrT [label="RL_ALONE"] [color="navy"] [fontcolor="navy"]
St01001011lTrCWG->St11000011lTGrCW [label="RL_GOAT"] [color="red"] [fontcolor="red"]
St01001011lTrCWG->St11100001lTCGrW [label="RL_CABBAGE"] [color="black"] [fontcolor="black"]
St01001011lTrCWG->St11010010lTWGrC [label="RL_WOLF"] [color="blue"] [fontcolor="blue"]
St01001011lTrCWG->St11000011lTGrCW [label="RL_ALONE"] [color="navy"] [fontcolor="navy"]
St10110100lCWGrT->St00011110lWrTCG [label="LR_CABBAGE"] [color="lightyellow"] [fontcolor="lightyellow"]
St10110100lCWGrT->St00101101lCrTWG [label="LR_WOLF"] [color="tomato"] [fontcolor="tomato"]
St10110100lCWGrT->St00111100lCWrTG [label="LR_ALONE"] [color="green"] [fontcolor="green"]
St11000011lTGrCW->St00001111lrTCWG [label="LR_GOAT"] [color="darkgreen"] [fontcolor="darkgreen"]
St11000011lTGrCW->St01001011lTrCWG [label="LR_CABBAGE"] [color="lightyellow"] [fontcolor="lightyellow"]
St11000011lTGrCW->St01001011lTrCWG [label="LR_WOLF"] [color="tomato"] [fontcolor="tomato"]
St11000011lTGrCW->St01001011lTrCWG [label="LR_ALONE"] [color="green"] [fontcolor="green"]
St11010010lTWGrC->St00011110lWrTCG [label="LR_GOAT"] [color="darkgreen"] [fontcolor="darkgreen"]
St11010010lTWGrC->St01011010lTWrCGDanger [label="LR_CABBAGE"] [color="lightyellow"] [fontcolor="lightyellow"]
St11010010lTWGrC->St01001011lTrCWG [label="LR_WOLF"] [color="tomato"] [fontcolor="tomato"]
St11010010lTWGrC->St01011010lTWrCGDanger [label="LR_ALONE"] [color="green"] [fontcolor="green"]
St11100001lTCGrW->St00101101lCrTWG [label="LR_GOAT"] [color="darkgreen"] [fontcolor="darkgreen"]
St11100001lTCGrW->St01001011lTrCWG [label="LR_CABBAGE"] [color="lightyellow"] [fontcolor="lightyellow"]
St11100001lTCGrW->St01101001lTCrWGDanger [label="LR_WOLF"] [color="tomato"] [fontcolor="tomato"]
St11100001lTCGrW->St01101001lTCrWGDanger [label="LR_ALONE"] [color="green"] [fontcolor="green"]
St11110000lTCWGr->St00111100lCWrTG [label="LR_GOAT"] [color="darkgreen"] [fontcolor="darkgreen"]
St11110000lTCWGr->St01011010lTWrCGDanger [label="LR_CABBAGE"] [color="lightyellow"] [fontcolor="lightyellow"]
St11110000lTCWGr->St01101001lTCrWGDanger [label="LR_WOLF"] [color="tomato"] [fontcolor="tomato"]
St11110000lTCWGr->St01111000lTCWrGDanger [label="LR_ALONE"] [color="green"] [fontcolor="green"]

 
 
 }

Граф переходов можно отрисовать при помощи программы dot

Фаза 6: проложить путь в графе переходов

При наличии графа переходов конечного автомата остается только проложить путь от начального состояния к целевому состоянию.

Этот путь и будет являться решением задачи

Результат

Вот так, при помощи обыкновенного конечного автомата удалось решить классическую задачу про козу, капусту и волка.

Ссылки