Важность порядка работы в алгоритмах обратного отслеживания

Question

Насколько эффективны операции по каждому рекурсивному шагу алгоритмов обратного отслеживания с точки зрения эффективности этого конкретного алгоритма?

Для примера.

В Задаче Рыцарского тура.

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

На каждом шаге имеется 8 возможных (в общем) способов перемещения.

int xMove[8] = { 2, 1, -1, -2, -2, -1, 1, 2 }; 
int yMove[8] = { 1, 2, 2, 1, -1, -2, -2, -1 }; 

Если изменить этот порядок, как ...

int xmove[8] = { -2, -2, 2, 2, -1, -1, 1, 1}; 
int ymove[8] = { -1, 1,-1, 1, -2, 2, -2, 2}; 

Теперь для * п платы ДО п = 6 и порядок работы не влияет никаких видимых изменений в исполнении время,

Но если п> = 7

Первая операция (движение) время исполнения заказа составляет намного меньше чем более поздний. В таких случаях невозможно выполнить весь порядок операций O (m!) И протестировать алгоритм. Итак, как я могу определить производительность таких алгоритмов в определенном порядке движения, а точнее, как можно достичь одного (или набора) порядков операций, чтобы алгоритм был более эффективным с точки зрения времени выполнения.

Answer 1

Это интересная проблема с точки зрения Math/CS. Определенно существует перестановка (или набор перестановок), которая была бы наиболее эффективной для заданного n. Я не знаю, есть ли перестановка, которая наиболее эффективна среди всех n. Думаю, нет. Там может быть перестановка, которая лучше «в среднем» (как вы ее определяете) по всем n.

Если мне было поручено найти эффективную перестановку, я мог бы попробовать сделать следующее: я бы сгенерировал фиксированное число x случайным образом сгенерированных заказов на перемещение. Измерьте их эффективность. Для каждого из произвольно созданных движителей произвольно создавайте фиксированное количество перестановок, которые находятся рядом с оригиналом. Вычислите их эффективность. Теперь у вас есть еще много перестановок, чем вы начали. Возьмите верхние x, выполнив и повторите. Это обеспечит некоторые локально-максимальные алгоритмы, но я не знаю, приведет ли это к алгоритму (-ам) с глобальным максимумом.