Каков наилучший способ реализации карты для решения проблемы коммивояжера (тура) в рубине с примерно 25 городами? Лучше всего использовать график и добавить каждое расстояние в каждый город как вершину? Или у рубина есть лучший способ для этого?Лучший способ реализации карты для TSP
Это хорошо пройденная территория. :)
«Маршрут для коммивояжера (# 142) - Мортон Голдберг
Торговец хочет призвать своих клиентов, каждый из которых находится в другом городе, он просит вас подготовить маршрут. для него, что позволит свести к минимуму его мили вождения. Маршрут должен взять его в каждый город ровно один раз и вернуть его к отправной точке. Можете ли вы написать программу Ruby для создания такого маршрута?
Эта проблема известна и известна тем, быть полным NP. Итак, как вас можно ожидать, чтобы решить его в качестве проекта Ruby Quiz в выходные дни? Это необоснованно, не так ли? Да, это так, если условия не смягчены ».
Смотрите полную страницу, плюс несколько решений в боковой панели на rubyquiz
Вы действительно должны иметь немного попробовать себя, чтобы помочь сузить объем помощи вам нужно. Ответ прямо сейчас «это зависит», потому что есть важные детали, которые вы также должны добавить к вопросу: 1) Какова метрика расстояния (более простые показатели, такие как прямые линии между точками и/или 'dist (A, B) == dist (B, A) 'поддаются более простым представлениям)? 2) У вас есть конкретный решатель, который вы хотите реализовать (некоторые решатели предпочитают представления)? Любой из них может быть легко увидеть в примере кода. –