Сравнение эвристик A* для решения N-головоломки

Я пытаюсь решить N-головоломку, используя алгоритм A * с 3 различными эвристическими функциями. Я хочу знать, как сравнить каждую из эвристик с точки зрения временной сложности. Я использую следующие эвристики: манхэттенское расстояние, манхэттенское расстояние + линейный конфликт, обмен N-max. И специально для головоломки на 8 и на 15.


algorithm a-star graph-algorithm heuristics sliding-tile-puzzle
person Petros Sofianos    schedule 23.02.2017    source источник
comment
Эвристики обычно сравнивают экспериментально.   -  person harold    schedule 24.02.2017
comment
Но как я могу их сравнить??   -  person Petros Sofianos    schedule 24.02.2017
comment
Например, генерируя псевдослучайные (поместите начальное число и PRNG в свою статью) перетасовки и записывая количество изученных узлов.   -  person harold    schedule 24.02.2017

Ответы (2)


arrow_upward
1
arrow_downward

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

Если вы ограничитесь головоломкой с 8 или 15 головоломками, алгоритм A * с любой допустимой эвристикой будет работать за время O (1), поскольку существует конечное (хотя и большое) количество позиций на доске.

person Paul Hankin    schedule 23.02.2017

arrow_upward
1
arrow_downward

Как сказал @Harold в своем комментарии, подход к сравнению временной сложности эвристических функций обычно основан на экспериментальных тестах. В вашем случае сгенерируйте набор из n случайных задач для головоломки с 8 и 15 и решите их, используя разные эвристические функции. Вещи, о которых следует знать:

  1. Сравнение всегда будет зависеть от нескольких факторов, таких как характеристики оборудования, язык программирования, ваши навыки при реализации алгоритма...

  2. Вообще говоря, более информированная эвристика всегда будет расширять меньше узлов, чем менее информированная, и, вероятно, будет быстрее.

И, наконец, чтобы сравнить три эвристики для каждого набора задач, я бы предложил график со средним временем выполнения (повторить, например, 5 раз каждую задачу), где:

  1. Задачи отсортированы по оси x по сложности.
  2. Время работы указано по оси Y для каждой эвристической функции (возможно, в логарифмическом масштабе, если разницу между альтернативами трудно увидеть).

и аналогичный график с количеством исследованных состояний.

person FrankS101    schedule 24.02.2017