Графики и СетиSalesman

До сих пор мы игнорировали тот факт, что некоторые города могут быть дальше друг от друга, чем другие. В реальной жизни, однако, это очень важное соображение: мы не просто хотим найти какой-либо путь, мы хотим найти кратчайший путь. Это называется проблемой коммивояжера . Это должно быть решено не только в сфере транспорта и логистики, но и при размещении транзисторов на микрочипах, для создания более быстрых компьютеров или при анализе структуры ДНК .

Один простой метод - это попробовать все возможные пути, найти длину каждого, а затем выбрать самый короткий. Однако мы только что показали, что даже с ${tsn2} города есть ${tsn2} ! знак равно ${factorial(tsn2)} возможные пути. Если у вас есть сотни или тысячи вершин, пробовать все возможные пути становится невозможно, даже используя мощные компьютеры.