Задача коммивояжера
Категория реферата: Рефераты по экономике
Теги реферата: конспект по русскому, титульный лист реферата
Добавил(а) на сайт: Jarkin.
Предыдущая страница реферата | 19 20 21 22 23 24 25 26 27 28 29 | Следующая страница реферата
Рефераты | Рефераты по экономике | Задача коммивояжера |
14 |
11 |
6 |
6 |
5 |
9 |
||
|
табл. 13 |
Одним из возможных недостатков такого
алгоритма является необходимость знать не матрицу расстояний, а координаты
каждого города на плоскости. Если нам известна матрица расстояний между
городами, но неизвестны их координаты, то для их нахождения нужно будет решить n систем квадратных уравнений с n неизвестными для каждой координаты. Уже
для 6 городов это сделать очень сложно. Если же, наоборот, имеются координаты
всех городов, но нет матрицы расстояний между ними, то создать эту матрицу
несложно. Это можно легко сделать в уме для 5-6 городов. Для большего
количества городов можно воспользоваться возможностями компьютера, в то время
как промоделировать решение системы квадратных уравнений на компьютере довольно
сложно.
На основе вышеизложенного можно сделать вывод, что мой алгоритм, наряду с деревянным алгоритмом и алгоритмом Дейкстры, можно отнести к приближённым (хотя за этим алгоритмом ни разу не было замечено выдачи неправильного варианта).
1.2.6. Анализ методов решения задачи коммивояжера
Для подведения итогов в изучении методов решения ЗК протестируем наиболее оптимальные алгоритмы на компьютере по следующим показателям: количество городов, время обработки, вероятность неправильного ответа. Данные занесём в таблицу.
|
Алгоритм лексического перебора |
||||||
|
Кол-во городов |
Время обработки, c |
Вероятность неправильного ответа, % |
Тип алгоритма |
|||
|
10 |
41 |
0 |
точный |
|||
|
12 |
12000=3ч.20мин |
0 |
||||
|
32 |
-* |
0 |
||||
|
100 |
-* |
0 |
||||
|
Метод ветвей и границ |
||||||
|
10 |
~0 |
0 |
точный |
|||
|
32 |
~0.0001 |
0 |
||||
|
100 |
1.2 |
0 |
||||
|
Мой алгоритм решения ЗК |
||||||
|
10 |
0.001 |
0 |
приближенный |
|||
|
32 |
2.5 |
0 |
||||
|
100 |
6 |
0 Рекомендуем скачать другие рефераты по теме: изложение по русскому 6 класс, деньги реферат. Предыдущая страница реферата | 19 20 21 22 23 24 25 26 27 28 29 | Следующая страница реферата Поделитесь этой записью или добавьте в закладкиКатегории: |