Автор: Админка

Как перевести волка козу и капусту на другой берег


Волк, коза и капуста. Загадка на логику.

Эта известная головоломка есть в народном творчестве таких стран, как Италия, Румыния, Эфиопия и Зимбабве. Существует не одна ее вариация: с лисой, курицей и хлебом или с пантерой, свиньей и кашей! А Ты знаешь, как решать задачу о переправе?

14 90 т.

Итак, представь, что Ты — фермер, у которого есть маленькая лодка. С одного берега реки на другой Тебе необходимо перевезти волка, козу и капусту. Всех вместе взять нельзя — нужно переправлять каждого «пассажира» по отдельности. Но имей в виду, что когда Ты повезешь на другой берег капусту, в это время волк съест козу. А если решишь везти волка — коза скушает капусту.

Что же делать? Хорошенько поразмысли. Рейсов можно делать сколько угодно — главное, чтобы все оставалось целым и невредимым.

Ну как, удалось решить эту нелегкую задачку? Все еще нет? Ну ладно, дам одну подсказку: переправлять «пассажира» можно не только туда, но и назад!

Что же — думаю, теперь Тебе удалось перевезти всех целыми и невредимыми! Посмотри на решение задачи и проверь, все ли сходится.

  1. Сначала нужно перевезти козу, оставив волка с капустой.
  2. Теперь возвращаемся и забираем волка. Но оставлять волка с козой на новом берегу нельзя.
  3. Поэтому берем козу с собой в лодку, а волк сидит на берегу одинокий и голодный.
  4. Козу оставляем на берегу, а капусту переправляем к волку.
  5. Возвращаемся назад и забираем козу.

Кстати, это не единственный вариант решения задачи. Вот еще один:

  1. Везем козу туда.
  2. Возвращаемся обратно.
  3. Везем капусту туда.
  4. Забираем козу назад.
  5. Везем волка туда.
  6. Возвращаемся за козой.
  7. Перевозим козу туда.

Готово!

А теперь признавайся, удалось ли Тебе самостоятельно дойти до правильного решения, и если да — то каким способом? ;)

Еще больше отборных загадок найдешь тут:

Заметили орфографическую ошибку? Выделите её мышкой и нажмите Ctrl+Enter

Решение проблемы с волком, козой и капустой (форум Programming Diversions на Coderanch)

Нет, Джим Инст, вам не нужно думать о том, что происходит, когда фермер переходит реку, или о том, что делает лодка; вы просто предполагаете, что лодка находится там, где находится фермер. На самом деле я получил 16 возможных состояний, пронумерованных от 0 до f, где самый старший бит (3-й бит = 8) представляет фермера, 2-й бит = 4 - это волк, 1-й бит = 2 - это гусь, а 0- -й бит (младший бит = 1) представляет собой зерно капусты или что-то еще.

Итак, f означает, что все четверо находятся на этой стороне реки, 0 означает, что все четыре пересеклись, 1 означает, что капуста одна на этой стороне реки, 2 означает, что гусь один на этой стороне реки и т. Д. можно было бы подумать, что это означает, что дополнение числа находится на другой стороне реки, поэтому 0 означает f на другой стороне. Тогда у вас будет инвариант thisSide + thatSide == 0xf.
По эту сторону реки есть три запрещенных штата: 3, 6, 7, где гусь ест капусту, лес - козу, или и то, и другое.Это означает, что на другой стороне есть три запрещенных состояния, 8 9 и c. Мы знаем, что 8 + 7 или 9 + 6 или c + 3 в сумме дают 0xf. Остается в общей сложности 10 разрешенных состояний. За каждым разрешенным состоянием могут следовать 1, 2 или 3 разрешенных состояния-преемника.

Правила таковы, что фермер должен переходить дорогу каждый раз в одиночку или в сопровождении одного предмета. Это эквивалентно побитовой операции XOR 8 9 a или c; если у вас есть переменные thisSide и thatSide, то одна и та же операция должна быть применена к обеим сторонам, чтобы сохранить инвариант класса.Также вы удаляете из результатов любое из шести запрещенных состояний.
Вы можете вернуть состояния обратно на английский с помощью побитового И: private final int FARMER = 8, WOLF = 4, GOOSE = 2, CABBAGE = 1; . . . . если (состояние и ФЕРМЕР> 0) outputString + = "фермер"; если (состояние & WOLF> 0) outputString + = "волк"; и т. д.

Затем вы получаете дерево, начинающееся с f, и затем вы проводите поиск дерева, пока не найдете в нем 0. Для достижения 0 требуется ровно 7 операций, первая из которых - состояние ^ = FARMER + GOOSE;

*********************************************** ***************************
В LISP он читает что-то вроде этого, предполагая, что ваш алгоритм поиска по ширине и оператор -> уже поставлено: (defparameter * farmer * '((fwgcR wcRfg) (fwgRc wRfgc gRfwc) (fwcRg wcRfg wRfgc cRfwg) (fgcRw gRfwc cRfwg) (fgRwc gRfwc Rfwgc) (wcRfg fwcRg fwgcR) (gRfwc fgRwc fwgRc fwcRg) (cRfwg fwcRg fgcRw) (wRfgc fwgRc fwcRg) (Rfwgc fgRwc))) (defun farmer-lmg (состояние) (-> * фермер * штат)) (width-search 'fwgcR' Rfwgc # 'farmer-lmg) Аббревиатуры (очевидно) означают фермерскую волчью гусиную капусту и РЕКУ; те, кто до R, находятся на этой стороне, а те, что после R, находятся на этой стороне.Бит defun создает генератор легального хода (LMG).
*********************************************** **************************
С предоставленными нами утилитами LISP он работает, но, кажется, всегда дает мне один и тот же ответ . Я думаю, есть 4 возможных решения, но первая операция всегда заключается в том, что фермер переносит гуся, а четвертая операция всегда возвращает гуся.

[править] Незначительные орфографические исправления и значение lmg [/ править]
[30 ноября 2007 г .: Сообщение отредактировал: Кэмпбелл Ричи]

.

искусственный интеллект - PDDL - Коза, волк и капуста

Переполнение стека
  1. Около
  2. Товары
  3. Для команд
  1. Переполнение стека Общественные вопросы и ответы
  2. Переполнение стека для команд Где разработчики и технологи делятся частными знаниями с коллегами
  3. Вакансии Программирование и связанные с ним технические возможности карьерного роста
  4. Талант Нанимайте технических специалистов и создавайте свой бренд работодателя
  5. Реклама Обратитесь к разработчикам и технологам со всего мира
  6. О компании

Загрузка…

  1. Авторизоваться зарегистрироваться
  2. текущее сообщество

.

Головоломка: Волк, коза и капуста

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

  1. Преобразование проблемы в структуры данных и функции
  2. Выберите стратегию поиска решения

Стратегия решения может быть методом Монте-Карло, генетическим алгоритмом, жадным поиском и т. Д.Как только вы остановитесь на переводе, вы можете обнаружить, что другая альтернативная формулировка лучше подходит для стратегии решения, поэтому вам может потребоваться переформулировать перевод. Можно с уверенностью предположить, что ваши первые решения будут менее элегантными, чем более поздние версии, поэтому продолжайте работать над ними.

На берегу реки волк, коза и капуста. У вас есть лодка, в которой поместится любое животное или растение. Вы хотите перенести на другую сторону и животных, и овощ. Однако, если вы оставите волка и козу одних на берегу, пока вы переправляете капусту, волк съест козу.Точно так же, если вы переправляете волка, оставив козу с капустой. Как вы перевозите всех трех пассажиров по одному, чтобы никто не поглотил друг друга?

Первый ход - единственно возможный: нужно переправить козу. На втором ходу вы можете подобрать волка или капусту. Допустим, вы переправляете волка следующим, а затем вам нужно посадить козу в лодку по возвращении на первый берег. Перемещаясь таким образом взад и вперед, вы можете переправить всех трех пассажиров на другую сторону.Это также можно было бы переформулировать как разлученную тётю, бывшую и шурина, путешествующую между Миннеаполисом и Сент-Полом, и превратить в болезненно неловкий инди-фильм о семейных связях и важности чего бы то ни было.

Это мой первый набросок, поэтому он обязательно неэлегантен. Позже я хотел бы найти решение с помощью Prolog, но моего Prolog Foo еще нет. Я также хотел бы сделать это более гибким, включив больше участников, «матрицу съедобности» и возможность создания нескольких островов вместо двух банков.

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

Эта первая функция смотрит на один банк и возвращает True , если из этого банка можно безопасно выйти, и False , если выход из этого банка приведет к тому, что что-то будет поглощено.

 импортировать случайный как rnd импорт scipy.stats из импорта pylab * def compare (x): '' ' Сравните каждый элемент `x` с каждый второй элемент `x`. Пункты закодированы как целые числа. Если один предмет можно съесть другой элемент, затем абсолютное значение их разница равна единице. Мы будем рассмотреть все `x`; если мы найдем один где угодно, тогда мы вернем False, в противном случае мы вернем True.'' ' # создать временный список tmp = список () # определить, сколько элементов в x N = len (x) # для каждого элемента в x .. для i в диапазоне (N): # сравнить с любым другим элементом в x для j в диапазоне (i + 1, N): # записываем абсолютное значение # разница двух предметов tmp.append (abs (x [i] - x [j])) # если в tmp стоит 1, это означает # что-то съели, возвращаем False если 1 в tmp: return False # else return True еще: вернуть True 

Эта функция использует вышеуказанную функцию и проверяет судно и оба берега.Если он возвращает True , тогда банки и лодка находятся в допустимом состоянии в соответствии с ограничениями проблемы, в противном случае он возвращает False .

 def check (x, y, z): '' ' Первое условие подсчитывает, сколько вещи в лодке. Следующее делает проверяет, осталось ли что-нибудь на банки могут есть что угодно. '' ' # Если в # лодка, затем верните False если len (y)> 1: return False # Если что-нибудь на любом берегу можно съесть # что-нибудь еще в этом банке, тогда # return False если len (y) == 1: если сравнить (x): если сравнить (z): вернуть True return False # Если у лодки правильный номер # жильцов и банки в безопасности # затем верните True вернуть True 

Я не знал, как назвать эту функцию.(Я не знал, как вызвать любую из этих функций.) Эта функция принимает текущее состояние и возвращает множество возможных ходов, как законных, так и незаконных. (Плавные) ходы кодируются как строки. Исходный (левый) берег - X , лодка - Y , а другой (правый) берег - Z . Мне это нравится, потому что это напоминает мне о математических задачах, и потому что аналогия слева и справа применима к буквам, когда вы думаете об алфавите.

Строка «X1R» означает «переместить элемент списка с одним индексом x на вправо », якобы в лодку.Строка «Z0L» означает «переместить элемент с нулевым индексом из списка z на левый в ожидающую лодку. Строка «YL», и «YR», означает «переместить лодку влево» и «переместить лодку вправо» соответственно. Это было совершенно произвольно, но я подумал, что это обеспечивает хороший баланс между краткостью и удобочитаемостью при отладке.

 def think (x, y, z): '' ' Это принимает текущее состояние и возвращает множество потенциально легальных и незаконных действий.'' ' # создаем пустой список ходов перемещается = список () # если лодка пуста .. если len (y) == 0: # если что-то есть на левом берегу если len (x)> 0: # предлагаем добавить каждый элемент на # левый берег к лодке для i в диапазоне (len (x)): move.append ('X' + str (i) + 'R') # если что-то есть на правом берегу если len (z)> 0: # предлагаем добавить каждый элемент на # правый берег к лодке для i в диапазоне (len (z)): движется.добавить ('Z' + str (i) + 'L') # если лодка полна .. еще: # предлагаю сдать вещи # на лодке на любом берегу move.append ('YL') move.append ('YR') # возвращаем возможные ходы ответные ходы 

Этот монстр принимает текущее состояние берегов и лодки в дополнение к потенциальному ходу, а затем возвращает либо новое состояние, если это допустимый ход, либо Ложь . Мы будем использовать этого парня в понимании списка с условным условием if в конце.(Условное условное в отличие от трехстороннего условного условное условие .)

 def оценивать (x, y, z, mv): '' ' Это принимает текущее состояние оригинала банк `x`, лодка` y`, другой берег `z` и некоторый ход `mv` закодирован как строка. Он возвращается новое состояние берегов и лодки, если move является допустимым, иначе возвращается False. '' ' # превращаем строку в список строк mv = [i for i in mv] # делаем копии банков x и z, # и лодку посередине, y tx, ty, tz = x [:], y [:], z [:] # сделать первый ход start = mv.поп (0) # если первый ход с лодки .. если start == 'Y': # взять предмет из лодки, y, # и положим на левый берег, x. если mv [0] == 'L': tx.append (ty.pop ()) # взять предмет с лодки, y, # и положите на правый берег, z. если mv [0] == 'R': tz.append (ty.pop ()) # если первый ход с левого берега .. elif start == 'X': # возьмите этот предмет с левого берега, x, # и положите на лодку, y.ty.append (tx.pop (int (mv.pop (0)))) # если первый ход с правого берега .. elif start == 'Z': # возьмите этот предмет с правого берега, z, # и положите на лодку, y. ty.append (tz.pop (int (mv.pop (0)))) # проверяем состояние # лодка и берега - допустимое состояние # и вернем новые состояния если проверить (tx, ty, tz): возврат tx, ty, tz # иначе вернуть False еще: return False 

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

 def test (): # начальное состояние с волком (2), # коза (1) и капуста (0) x = список ([0,1,2]) y = список () z = список () # счетчик я = 0 # запускаем цикл в то время как True: # увеличить счетчик я + = 1 # если у вас все пассажиры # на другой берег, затем остановите цикл если len (z) == 3: перерыв # генерируем кучу ходов движется = думать (x, y, z) # выбрать легальные ходы legal = [mv для mv в ходах, если оценивать (x, y, z, mv)] # произвольно оцениваем допустимый ход x, y, z = оценивать (x, y, z, rnd.выбор (законный)) # если мы пройдем 1000 шагов, то # остановим цикл и закончим если я == 1000: перерыв # вернуть количество итераций вернуться я # создаем список для # количество итераций раз = список () # несколько раз .. для k в диапазоне (10000): # посмотрим, сколько итераций это # требуется для решения проблемы times.append (тест ()) 

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

 counts, bin, patch = hist (times, bin = 60, alpha = 0.5) title («Количество шагов, необходимых для решения головоломки») ylabel ("Количество решений") xlabel («Количество шагов для решения») savefig ("puzzle_histogram.png", fmt = "png", dpi = 200) 

.

AlCollins / Wolf-Goat-Capbage-Farmer: Решение проблемы выращивания волчьей козьей капусты для курса CS по искусственному интеллекту

перейти к содержанию Зарегистрироваться
  • Почему именно GitHub? Особенности →
    • Обзор кода
    • Управление проектами
    • Интеграции
    • Действия
    • Пакеты
    • Безопасность
    • Управление командой
    • Хостинг
    • мобильный
    • Истории клиентов →
    • Безопасность →
  • Команда
  • Предприятие
  • Проводить исследования
    • Изучить GitHub →
    Учитесь и вносите свой вклад
    • Темы
.

Смотрите также


Информация
Посетители, находящиеся в группе Гости, не могут оставлять комментарии к данной публикации.



Понравился рецепт? Подпишись на RSS! Подписаться!