Вот два способа построения эвристики:
Один из распространенных способов построения эвристики - это ослабить первоначальное определение проблемы, чтобы позволить новые действия, которые ранее не могли быть предприняты. Это может только сделать решение короче, поэтому мы можем использовать это для получения допустимого heuristi c. Текущая проблема ограничивает то, что только два человека могут быть на мосту одновременно и что им нужен факел, чтобы пересечь мост. Если вы ослабите оба требования, вы просто потратите максимум времени на то, чтобы пересечь кого-то с оригинальной стороны, и это даст вам допустимый heuristi c. То есть вы предполагаете, что они просто все пересекаются, и все готово.
Пример 1:
Оригинал: AB C D [факел]
Цель :
Heuristi c: 8 минут (максимум 1, 2, 5, 8)
Пример 2:
Оригинал: AB C
Цель: D [факел]
Heuristi c: 5 минут (максимум 1, 2, 5)
Вы можете сделать немного лучше расслабляя только один из них - им все еще нужен факел, но на мосту может оказаться любое количество людей. Если горелка находится на оригинальной стороне, это heuristi c выше. В противном случае вы можете добавить минимальное время, чтобы вернуть факел к исходной стороне. (И если факел с кем-то медленным, этот медленный человек будет частью вычислений heuristi c в обе стороны.)
Пример 3:
Оригинал: AB C
Цель: D [факел]
Heuristi c: 16 минут (8, чтобы получить D с факелом, 8, чтобы вернуть всех)
Пример 4:
Оригинал: C D
Цель: AB [факел]
Heuristi c: 9 минут (1 для получения A с факелом, 8, чтобы вернуть всех)
Другой способ состоит в том, чтобы абстрагировать проблему в подзадачу (в абстрактной задаче всего k из N человек) и полностью ее решить. Тогда heuristi c для текущего состояния - это стоимость решения для k человек в абстрактной задаче. Вы можете сделать несколько абстракций и взять максимум, чтобы улучшить эвристику таким образом.