slawek <h...@s...pl> napisał(a):


> Gdy myślałem o jakichś /łatwych/ problemikach, żeby nie zapętlać się na
> hetmanach itp. "standardach"... coś takiego przyszło mi do głowy:
>
> Mamy N cylindrycznych bolców (trzpieni?), które powinny pasować do N
> otworów, każdy otwór jest wywiercony w jednej z N sześciennych kostek. Bolce
> nie pasują jednak dokładnie i trzeba dobrać możliwie najlepiej pary
> (bolec,kostka). Ok, algorytm jest trywialny - posortować średnice bolców,
> posortować średnice otworów, ... nuda.
>
> Ale teraz wprowadzamy małą modyfikację - otworów jest 3N, tzn. w każdej
> kostce są trzy. Nadal jednak trzeba znaleźć najlepsze pary (bolec, kostka),
> choć tym razem 2 otwory w kostce będą nieużyte. (Można sobie wyobrazić, że
> otwory w kostce są nawiercone wzdłuż osi x,y,z, a bolec np. mocuje kostkę do
> ściany.)
>
> Uwaga: w obu przypadkach możliwe jest że będą bolce nie pasujące do
> jakiejkolwiek kostki (jeżeli różnica pomiędzy średnicą otworu i średnicą
> bolca nie spełnia warunku b > (D-d) > a ).
>
> Nie potrzebuję rozwiązania tego zadania (choć jeżeli ktoś chce?), lecz
> raczej czy to zadanie jest - według was - łatwe, czy też dość trudne?
>
> (Nota bene, swego czasu przebojem był program parujący tranzystory
> komplementarne na podstawie ich charakterystyk połączony przez kartę AD/DA
> do PC. Ale to problem "z jedną dziurką".)

Wygląda jak zadanie optymalizacyjne, choć nie doszukałem się funkcji
celu. Napiszę jak to zrozumiałem.

Mamy dwa główne zbiory. Jeden zbiór A drugi to B. Zbiory zawierają
po prostu elementy a_1, a_2, a_3 a_n; b_1, b_2, b_3, b_m. Poza dwoma
zbiorami głównymi mamy tyle zbiorów pobocznych P_1, P_2, P_3 P_N ile
jest elementów w zbiorze A. Każdemu elementowi a_j ze zbioru A jest
przyporządkowany dokładnie jeden zbiór poboczny P_j. Element b_i ze
zbioru B poprawnie pasuje do elementu a_j ze zbioru A wtedy i tylko wtedy gdy
b_i znajduje się w zbiorze pobocznym P_j. Należy znaleźć takie
przyporządkowanie elementów b_i ze zbioru B do elementów a_j ze zbioru A aby:
a) do elementu a_j pasował poprawnie co najwyżej jeden element b_i
b) element b_i pasował poprawnie co najwyżej do jednego elementu a_j
c) elementów a_j do których nie pasuje żaden element b_i było jak najmniej,
czyli pozostało możliwie mało elementów a_j nieprzymocowanych do ściany
przy pomocy elementu b_i.

Łatwo podać procedurę siłową, która będzie miała złożoność mniej/więcej
x^y, gdzie x to ilość elementów a_i, a y to średnia ilość pasujących
elementów b_i do elementu a_i. A czy istnieje lepsza dla każdych danych?

Ponadto problem można skomplikować: każdy element a_j może mieć inną wagę
(inną karę) za to że do niego nie został dopasowany żaden element b_i.

Pozdrawiam


--
Wysłano z serwisu Usenet w portalu Gazeta.pl -> http://www.gazeta.pl/usenet/