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ą".)

do góry

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/

do góry

M.M. <m...@N...gazeta.pl> napisał(a):

> Ł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?
Ehhh miały być y^x. Sory.



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

do góry

Dnia Mon, 09 Jul 2012 16:34:16 +0200, slawek napisal:

> 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ą".)

Zacznij od tych niepasujących bolców, trywialna eliminacja od góry. Potem
z górki, a właściwie z dołu.

Edek

do góry

Użytkownik "Edek Pienkowski" napisał w wiadomości grup
dyskusyjnych:jtfo0f$qka$...@m...internetia.pl...

>Zacznij od tych niepasujących bolców, trywialna eliminacja od góry. Potem
>z górki, a właściwie z dołu.

Ok, więc trzeba zmodyfikować - bolców jest N+M, natomiast dziurek jest 3N w
N bloczkach. I dodatkowo rozwiązanie ma być optymalne w sensie Pareto - tzn.
że każde inne rozmieszczenie bolców: 1. albo daje mniejszą ogólną liczbę
bloczków z bolcami w środku; 2. albo daje większy maksymalny luz w bolca w
dziurce (w sześciennym bloczku) dla wszystkich zabolcowanych. Dodatkowo M
może być ujemne. Ufff... A i fajne jest to, że można zamiast maksymalnym
luzem posłużyć się np. średniokwadratowym, medianą...

(Możliwych wybolcowań może być, dla M > 0, IMHO, 3*(M+N)!/M!, czyli przy N
= 100 i M = 100, przy 100% zabolcowaniu, będzie to 8.45E216 . Nieźle, brute
force nie da rady.)

I tak, masz rację, /prawie/ trywialna eliminacja - bo idąc od najgorszych
tworzysz najgorsze połączenia - choć być może są lepsze (w sensie
minimalizacji maksymalnego luzu).
Ogólnie? Chodziło i chodzi mi o wymyślenie problemu, który będzie dość
trudny, ale zarazem możliwe powinno być szukanie /jakiś/ rozwiązań. Choćby
metodą MC.

Zresztą można zmienić kontekst: np. masz M mężczyzn i K kobiet, dla każdego
osobnika określamy przy pomocy SQUID atrakcyjność pozostałych M+K-1. Jak
dobrać pary tak, aby osobniki w parach były możliwie atrakcyjne dla siebie?
Zakładamy że wynik pomiaru to liczba rzeczywista od 0 do 1.0 i że musi ona
wynosić przynajmniej dzeta dla udanego związku (dla obojga). Jak obliczyć
funkcję P(dzeta), czyli zależność maksymalnej liczby udanych związków w
zależności od poziomu oczekiwań?! (No jakoś to w Real World działa,
czasami..., takie rzeczy badał prof. Nęcka swego czasu, no ale nie miał
SQUID.) To się chyba da rozciągnąć ogólniej na dopasowanie czegoś do
czegoś... jest jakaś tego teoria?! (Cząsteczki chemiczne, ludzie, części
maszyn, towary i producenci, usługi i klienci, użytkownicy i serwery...
ojej, to chyba się zrobił POWAŻNY PROBLEM, łał!)

do góry

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

> Możliwych wybolcowań może być, dla M > 0, IMHO, 3*(M+N)!/M!, czyli przy N
> = 100 i M = 100, przy 100% zabolcowaniu, będzie to 8.45E216 . Nieźle, brute
> force nie da rady.)
Zastanawia mnie jak wyszło 3*(M+N)!/M!.
Bolców jest (M+M). Wybieramy z nich N - liczy się kolejność wybierania.
Czyli mamy (M+N) * (M+N-1) * (M+N-2) * ... (M+1), czyli (N+M)!/M!.
Klocki są zawsze w tej samej kolejności, więc dla pierwszego klocka będzie
pierwszy wybrany bolec, dla drugiego drugi, itd. Zakładamy że dziury w
klockach nie są stożkowe, więc obojętne jest czy bolec wkładamy od przodu czy
od tyłu. A wiec każdy klocek można ułożyć w trzech stanach. Oznacza to że
mamy liczbę liczbę N cyfrową przy podstawie 3, co daje 3^N ułożeń klocków.
Moim zdaniem wybolcowań jest 3^N * (M+N)!/M!. De facto wybolcowanie jednego
klocka po przypisaniu na stałe bolca do klocka nie wpływa na wybolcowanie
drugiego, a więc optymalne wybolcowanie wszystkich jest sumą optymalnych
wybolcowań pojedynczych (powtarzam, po zafiksowaniu par bolec-klocek). Z
uwzględnieniem powyższego mamy 3*N * (M+N)!/M!.
Pozdrawiam


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

do góry

Użytkownik " M.M." <m...@N...gazeta.pl> napisał:

>> Możliwych wybolcowań może być, dla M > 0, IMHO, 3*(M+N)!/M!, czyli przy N
>> = 100 i M = 100, przy 100% zabolcowaniu, będzie to 8.45E216 .
>> Nieźle, brute force nie da rady.)

Wiem ze to kawal z broda dluzsza od mojego brzucha, ale jak nic
jako "best solution" pasuje tu PRLowski dowcip o kursie dla milicjantow ;)

AK

do góry

Użytkownik " M.M." napisał w wiadomości grup
dyskusyjnych:jtjuk8$gki$...@i...gazeta.pl...

>Moim zdaniem wybolcowań jest 3^N * (M+N)!/M!. De facto wybolcowanie jednego

Masz rację - ale to jest więcej niż 3*(M+N)!/M! - czyli ja też mam rację ;)
(Chodzi o liczbę możliwych połączeń dziurka-bolec, a nie ile z nich ma
sens.)

>klocka po przypisaniu na stałe bolca do klocka nie wpływa na wybolcowanie
>drugiego, a więc optymalne wybolcowanie wszystkich jest sumą optymalnych
>wybolcowań pojedynczych (powtarzam, po zafiksowaniu par bolec-klocek). Z

To zadanie zaczyna mi się coraz bardziej podobać!

do góry

Użytkownik "AK" napisał w wiadomości grup
dyskusyjnych:jtjv5q$ahp$...@i...gazeta.pl...

>Wiem ze to kawal z broda dluzsza od mojego brzucha, ale jak nic
>jako "best solution" pasuje tu PRLowski dowcip o kursie dla milicjantow ;)

Sorry, ale dowcipy był "ludzkie" - a że ludzie akurat byli wlogowani w PRL
to już nie ich wina - taki był OS.

Cóż, nie jest źle: Dasgupta et al. opisują, ISBN 978-83-01-16278-8, pp. 252,
co Cela i Czesiek robią z Bocianem (3D matching jako rozwinięcie bipartite
matching).

do góry