Моя проблема заключается в сортировке строк, указанных в трех списках, с использованием реализации поиска A *, поэтому мне нужно разработать эвристическую функцию, которая позволит эффективно решать различные случаи этой проблемы.Эвристическая функция A * поиск сортировки
состояния может быть представлен с списком 3 списков, например: [[C B], [D], [H G F A E]]
я забрать верхнюю часть любого стека и переместить его в любую другую. Например, H выше может быть перемещен поверх C или D, а [HG] можно перенести во второй стек, чтобы создать [HGD] и т. Д. В этом домене есть затраты оператора на единицу, поэтому каждый перемещать затраты 1, независимо от того, сколько слов перемещается.
Цель состоит в том, чтобы взять начальную конфигурацию блоков и переместить их все в левый стек в отсортированном порядке сверху вниз. Например, учитывая 8 блоков в приведенном выше примере, целью будет [[A B C D E F G H] [] []].
Мне нужно разработать эвристику, которая может использоваться с A * search, чтобы сделать поиск эффективным. Я должен попытаться сохранить допустимую эвристику. Для этого вы можете попытаться, чтобы ваши эвристики приблизили количество шагов, оставшихся до достижения цели.
Я думаю об эвристике зависит от отсортированных слов в каждом стеке, а сумма очков каждого стека является эвристикой для состояния, но это неэффективно, я думаю, что мне нужно включить ascii-код каждого письмо к моим расчетам, любые идеи?
Итак, вы хотите отсортировать список этих проблем по количеству шагов для решения проблемы? Подсказка. Если у вас есть парное сравнение, например, на Java, убедитесь, что функция поиска вызывается только один раз для каждого элемента в списке, а не для каждой комбинации. Например, используйте хэш-карту для кэширования результатов поиска. Возможно, этого достаточно для ускорения. –
Кроме того, ваша проблема очень похожа на проблему Towers of Hanoi, просто со случайной начальной конфигурацией. Возможно, это поможет вам в поиске хорошей эвристики A *. –
да, я программирую с помощью java, единственное, что мне нужно, это значение эвристики для каждого состояния, поэтому мне нужно, чтобы алгоритм мог вычислять эвристическое значение для каждого возможного состояния, тогда я могу выбрать лучший. что вы имеете в виду именно функцией поиска? –