Aşağıdaki sorunu çözmek için daha iyi bir algoritma bulmak istiyorum:

VardırNpuan (mor) başlangıç veN2D hedef noktaları (yeşil). Tüm parçaların toplam uzunluğu en aza indirirken, bir çizgi parçasının puan (kahverengi) bu kesimleri kesişen (kırmızı) ve hedef için bir başlangıç noktası bağlanan bir algoritma istiyorum.

C benim ilk çaba tüm olası durumlar permuting, kavşak-ücretsiz Birleşik Devletleri bulmak ve minimum toplam segment uzunluğu ile devlet arasında yer aldıO(n!). Ama orada daha iyi bir yolu olmalı düşünüyorum.

Herhangi bir fikir? Veya arama için iyi bir anahtar kelime?

Bu Minimum Euclidean Matching in 2D. Link bu sorun hakkında bilinen bir bibliyografya içerir. Toplam uzunluğu en aza indirmek için istediğiniz belirli olmayan kavşak kısıtlaması çapraz kesimleri, çift uzunluğu onları uncrossing azaltılabilir gibi gereksiz.