[Java][Wątki] Komiwojażer

witam,
mam do zrobienia na uczelnie (systemy równoległe) program rozwiązujący problem komiwojażera wykorzystujący wątki. W wersji jednowątkowej sprawę załatwiałem przez rekurencję rozwijając drzewa permutacji (przeglądem zupełnym) oraz wykorzystując branch&bound odcinając dane gałęzie, które nie miały szans uzyskac lepszego wyniku.

1)Czy ma sens kod, tworzący wątki rekurencyjnie? Powstanie wtedy sporo wątków, obawiam się o koszt tworzenia wątków.

2)Wymyśliłem jeszcze drugie podejście do tego - utworzenie kilku wątków, i dynamiczne przydzielanie im roboty takie, że: każdy wątek ma przydzielone miasto początkowe, i rozwija rekurencyjnie dalej swoje drzewo(jak w wersji jednowątkowej), a gdy skończy pracę pobiera następne ewentualne miasto początkowe itd.

Jaka jest optymalna ilość wątków? Czy powinno to być parę, czy można sobie pozwolić na dużą większą ilość?

W JDK 5 masz Executory, np java.util.concurrent.executors.newFixedThreadPool , http://download.oracle.com/javase/tutorial/essential/concurrency/pools.html

W JDK 7 będzie Fork/Join Pool: http://download.oracle.com/javase/tutorial/essential/concurrency/forkjoin.html , który myślę, że znacznie uprościł by ci zadanie.

Stworzenie nowego Runnable jest bardzo tanie, wysłanie go do Executora ze stałą pulą wątków raczej też jest tanie.