misscann.htm

misscann0.htm , misscann1.htm

false.ref , true.ref , true1.ref

misscann.zip

Миссионеры и каннибалы

       При работе над этим параграфом мне помогали многие. Некоторые моменты дискуссии по постановке задачи помещены в misscann0.htm, по решению задачи - в  misscann1.htm.

      Оригинальная задача.

      Missionaries and Cannibals. Turchin's example from the Refal-5 book.

      Consider the well-known problem ``Missionaries and Cannibals''. Three missionaries and three cannibals come to the bank of a river and see a boat. They want to cross the river. The boat, however, can carry no more than two people. There is a further restriction. At no time should the number of cannibals on either bank of the river (including the moored boat) exceed the number of missionaries (because the missionaries would then be overpowered and eaten). How (if at all) is it possible to cross the river?

      Рассмотрим более общую задачу. Несколько миссионеров и каннибалов переправляются через речку. В каких случаях переправка возможна, а в каких невозможна.

      Ответ в этой задаче представим в виде таблицы бесконечной вправо и вниз.

      Буквой T отмечены случаи, когда перевозка возможна. Сложность вызывают те клетки, где перевозка невозможна. Там, где перевозка возможна, там достаточно предъявить конкретный способ. Там, где перевозка невозможна, там это надо доказывать, надо доказывать, что любая последовательность не приводит к успеху.

      Я предлагаю использовать суперкомпиляцию для полного заполнения таблицы в несколько этапов. Суперкомпилятор позволяет это сделать !

      Суперкомпилируется задание

<MissCann ( e.left ) ( e.path ) > ;

где  e.path - последовательность перевозок,
       e.left   - миссионеры и каннибалы на левом берегу в начальный момент.
Результат замены -
     истина, если заданная переправка e.path заканчивается успехом (все на правом берегу), или
     ложь (или отождествление невозможно), если переправка не успешна.

      Приводим две программы false.ref , true.ref, которые отличаются в закомментированных строчках в двух местах в функции Miss. Вариант false.ref для случая, когда я хочу доказывать невозможность решения, true.ref - для поиска конкретной перевозки.

      Последовательность перевозок e.path - последовательность, состоящая из символов  M, C, MM, MC, CC, соответствующих условию задачи.

      Компанию людей e.left представляем в виде тройки ( e.m ) ( e.p ) ( e.c ), где
     e.m - последовательность символов 'm', каждый из которых соответствует одному миссионеру,
     e.c - последовательность символов 'c', каждый из которых соответствует одному каннибалу,
     e.p - последовательность пар миссионер-каннибал, при этом миссионеры расположены сначала, а потом каннибалы.

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

      Предусмотрел бессмысленность двух одинаковых переездов туда-сюда. Остальные бессмысленные поездки я не анализирую.

      Следующие 6 примеров суперкомпиляций полностью заполняют таблицу с ответами.

      Пример 1. Три миссионера и три каннибала. Суперкомпилируется программа true.ref. Ищутся решения, предложение с ложью игнорируется путем "отождествление невозможно". 

      Задание на суперкомпиляцию

<MissCann (( ) ('mmmccc') ( )) (e.path)>;

      Суперкомпилятор строит программу

/*
$ENTRY Go {
 = <Prout <P31 e.path >> ;
}
*/

P31 {
 MC e.1  , <F19 e.1 >:e.118  = T (e.118 ) ;
 CC e.1  , <F251 e.1 >:e.136  = T (e.136 ) ;
}

F251 {
 C CC C MM MC MM C CC M MC e.1  = e.1 ;
 C CC C MM MC MM C CC C CC e.1  = e.1 ;
 C M MC CC e.1  = <F251 e.1 > ;
}

F19 {
 M CC C MM MC MM C CC M MC e.1  = e.1 ;
 M CC C MM MC MM C CC C CC e.1  = e.1 ;
 M C CC MC e.1  = <F19 e.1 > ;
}

      Результат замены я искусственно сделал не просто T, а с остатком пути, тогда получается именно такая программа (иначе ничего не понятно). e.1 можно игнорировать при анализе ответа.

      Суперкомпилятор строит не одно решение, а множество всех решений. Видно, что последовательности C M MC CC и M C CC MC относятся к бессмысленным. Можно, конечно, за счет усложнения программы удалять и эти перевозки. 

      Наконец, мы видим, что имеется не одно решение, а четыре осмысленных.

      Случаи, когда имеется только одна пара миссионер-каннибал, приведен в mc.htm, случай двух пар - в mmcc.htm.

      Пример 2. 4 миссионера и 4 каннибала. Пример не является необходимым, поскольку пример 3 его перекрывает. 

      Суперкомпилируем программу false.ref с анализом неудачных переправок (с ложью). Если этого не делать, то получится программа

e.1 = F; 

в которой ни в чем нельзя быть уверенным.

       Задание на суперкомпиляцию

  <MissCann  (( ) ('mmmmcccc') ( )) (e.path)>;

      Суперкомпилятор строит программу.

/*
$ENTRY Go {
 = <Prout <P41 e.path >> ;
}
*/

P41 {
 MC e.1  , <F19 e.1 >:s.140 (e.141 ) (e.142 )
         = F s.140 (() (e.141 ) (e.142 )) ;
 CC e.1  , <F206 e.1 >:s.183 (e.184 ) (e.185 )
         = F s.183 (() (e.184 ) (e.185 )) ;
 C  = F R (() () ('c' )) ;
}

F206 {
  = R () ('cc' ) ;
 C  = L () ('c' ) ;
 C CC  = R () ('ccc' ) ;
 C CC C  = L () ('cc' ) ;
 C CC C MM  = R ('mmcc' ) () ;
 C CC C MM MC  = L ('mc' ) () ;
 C CC C CC  = R () ('cccc' ) ;
 C CC C CC C  = L () ('ccc' ) ;
 C M  = R ('mc' ) () ;
 C M MC  = L () () ;
 C M MC CC e.1  , <F206 e.1 >:s.200 (e.201 ) (e.202 )
                = s.200 (e.201 ) (e.202 ) ;
 C M MC C  = R () ('c' ) ;
}

F19 {
  = R ('mc' ) () ;
 M  = L () ('c' ) ;
 M CC  = R () ('ccc' ) ;
 M CC C  = L () ('cc' ) ;
 M CC C MM  = R ('mmcc' ) () ;
 M CC C MM MC  = L ('mc' ) () ;
 M CC C CC  = R () ('cccc' ) ;
 M CC C CC C  = L () ('ccc' ) ;
 M C  = R () ('cc' ) ;
 M C CC  = L () () ;
 M C CC MC e.1  , <F19 e.1 >:s.197 (e.198 ) (e.199 )
                = s.197 (e.198 ) (e.199 ) ;
 M C CC C  = R () ('c' ) ;
}

      Видно, что истины здесь нет, более того, суперкомпилятор сразу выносит F в результат. Я сделал так, что результатом замены является не просто F, а F с указаниями, где лодка, и кто на правом берегу (если последовательность перевозок закончилась).

      Пример 3. Самый интересный случай. Миссионеров и каннибалов больше трех и поровну.

     Задание на суперкомпиляцию

<MissCann ( ( ) ( 'mmmm' e.p 'cccc' ) ( ) ) (e.path) > :

      Суперкомпилируем программу false.ref с анализом неудачных переправок.

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

      Суперкомпилятор строит программу fp4pref.htm.

      Вроде ничего не пропускается. Как теперь понять, что все нормально? Придется, наверное, все же как-то анализировать эту остаточную программу, а не просто сказать, что в ней нет истины.

      Я пробовал повторно суперкомпилировать эту программу, фиксируя начальное количество пар. Все происходило очень быстро. Там четко видно, что случай увеличения каннибалов на правом берегу анализируется.

      Пример 4. Случай, когда миссионеров больше, чем каннибалов - переправка возможна. Суперкомпиляция предложенных программ false.ref , true.ref приводит к необозримым результатам ввиду обилия решений.

      Я поступил так. Внес изменения в программу, оставив перевозки MM, MC, MC с левого берега на правый и M, C с правого на левый (true1.ref). Смысл состоит в том, чтобы увеличивать количество людей справа и тем самым приближаться к решению. Замечу, что такое изменение программы могло оказаться неудачным, например, для трех миссионеров и трех каннибалов, как я попробовал, перевозки из этого класса не существует.

      Короче, о чем мы спрашиваем суперкомпилятор, то он нам и отвечает.

      Суперкомпилируем для случая трех миссионеров и двух каннибалов, получаем программу

* InputFormat: <MP21 e.1 >
MP21 {
 MC M MM M MM M MC e.1  = T (e.1 ) ;
 MC M MM M MM C CC e.1  = T (e.1 ) ;
 MC M MM M MC C MC e.1  = T (e.1 ) ;
 MC C MC M MM M MC e.1  = T (e.1 ) ;
 MC C MC M MM C CC e.1  = T (e.1 ) ;
 MC C MC M MC C MC e.1  = T (e.1 ) ;
 CC C MM M MM M MC e.1  = T (e.1 ) ;
 CC C MM M MM C CC e.1  = T (e.1 ) ;
 CC C MM M MC C MC e.1  = T (e.1 ) ;
}

      Отсюда можно извлечь, к примеру, что последовательность из четырех перевозок

MC C MC M

если лодка слева, добавляет на правый берег пару миссионер-каннибал при условии, что слева есть хотя бы один "лишний" миссионер. Многократное применение этой последовательности приводит к успеху.

      Пример 5. В начальный момент имеются только миссионеры (в любом количестве). Суперкомпилируется программа true.ref, задание на суперкомпиляцию 

<MissCann ( (e.m) ( ) ( ) ) (e.path) > :

      Суперкомпилятор строит программу

/*
$ENTRY Go {
 = <Prout <M_1 (e.m ) e.path >> ;
}
*/

M_1 {
 (e.1 'mm' ) MM e.2  , <F52 (e.1 ) () e.2 >:e.113  = T (e.113 ) ;
}

F52 {
 () (e.106 ) e.107  = e.107 ;
 (e.105 'm' ) (e.106 'm' ) M MM e.107
      = <F52 (e.105 ) (e.106 'mm' ) e.107  > ;
 (e.105 'm' ) () M MM e.107  = <F52 (e.105 ) ('m' ) e.107 > ;
}

      Пример 6. В начальный момент имеются только каннибалы (в любом количестве). Суперкомпилируется программа true.ref, задание на суперкомпиляцию 

<MissCann ( ( ) ( ) ( e.c ) ) (e.path) > :

      Суперкомпилятор строит программу

/*
$ENTRY Go {
 = <Prout <C_1 (e.c ) e.path >> ;
}
*/

C_1 {
 ('cc' e.1 ) CC e.2  , <F60 (e.1 ) e.2 >:e.111  = T (e.111 ) ;
}

F60 {
 () e.107  = e.107 ;
 ('c' e.105 ) C CC e.107  = <F60 (e.105 ) e.107 > ;
}

      Таким образом, я считаю, что задача решена, и ответ такой. 

      Если каннибалов больше, чем миссионеров (не =0), то переправка невозможна. Если миссионеров больше, чем каннибалов, то переправка возможна. При равенстве, переправка возможна лишь при одной, двух или трех парах.