Я был в библиотеке в закрытой секции и прочитал что-то довольно странное о редком отрывке из теории графов. Называется, насколько я понимаю, Цветком. По крайней мере, я чувствовал себя Томом Риддлом, когда случайно познакомился с алгоритмом цветения Эдмонда во время участия в «TPS 2018 Prime Paths kaggle Competition. Соперничали со мной и в конечном итоге заняли первое место Келд Хелсгаун и Уильям Кук, написавшие книги о TSP. Кук написал В погоне за коммивояжером, а Хельсгаун много опубликовал и внедрил быстрый решатель LKH (http://akira.ruc.dk/~keld/research/LKH/). TSP преподавали в бакалавриате, а затем в магистратуре, но только в отношении теории сложности, а не в богатой истории поиска оптимизаций для этой сложной NP-задачи.
Презентация Кука знакомит с алгоритмом цветения Эдмондса для максимального соответствия, который был применен к TSP в 1960-х годах. Такой важный алгоритм комбинаторной оптимизации не будет упоминаться на большинстве уроков информатики. Материала по этому поводу в сети предостаточно — я бы порекомендовал эти лекции Шашанка К. Мехты (здесь и здесь). Или, если вы предпочитаете борьбу, Дороги, деревья и цветы Эдмондса.
Я не очень хорошо занял место в таблице лидеров Kaggle, но 2-е место имеет отличную рецензию: https://www.kaggle.com/c/traveling-santa-2018-prime-paths/discussion.
