plz pomoć!

[Ramone]

Hi there!Radim na nekim robotika i ja koristiti Traveling Salesman Problem napraviti neke staze.U trenutku sam težak to model ovu igru:
prodavač počinje od grada (recimo 1) i ima n gradovima na putovanje, ali on ima samo jedinice T vrijeme.Pretpostavljajući da je svaki putovanje između 2 grada je jedan jedinici vremena onda koji je najbolji put da se?

To znači da imam to preformulirati na neki način problem.Ja sam mislio na rješenje, ali kako mogu gurrante ako je to optimalno ili ne?Što matematike za upotrebu?

 

[mat]

TSP problem je dobro poznat NP-hard problem.Dok optimalan put se može naći u razumnom roku za male N, to dokazuje i teško za velikim N, gdje se fokusira na traženje suboptimalno stazama.

Wikipedia ima popis mogućih algoritama.
http://en.wikipedia.org/wiki/Traveling_salesman_problem
Last edited by mat on 16 kolovoz 2005 19:00, edited 1 time in total

 

[Ramone]

Pokušajte ponovno čitajući moj post - shvatit ćete što ja želim.Ako želite testirati heuristička (P vremena) za NP problem, prvo se morate pronaći točno rješenje za optimalnu problem.Budući da ono što želim počinje od TSP, ali to nije TSP ja prvo mora znati je li moj formulacija je OPTIMALNE ili ne (na taj način pronaći drugi).

 

[yjkwon57]

Bok.

Ova tema pripada posebne vrste matematike, pod nazivom Graph Theory.