Отступление Экспериментальное исследование эффективности алгоритмов

Задача коммивояжера
Построение и анализ алгоритмов
Лекция 2




Отступление
Экспериментальное исследование

эффективности алгоритмов

по какому ансамблю?
Повторяющиеся элементы? - зависит от задания…
Тип,

диапазон (например, 1..n)?
“n!” ? (см.далее)
Что измерять?
Число операций, время.
Как измерять? (при малых и больших значениях n), (см.код Бентли, в папке «программа»/ tm1.cpp)
Контроль правильности результата… (отличие выборочных тестов от массовой генерации)

следующую индукционную схему:
на i-ом шаге первые i элементов составляют

равновероятную (среди всех i!) случайную перестановку:
База. Один элемент является единственной случайной перестановкой из одного элемента.
Предположение. Предположим, что на (i − 1)-ом шаге первые (i − 1) элементов составляют равновероятную случайную перестановку.
Переход. Перейдем от (i − 1)-го шага к i-му: возьмем случайный индекс от 1 до i, поставим i-ый элемент на место этого индекса, а тот элемент, который стоял по этому индексу до операции, поставим на место номер i.
Очевидно, что таким образом можно получить всевозможные перестановки первых i элементов и при этом они будут равновероятны.

@param randseed Зерно случайного генератора
*/
void shuffle( intrandseed ) {
sedge t;

int rind;
int i;
/* инициализация генератора случайных чисел: */
srand( randseed );

for(i=0; i rind = (i==0) ? 0 : rand()%i;
t = e[i]; e[i] = e[rind]; e[rind] = t;
}
}

Algorithms»
в файле «experguide.pdf».


Есть также
«ACM Journal on Experimental Algorithmics».

(Algorithms. Data Structures . Experiments. Analysis)
http://www.jea.acm.org/