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
	» wrrr 22:29 » bajbusek 22:28 » rooter666 22:27 » Soulburne 22:18 » fiskomp 22:17 » akslow 22:14 » alien1 22:13 » biEski 22:10 » metacom 22:02 » m&m 22:00 » Dhoine 21:58 » zeb 21:58 » dida 21:56 » bodeq 21:56 » rainy 21:55 » cVas 21:46 » piszczyk 21:34 » Marian30p 21:33 » Kool@ 21:30 » DYD 21:22 Dzisiaj przeczytano 20457 postów, wczoraj 27057 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