Хоббит, туда и обратно.
Меня пугает, что студенты сначала гуглят, потом думают.
Решаем задачу коммивояжёра (пройти по всем городам и посетить каждый ровно один раз) алгоритмом Литла. Алгоритму плохо, если в графе есть петли. Если петлю находим, то говорим, что петлю не делаем, ребро выбрасываем, ок.
Но как проверить, получилась петля или нет? Фигня вопрос! Гуглим! Находим, что надо применить поиск в глубину, на прохождении туда красить серым, обратно - черным. Если наткнулись на следующую в пути вершину серую, то цикл есть.
Наступили на грабли:
1) решение должно быть циклом, а мы его выкидывали. (Это нормальный баг, починили).
2) у нас же новое ребро очередное в частичном решении? Возьми его и пойди по цепочке взятых ребер. Если дошли исходного, то цикл. O(n). Если длина цикла = количеству городов, то исходное решение. Но нет, мы будем циклом по всем вершинам пытаться запускать поиск в глубину...
Решаем задачу коммивояжёра (пройти по всем городам и посетить каждый ровно один раз) алгоритмом Литла. Алгоритму плохо, если в графе есть петли. Если петлю находим, то говорим, что петлю не делаем, ребро выбрасываем, ок.
Но как проверить, получилась петля или нет? Фигня вопрос! Гуглим! Находим, что надо применить поиск в глубину, на прохождении туда красить серым, обратно - черным. Если наткнулись на следующую в пути вершину серую, то цикл есть.
Наступили на грабли:
1) решение должно быть циклом, а мы его выкидывали. (Это нормальный баг, починили).
2) у нас же новое ребро очередное в частичном решении? Возьми его и пойди по цепочке взятых ребер. Если дошли исходного, то цикл. O(n). Если длина цикла = количеству городов, то исходное решение. Но нет, мы будем циклом по всем вершинам пытаться запускать поиск в глубину...