Одним из возможных недостатков такого
алгоритма является необходимость знать не матрицу расстояний, а координаты
каждого города на плоскости. Если нам известна матрица расстояний между
городами, но неизвестны их координаты, то для их нахождения нужно будет решить 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 | Следующая страница реферата
|
|
Главная