Кратчайший путь с использованием имитации отжига с использованием приложения Android

Question

Я реализую приложение android, используя разные географические c координаты, и мне нужно решить проблему, аналогичную путешествующему продавцу.

Я нашел реализацию алгоритма в http://www.theprojectspot.com/tutorial-post/simulated-annealing-algorithm-for-beginners/6.

Я настроил код так, как мне нужно, и он дает теоретически оптимальные результаты. Однако я заметил, что каждое выполнение приводит к различному типу результата.

Я вернулся к исходному коду и обнаружил, что даже в оригинале есть разногласия относительно результатов.

Не понимаю. Разве результат не должен быть уникальным? В конце концов, мы ищем наименьший путь ... возможно, небольшую вариацию, но каждое выполнение отличается на несколько единиц от предыдущего выполнения.

Как я могу настроить алгоритм для получения одинакового результата во всех прогонах ? Кто-нибудь работал с этим?

Answer 1

Это цена, которую вы платите за алгоритм, подобный этому: полученные результаты вполне могут каждый раз отличаться. Алгоритм не «находит кратчайший путь», что является вычислительно неразрешимой проблемой («коммивояжер»). Вместо этого он пытается быстро найти решение, которое "достаточно короткое". Будет ли это на самом деле так, во многом зависит от данных ... и, в нетривиальной степени, от случайного случая.

И, поскольку алгоритм является сравнительно быстрым, иногда вы запускаете его несколько раз подряд, чтобы оценить изменчивость полученных решений. Если (скажем) три прогона в каждом случае дают результаты, которые «достаточно близки» друг к другу, есть хороший шанс, что результат будет надежным. Но если стандартное отклонение очень велико, алгоритм может не дать вам хорошего ответа. (Имейте в виду, что иногда решение будет неправильным.)

Так сказать: «вы получаете то, за что платите, но вы за это не платите много, и, конечно, вот в чем дело. "