Algorytm - minimalne ścieżki połączeń dla zbioru punktów

	B O A R D
	» Board » Zadaj pytanie » Archiwum » Szukaj » Stylizacja

M E N U

» Nowości

» Archiwum

» Recenzje / Testy

» Board

» Rejestracja

Szukaj @ TwojePC

	OBECNI NA TPC
	» rainy 02:22 » Killer 01:42 » Banan 01:42 » Martens 01:39 » Lucyferiu 01:13 » MARC 00:57 » Zic 00:53 » Visar 00:52 » g5mark 00:44 » piszczyk 00:41 » metacom 00:30 » Tomasz 00:25 » kojot 00:24 » GLI 00:15 » DJopek 00:10 » Lukas12p 23:50 » Emios 23:41 » 3kawki 23:37 » dugi 23:13 » Curro 23:10 Dzisiaj przeczytano 2721 postów, wczoraj 30591 Szybkie ładowanie jest: włączone.

ccc

A R C H I W A L N A W I A D O M O Ś Ć

Algorytm - minimalne ścieżki połączeń dla zbioru punktów , Rhobaak 19/03/05 20:14
Mam taki problem algorytmiczny do rozwiązania: na siatce o wymiarach AxB rozmieszczone są dwa rodzaje punktów. Należy połączyć punkty tego samego rodzaju za pomoca odcinków złożonych z linii poziomych lub pionowych (odcinki mają tworzyć drzewo spójności dla danego zbioru punktów). Cały problem polega na tym, że odcinki tworzące połączenia dla pierwszego rodzaju punktów nie moga przecinać się z odcinkami drugiego rodzaju... Ma to być coś takiego:
____1____2
__1oooo1_x
2____o___x
x_1oo1_xxx
x______2__
x2xxxxxx2_

Gdzie '1' i '2' to punkty do łączenia a 'o' i 'x' to połączenia między nimi.

Gdyby zbiór punktów był tylko jeden, to zadanie byłoby proste, ale tak - bardzo się komplikuje. Byłbym wdzięczny za jakąkolwiek pomoc, wskazanie algorytmu lub jakiś link, bo męczę sie już z tym długo i stoję w miejscu. Na myśl przychodzi skojarzenie z problemem komiwojażera i zastosowanie algorytmu heurystycznego dla każdego ze zbiorów punktów, ale pozostaje problem nieprzecinania się drzew...

Kor2dual3,2hZ overkloc,4Gbit Ram
G-forc 460 gietex,barakudy
Children of Neostrada Association MVP