armpomor / simulated_annealing Goto Github PK

Simulated_annealing - Алгоритм метод отжига.

Дан взвешенный, неориентированный, полный граф. Задача - найти кратчайший гамильтонов цикл, т.е. решить задачу коммивояжера. Для отображения графиков необходима Plotly v.2.12.1

1. Генерируем евклидов граф в networkx.
2. Берем список вершин перемешанный случайным образом, но так чтобы он начинался и заканчивался одной той же вершиной, т.е. был замкнутым или иначе говоря циклом. S1. Это первый random.
3. По S1 прокладываем маршрут.
4. Random выбираются два индекса S1, не включая индексы 0 и -1. И инвертируем список, начиная с меньшего индекса и заканчивая большим. Таким образом мы изменяем только два ребра в маршруте. Это второй random.
5. Получается новый вариант списка вершин. S2
6. Вычисляем длины S1 и S2. L1 и L2.
7. Если L2 < L1, то для следующей итерации выбираем маршрут S2.
8. Если L2 > L1, то вычисляем вероятность принятия маршрута с длиной L2. P = 100 * e ** (-(L2 - L1) / T), где Т - это температура, которая снижается на каждой итерации T_2 = ALPHA * T_1, где ALPHA - это коэффициент остывания системы, число меньше единицы.
9. Random выбираем число в пределах от 1 до 100, P_r. Это третий random.
10. Если P > P-r, то для следующей итерации выбираем маршрут S2, если меньше, S1
11. Начинается новая итерация с пункта 4.
12. Если все время выбирать лучший маршрут, то получается "жадный" алгоритм.