Содержание
- 2. Вступление В 1859 г. Сэр Вильям Гамильтон, знаменитый математик, давший миру теорию комплексного числа и кватерниона,
- 3. Рассмотрим задачу о коммивояжере. Имеются n городов, расстояния (стоимость проезда, расход горючего на дорогу и т.д.)
- 4. Опишем алгоритм Литтла для нахождения минимального гамильтонова контура для графа с n вершинами. Граф представляют в
- 5. 5. Выбираем дугу , для которой степень нулевого элемента достигает максимального значения 6. Разбиваем множество всех
- 6. Процесс разбиения множеств на подмножества сопровождается построением дерева ветвлений. 11. Если в результате ветвлений получаем матрицу
- 7. условия (2) - (4) в совокупности обеспечивают, что каждая переменная равна или нулю, или единице. При
- 8. Табл.1
- 9. 1) Справа к таблице присоединяем столбец Ui, в котором записываем минимальные элементы соответствующих строк. Вычитаем элементы
- 10. 2) Внизу полученной матрицы присоединяем строку Vj, в которой записываем минимальные элементы столбцов. Вычитаем элементы Vj
- 11. 3) В результате вычислений получаем матрицу, приведенную по строкам и столбцам, которая изображена в виде таблицы
- 12. 4) Находим константу приведения Таким образом, нижней границей множества всех гамильтоновых контуров будет число 5) Находим
- 14. 8) Матрицу гамильтоновых контуров получим из таблицы 2 путем замены элемента (1;5) на знак «?».
- 15. 9) Делаем дополнительное приведение матрицы контуров : = 0. Нижняя граница множества равна . 10) Находим
- 17. 12) Узнаем степени нулей матрицы. Претендентами на включение в гамильтонов контур будут несколько дуг (5;2) и
- 18. Табл.4
- 19. Определим константы приведения для этих матриц , Следовательно , Так как , то дальнейшему ветвлению подлежит
- 20. Претендентом к включению в гамильтонов контур станет дуга (3;2). Разбиваем множество на два и .
- 21. Очевидно , Следовательно, очередному ветвлению нужно подвергнуть подмножество . Переходим к ветвлению подмножества . Определяем степени
- 23. Скачать презентацию