Leten kamp

Moze pomos okolu ovaa zadaca?
Blagodaram odnapred,

This message was edited 1 time. Last update was at 16/01/2017 14:58:15

divio wrote:Moze pomos okolu ovaa zadaca?
Blagodaram odnapred,

Ако добро ја сфатив задачата, постојат само K (до 15) важни градови кои ни се од интерес да ги посетиме. На почеток, можеме да го искористиме алгоритамот за пронаоѓање на најкраток пат во граф од Dijkstra, и од секој од овие K градови, да го најдеме растојанието до сите останати K важни градови. Сега, добиваме нов граф кој што има само 15 темиња, бидејќи воопшто не не интересира кои други градови ги посетуваме кога патуваме, само не интересира растојанието, а тоа веќе го имаме пресметано за секој од важните градови (до секој друг).

Остатокот од решението е со динамичко програмирање.