Łączenie lini

0

Mój problem jest dość podobny do znanego problemu komiwojażera, nie ma jednak podanych wszystkich tras pomiędzy punktami. Algorytm powinien mieć możliwość tworzenia swoich połączeń.

Problem:
Są line, punkty i okręgi, należy połączyć je jedną łamaną (końce liń, środki okręgów i punkty) aby długość tej łamanej była jak najmniejsza, i aby przejść po danej lini (przez dane punkty) tylko raz. Jest możliwość tworzenia lini których nie ma, ale należy przejść po liniach które są.

Mam nadzieje że dobrze zdefiniowałem problem. Może da się go sprowadzić do znanego (komiwojażera?)
Jakieś propozycje?

0

Jakie znaczenie mają okręgi? Z Twojego opisu wynika, że ważny jest tylko środek okręgu czyli punkt.

0

Masz racje. Nie ma to znaczenia czy jest to okrąg czy punkt

0

Jeszcze pytanie uściślające. Po dodanych odcinkach można chodzić wielokrotnie?

0

Po dodanych odcinkach można, po istniejących nie.

0

Na razie udało mi się to zrealizować algorytmem zachłannym. Nie udało się natomiast ciągle sprowadzić do problemu komiwojazera nawet bez zdefiniowanego grafu.

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0