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
	» Killer 03:00 » Martens 02:57 » PiotrexP 02:50 » AdiQ 01:49 » Zibi 01:46 » elliot_pl 01:42 » Zbyszek.J 01:40 » cVas 01:15 » piszczyk 01:00 » GULIwer 00:52 » Visar 00:40 » Marek1981 00:37 » hideox 00:37 » doxent 00:18 » luckyluc 00:14 » ReeX 00:10 » Magnus 00:08 » Brauni 00:05 » Raist 23:50 » rooter666 23:34 Dzisiaj przeczytano 7392 postów, wczoraj 40396 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