Witam ;)
Przypuśćmy, że mam listę pewnych odcinków i chciałbym je połączyć w różnej kolejności, tak aby otrzymać łamaną zamkniętą - załóżmy także, że istnieje tylko jedna taka kombinacja oraz każdy odcinek może być wykorzystany tylko raz.
Istnieje jakaś metoda rozwiązania tego, oprócz czystego brute force?
Btw, to nie jest chyba żaden konkretny problem - wpadło mi takie coś na myśl w nocy i zacząłem się zastanawiać :P
0
0
Kiedyś to bardzo długo analizowałem, udowodniłem że sprowadza się to do komiwojażera.
Zrobiłem nawet całkiem ładny algorytm przybliżony który daje bardzo dobre wyniki (w czasie O(N2) ) lecz nie mogę ani znaleźć przypadku który udowadnia że nie znajduje on rozwiązania optymalnego ani też udowodnić że znajduję optymalne rozwiązanie.
0
udowodniłem że sprowadza się to do komiwojażera.
w czasie O(N2)
nagroda Turinga i miliony czekają ;)
3
Wiem o tym, tylko że nie widzę jak ugryźć dowód.