lxsmkv Oct 15 2017 at 15:29

Задача о переправе

5 min

20K

Studying in IT

From sandbox

+10

Comments 21

LightSUN Oct 15 2017 at 16:29

Имхо сложность тут вовсе не алгоритмическая, а в том, что под «перевезти» в жизни понимается перемещение груза только в одно направление — вся «сложность» в том, чтобы догадаться, что можно груз возить обратно.

lxsmkv Oct 15 2017 at 22:43

Очень верное замечание. В задаче имеется неявное правило. Именно поэтому я думаю, в программировании всегда нужен будет человек, чтобы из задачи сформулированной на человеческом языке, выделять правила явные, и неявные. Это как раз то, что мы понимаем под словом «думать» и чему, как мне кажется, машина в сегодняшнем ее виде, никогда не сможет «научиться».

lxsmkv Oct 17 2017 at 06:22

Я тут еще размышлял над этим, и мне стало ясно, что выведение правил и условий из поставленной задачи по сути явлется анализом требований. Значит requirements engineering это интересная и чертовски сложная умственная работа. И, ссылаясь на замечание Dr_Dash ниже, любопытно, что хороший инженер выведет условия как в статье, а превосходный инженер скажет, что «мужик не нужен». И сэкономит этим самым деньги клиента.

Dr_Dash Oct 15 2017 at 17:17

Я занимался решением этой задачи через автоматы, то есть хотел построить автомат решающий эту задачу для Х коз Y волков Z капуст и K крестьян, и формулируя эту задачу конкретнее, я понял, что по сути это задача-обманка. Просто нужен свежий взгляд. Смотрите о чём я:
Есть два «инертных» элемента — волк и капуста, которые никак не влияют друг на друга, и есть «активный» элемент сродственный обоим элементам, который не должен комбинироваться ни с одним из других. Крестьянина считать элементом комбинации нецелесообразно. Когда крестьянин на берегу мы это не должны считать комбинацией вообще. Комбинация фиксируется только тогда когда крестьянин плывёт по реке, а когда он на берегу, это переход между состояниями. В комбинациях участвуют только те элементы, которые не в лодке.
А теперь представляем себе задачу с начальными условиями «на этом берегу крестьянин, волк и капуста, а на том коза»(получается из нашей задачи предварительной перевозкой козы), и тогда у нас имеется как бы два параллельно протекающих процесса, и даже не связанных по большому счёту:
1 крестьянин перевозит на тот берег волка, возвращается, потом перевозит капусту.
2 на обратном пути между перевозкой волка и капусты, коза переезжает с того берега на этот.
В результате мы имеем на выходе полную симметрию начальному условию: на том берегу волк, капуста и крестьянин, на этом коза. Осталось забрать козу.
При такой формулировке «активный» элемент никогда не входит в комбинацию с «инертными»
Любое увеличение коз, капуст или волков порождает уже другую задачу, не столь элегантную.

lxsmkv Oct 15 2017 at 22:35

2 на обратном пути между перевозкой волка и капусты, коза переезжает с того берега на этот.

По условиям оригинальной задачи, перемещение возможно только с участием крестьянина. А так получается у нас какая-то квантовая физика уже, коза как бы еще там но уже не там. В классической машине Тъюринга нет неопределенности. Или мы в одном состоянии или в другом. Нет никакого промежуточного состояния. Как и нет процесса. Т.е. процесс конечно можно смоделировать в пригодном для машины Тьюринга виде, но это будет тоже состояние. Машина Тьюринга не имеет памяти, т.е если остановить ее в какой-то момент, а потом запустить снова, она просто продолжит выполнять свой алгоритм с того места на котором остановилась. (Чего не делают, кстати сказать современные персональные компьютеры)

В результате мы имеем на выходе полную симметрию начальному условию:
… Осталось забрать козу.

Да, в задаче есть симметрия. Это видно из расположения допустимых состояний на ленте, они симметичны относительно середины. Если развернуть ленту в машине Тьюринга, но не изменять программу, то когда коза на одном берегу, а все остальные на другом, машина дойдет до решения за два перехода: крестьянин поедет за козой и перевезет ее на берег, где волк, в гордом одиночестве, пасет капусту.

Dr_Dash Oct 15 2017 at 23:06

По условиям оригинальной задачи, перемещение возможно только с участием крестьянина. А так получается у нас какая-то квантовая физика

вы здесь путаете физику и математику. Мы не обсуждаем детали перемещения козы, мы составляем математическую модель которая полностью описывает процесс, и эта «квантовая» коза просто напросто исключение математически незначащего случая — кто бы ни был с крестьянином, с ним всё будет в порядке, а вот «фейл» может произойти только в комбинациях на берегу. Так проще. Попробуйте применить свою модель не учитывая крестьянина и того кто с ним, и сами убедитесь что она станет проще.

lxsmkv Oct 16 2017 at 00:25

от «мужика» избавиться не получается, это было бы недопустимым упрощением. Без него мы не сможем скомбинировать волка козу и капусту. Все таки мы перемещаем предметы из одной точки в другую и у нас есть паромщик. Если мы пренебрежём паромщиком, то у нас получится совсем другая задача. Важно при моделировании, не увлекаться и не уничтожить детали изначальной задачи, которая имеет вполне прикладной контекст. (Как в анекдоте про физика, инженера и математика на пожаре — «решение существует») При решении мы упрощаем до допустимой абстракции, а потом переводим решение, которое мы вывели для общего случая, обратно в предметную область.
Можно ведь вообще сказать «поменям берега местами» — задача решена. Нет так делать нельзя.

Dr_Dash Oct 16 2017 at 01:16

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

вы заблуждаетесь. просто побудем математиками, представьте, что у нас может происходить телепортация предмета с берега на берег, или телепортационный обмен предметов на противоположных берегах — одно из двух, а паромщик в данном случае физически отсутствует с ними на берегу. Это тот же самый случай, просто в другой обёртке Уберите из своей таблицы все строки/столбцы с P и получите этот случай и таблицу в два раза меньше

Dr_Dash Oct 16 2017 at 01:23

PS крайние случаи когда все трое вместе на берегу отбрасываем, потому что в этом случае либо паромщик сейчас возьмёт кого-то и повезёт(то есть останется только двое), либо они уже на другом берегу и паромщику плыть никуда не надо, т.е. как видите эти случаи исключаются из задачи, не влияя на дальнейший ход а в дальнейшем упоминание паромщика не требуется

lxsmkv Oct 16 2017 at 01:59

я понимаю ход мысли, но делать так нельзя, иначе мы получим производную задачу. Полученное решение производной задачи нельзя будет перевести обратно в предметную область исходной задачи. swap (обмен) предметов противоречит механизму перемещения указанному в задаче, а он — челночный. И это важный аспект предметной области для которой мы ищем решение, и пренебрегать этим нельзя.

Но я не люблю словесных баталий, давайте лучше разберем эту производную задачу «на бумаге», чтобы было на что ссылаться. Обозначим козу 1, капусту 2, а волка 4. Не допустимой будет любая нечетная комбинация.
Изначально, по условию задачи, все находятся на одном берегу. Комбинация 7. Нечетная. Это недопустимое состояние. Давайте, ради продолжения мысленного эксперимента, выведем систему из недопустимого состояния, перенеся козу на другую сторону, как Вы предлагали в исходном комментарии.
Челнок находится на другом берегу. Там где коза. Возвращаем челнок к волку с капустой. Кого бы мы не переправили на другой берег (к козе) мы получим не допустимое состояние.
Эта производная задача не решается.

Продолжим мысленный эксперимент, пусть у нас будет портал, в который можно войти либо с одной стороны либо с другой. Перенеся один предмет через портал нельзя перенести следующий предмет в том же направлении, не перенеся какой-то предмет обратно. Т.е нельзя сделать два перемещения в одну сторону это бы противоречило условию задачи. (Мужик может и не нужен, но челнок никуда не деть, это важный аспект механики предметной области) Коза перебралась через портал.Теперь чтобы открыть портал со стороны волка с капустой снова, нужно перенести козу обратно. Эта производная задача не решается, потому, что пренебрегает устройством пропускного механизма. Он челночный.

-1

Dr_Dash Oct 16 2017 at 06:42

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

а случай когда мужик перевозит козу, потом возвращается обратно за капустой(не возвращая предмет обратно) не тот?

Челнок находится на другом берегу. Там где коза. Возвращаем челнок к волку с капустой. Кого бы мы не переправили на другой берег (к козе) мы получим не допустимое состояние.
Эта производная задача не решается.

Но мы можем привести к козе хоть волка хоть капусту а козу забрать обратно, (то что я описал как «телепортационный обмен предметов на противоположных берегах». )
Вы как-то не можете абстрагироваться от этого злополучного челнока. Я же написал выше

представьте, что у нас может происходить телепортация предмета с берега на берег(крестьянин увёз козу), или телепортационный обмен предметов на противоположных берегах(привёз капусту, увёз козу обратно) — одно из двух,

это не какая-то «производная задача», это и есть та же самая задача, понимаете? И тогда у нас исчезает фигура крестьянина из таблицы, начисто. И при этом таблица полностью описывает задачу, здесь нет никакого обмана или искажения, это типа «тождественного преобразования».

lxsmkv Oct 16 2017 at 13:49

да, теперь я понял, что не до конца понял. Под телепортацией я понял телепортацию с берега на берег. Но имеется ввиду, одновременная разгрузка-загрузка челнока. Тогда все как вы говорите. Спасибо за терпение. Распишу подробно для тех, кому интересно:
Коза садится в челнок и переправляется на другой берег, челнок возвращается, капуста загружается на челнок, челнок едет к козе, капуста выгружается на другой берег, а коза тут же загружается на челнок, коза едет к волку на берег, коза выгружается, а волк загружается и перезжает к капусте. Челнок возвращается пустой, забирает козу, и перевозит ее на другой берег.

Dr_Dash Oct 17 2017 at 07:27

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

Dr_Dash Oct 15 2017 at 23:06

попробуйте свой алгоритм для нескольких участников — мне было некогда я отложил на потом ) а так интересно поглядеть что будет

akhmelev Oct 16 2017 at 07:36

Динамическое программирование тут нужно, а не ооп и алгоритмизация рассуждениями.

vartv27 Oct 16 2017 at 10:41

если будет 100+(коз, волков и крестьян), динамическое программирование на не чем не поможет, а рекурсию заменим на цикл и все будет прекрасно.

Scf Oct 16 2017 at 12:19

2 волка, 2 козы, 2 капусты — задача уже неразрешима. Что бы крестьянин ни взял в лодку, будут жертвы.

Dr_Dash Oct 16 2017 at 13:13

а вот если добавить собаку-пастуха? Пока они с волком на берегу одни у них «вооружённый нейтралитет», а если оставить их с козой, то у волка взыграет кровожадность, а у собаки чувство долга и они сцепятся. вот кстати интересно

vaniacer Oct 16 2017 at 15:29

Убежден что работать должен компьютер. Пусть компьютер подставляет циферки не нужно перекладывать это на себя. Вот как я решил эту задачу на баше:

#!/bin/bash

 left_side=('goat' 'cabbage' 'wolf')
right_side=()

function check {

  case $1:$2 in
    'goat':'cabbage' | 'cabbage':'goat' | 'wolf':'goat' | 'goat':'wolf' )
        return 1;;
    *)  return 0;;

  esac

}

while [[ ${left_side[@]} ]]; do

  for i in ${left_side[@]}; do

    passenger=${left_side[0]}
    unset left_side[0]; left_side=(${left_side[@]})

    check ${left_side[@]} && {

        right_side+=("$passenger")
        echo -e "${left_side[@]}\n$passenger -->\n${right_side[@]}\n"

    } || {

      left_side+=("$passenger")
      continue
    }

    check ${right_side[@]} || {

      passenger=${right_side[0]}
      unset right_side[0]; right_side=(${right_side[@]})
      left_side+=("$passenger")
      echo -e "${left_side[@]}\n<-- $passenger\n${right_side[@]}\n"
      continue

    }

  done

done

Вывод:
cabbage wolf
goat -->
goat

wolf
cabbage -->
goat cabbage

wolf goat
< — goat
cabbage

goat
wolf -->
cabbage wolf

goat -->
cabbage wolf goat

vaniacer Oct 16 2017 at 15:52

А потом делается рефакторинг:)

#!/bin/bash

 left_side=(${1:-'goat'} ${2:-'cabbage'} ${3:-'wolf'})
right_side=()

function check {

  case $1:$2 in
    'goat':'cabbage' | 'cabbage':'goat' | 'wolf':'goat' | 'goat':'wolf' )
        return 1;;
    *)  return 0;;

  esac

}

while [[ ${left_side[@]} ]]; do

  passenger=${left_side[0]}; unset left_side[0]; left_side=(${left_side[@]})

  check ${left_side[@]} \
  && { right_side+=("$passenger")
       echo -e "${left_side[@]}\n$passenger -->\n${right_side[@]}\n"; } \
  || { left_side+=("$passenger"); }

  check ${right_side[@]} || {
    passenger=${right_side[0]}
    unset right_side[0]
    right_side=(${right_side[@]})
    left_side+=("$passenger")
    echo -e "${left_side[@]}\n<-- $passenger\n${right_side[@]}\n"
  }

done

Scf Oct 16 2017 at 16:31

Выглядит как чувак, который колет дрова с завязанными глазами

Show the best of all time