Использование решателя коммивояжера для решения гамильтонова пути
По умолчанию чувствительность к регистру отключена:
PS> 'test','TEST','TeSt','notest' | ? { $_ -like 'test' }
test
TEST
TeSt
Из документации:
По умолчанию все операторы сравнения не чувствительны к регистру. Чтобы сделать оператор сравнения чувствительным к регистру, перед именем оператора поставьте
"c". Например, чувствительная к регистру"-eq"является"-ceq". Чтобы сделать нечувствительность к регистру в явном виде, перед оператором ставится символ"i". Для например, явно версия"-eq", не чувствительная к регистру, имеет вид"-ieq".
Для получения дополнительной информации запустите help about_comparison_operators
2 ответа
Не знаю, получил ли ты когда-нибудь ответ на этот вопрос. Простой трюк состоит в том, чтобы добавить одну фиктивную точку, которая имеет расстояние в ноль ко всем остальным вашим точкам. Решите TSP и избавьтесь от манекена - осталось только гамильтонский путь. Просто!
Обе задачи являются комплексными NP, поэтому по определению вы можете преобразовать ввод и использовать один и тот же алгоритм; -)
Но основная идея должна работать. Конечно, вам может потребоваться изменить создание новых путей и критерии успеха.
EDIT: Кстати: Есть предложение для рандомизированного алгоритма: http://en.wikipedia.org/wiki/Hamiltonian_path_problem