|
TwojePC.pl © 2001 - 2024
|
 |
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
|
|
|
|
 |
All rights reserved ® Copyright and Design 2001-2024, TwojePC.PL |
 |
|
|
|
