1 тема
Фермер пересекает реку с волком, овцой и ношей травы. Лодка может одновременно перевозить только фермера и тот же товар. Волк съест овцу, а овца съест траву. Только когда фермер там будет безопасно. Теперь я хочу сделать так, чтобы все предметы, включая фермера, благополучно перешли другую сторону реки, и использовать программу для решения проблемы.
2 Анализ дизайна
Расположите фермера, волка, овцу и траву в порядке "фермер, волк, овца, трава" и используйте логический массив для представления их статуса. Логическое значение status false означает, что соответствующий человек (вещь) не пересекал река, а статус верный. Это означает, что соответствующее лицо (вещь) пересекло реку. Одним из преимуществ использования булевых значений является то, что текущее состояние можно обратить, чтобы получить состояние на противоположной стороне реки (независимо от того, была ли река пересечена изначально).
Видно, что в начальном состоянии они:
status[4] = [false, false, false, false]
После пересечения реки их состояние должно быть [правда, правда, правда, правда]
Ситуация переправы представлена до и после изменения состояния массива status[4], тогда правило переправы соответствует компьютерной логике следующим образом:
1) Каждый раз, когда вы пересекаете реку, фермер обязан участвовать - каждый раз, когда меняется состояние, 0-й бит (примечание: начинается счет 0-го нижнего индекса) должен быть изменен;
2) Каждый раз, когда вы пересекаете реку, вы можете принести только один предмет, и вам нужен фермер, чтобы плыть по лодке — каждый раз, когда вы меняетесь, 1-я, 2-я и 3-я позиции могут меняться не более чем на 1 из них, а изменение позиции должно быть синхронизировано с 0-й позицией;
3) Когда один из трех волков, овец и травы является другой едой, присутствие фермера должно быть безопасным - после каждого изменения, если 1-й, 2-й и 3-й соседствуют друг с другом, они должны быть одинаковыми. так как 0-е биты одинаковы.
В соответствии с этим правилом используйте массив в качестве корневого узла текущего состояния для генерации всех последующих состояний, а затем перечислите последующие ситуации для получения числовой структуры состояния:
В этом дереве состояние в правой части третьего слоя (то есть после того, как фермер приводит овец, а затем возвращает овец) выглядит так же, как и корневой результат, поэтому нет необходимости продолжать генерировать его дети. Другие узлы (например, крайнее правое состояние четвертого слоя), если они выглядят так же, как узел родителя, не должны продолжать генерировать (обходить) поддерево, потому что последующая ситуация, генерируемая этим состоянием, должна повторяться. с предыдущим состоянием.
3 кодировка
Сначала блок-схема:
Согласно правилам, чтобы определить, является ли состояние безопасным (законным) - когда одно является пищей для другого, если они находятся на одной стороне реки, фермер должен присутствовать, чтобы быть в безопасности. Логика кода следующая (код Python):
def is_valid_status(status):
if status[1] == status[2]:
if status[0] != status[1]:
# 狼和羊同侧，没有人在场
return False
if status[2] == status[3]:
if status[0] != status[2]:
# 羊和草同侧，没有人在场
return False
return TrueВ текущем состоянии перечислить все ситуации, порождающие следующее состояние, то есть все возможные ситуации для перехода через реку на следующем шаге. Отрицать состояние — значит пересечь реку, будь то прошлое или возвращение — просто отрицай его. Логика кода следующая:
def create_all_next_status(status):
next_status_list = []
for i in range(0, 4):
if status[0] != status[i]: # 和农夫不同一侧？
continue
next_status = [status[0],status[1],status[2],status[3]]
# 农夫和其中一个过河，i 为 0 时候，农夫自己过河。
next_status[0] = not next_status[0]
next_status[i] = next_status[0] # 和农夫一起过河
if is_valid_status(next_status):
next_status_list.append(next_status)
return next_status_list
Шаги логического кода рекурсивного обхода дерева следующие:
1) Во всех случаях, когда все последующие состояния генерируются на основе текущего состояния,
2) Пройдите и оцените все ситуации сгенерированного состояния,
(1) Если следующее состояние является окончательным желаемым состоянием (все пересекли реку), выведите результат текущего пути,
(2) Если следующее состояние уже появилось в истории, игнорировать его,
(3) Если следующим состоянием является новое состояние, запишите это состояние в историю и рекурсивно выполните шаг 1.
Код поиска выглядит следующим образом, что является центральной идеей логики рекурсивного обхода дерева (не по теме: логика рекурсивного обхода шахматных игр тоже похожа):
def search(history_status):
global scheme_count
current_status = history_status[len(history_status) - 1]
next_status_list = create_all_next_status(current_status)
for next_status in next_status_list:
if next_status in history_status:
# 出现重复的情况了
continue
history_status.append(next_status)
if is_done(next_status):
scheme_count += 1
print("scheme " + str(scheme_count) + ":")
print_history_status(history_status)
else:
search(history_status)
history_status.pop()Проще судить, перешли ли они реку:
def is_done(status):
return status[0] and status[1] and status[2] and status[3]
Полный код выглядит следующим образом:
#-*- coding: UTF-8 -*-
name = ["farmer", "wolf", "sheep", "grass"]
scheme_count = 0
# 完成局面
def is_done(status):
return status[0] and status[1] and status[2] and status[3]
# 生成下一个局面的所有情况
def create_all_next_status(status):
next_status_list = []
for i in range(0, 4):
if status[0] != status[i]: # 和农夫不同一侧？
continue
next_status = [status[0],status[1],status[2],status[3]]
# 农夫和其中一个过河，i 为 0 时候，农夫自己过河。
next_status[0] = not next_status[0]
next_status[i] = next_status[0] # 和农夫一起过河
if is_valid_status(next_status):
next_status_list.append(next_status)
return next_status_list
# 判断是否合法的局面
def is_valid_status(status):
if status[1] == status[2]:
if status[0] != status[1]:
# 狼和羊同侧，没有人在场
return False
if status[2] == status[3]:
if status[0] != status[2]:
# 羊和草同侧，没有人在场
return False
return True
def search(history_status):
global scheme_count
current_status = history_status[len(history_status) - 1]
next_status_list = create_all_next_status(current_status)
for next_status in next_status_list:
if next_status in history_status:
# 出现重复的情况了
continue
history_status.append(next_status)
if is_done(next_status):
scheme_count += 1
print("scheme " + str(scheme_count) + ":")
print_history_status(history_status)
else:
search(history_status)
history_status.pop()
def readable_status(status, is_across):
result = ""
for i in range(0,4):
if status[i] == is_across:
if len(result) != 0:
result += ","
result += name[i]
return "[" + result + "]"
#打印结果
def print_history_status(history_status):
for status in history_status:
print(readable_status(status, False) + "≈≈≈≈≈≈≈≈≈≈" + readable_status(status, True))
if __name__ == "__main__":
# 初始局面
status = [False, False, False, False]
# 局面队列
history_status = [status]
search(history_status)
print("finish search, find " + str(scheme_count) + " scheme")
5 бегущих результатов
Из результатов вывода видно, что есть две ситуации:
Вариант А:
1) Фермер приводит овец
2) Фермер возвращается сам
3) Фермер берет туда волка
4) Фермер возвращает овец
5) Фермер приносит туда траву
6) Фермер возвращается сам
7) Фермер ведет туда овец
1) Фермер приводит овец
2) Фермер возвращается сам
3) Фермер приносит туда траву
4) Фермер возвращает овец
5) Фермер берет туда волка
6) Фермер возвращается сам
7) Фермер ведет туда овец