Informatyka UJ forum

SZCZUR

mam takie zadanie:

firma produkuje urządzenia o "n" parametrach (np. kolor, wielkość...), ma ich wyprodukować "m" (każde urządzenie może mieć inaczej ustawione parametry).

problem jest taki ze przestawienie parametru w linii produkcyjnej kosztuje mamy podaną tabelkę "k[n]" z informacja o kosztach przestawienia każdego z parametrów.

jak to posortować żeby koszt tych przestawień był minimalny..

---------

od razu mówię ze posortowanie po najdroższych parametrach..a potem mniejszych nie zadziała bo:

..1..|..2..|..3..|..4.. - numer obiektu
----------------------
..0..|..0..|..1..|..1.. - param 0
..a..|..b..|..a..|..b.. - param 1

wystarczy zamienić obiekt 3 z 4 żeby otrzymać lepsza konfiguracje.

----------

jak ktoś zarzuci pomysłem lub chociażby linkiem do podobnego problemu będę wdzięczny.

Robson

A jak wielkich danych sie spodziewasz? I jaki jest oczekiwany czas liczenia?...

SZCZUR

ilosc parametrów to ok 5-10 ("n")
ilosc obiektów 10000-100000 ("m")

algorytm nie moze byc wolniejszy niz n*mlog(m), może podawać czasem błędne wyniki ale nie gorsze niz +10% do kosztów.

edit:

jeśli znasz sie na grafice, to jest mi to potrzebne do posortowania obiektów przed wyświetleniem. dla kazdego obiektu znam shadery, textury, VertexDeclaration..., przełączanie każdego parametru kosztuje, wiec warto to posortować.

Robson

A szukałeś na Gamasutrze, albo DevNetcie? Moze juz ktos opisywał taki feature...?

PS. Pomysle nad tym... ale pewnie Rogal ma na to gotowe rozwiazanie :P

Rogal

Trochę mocno nieprecyzyjna treść, więc nie wiem czy dobrze rozumiem, ale jeśli tak to to działa w ten sposób:

1. Sortujemy parametry po koszcie, rosnąco.
2. Załóżmy, że znamy sposób w jaki optymalnie wyprodukować produkty korzystając tylko z k parametrów. Wtedy optymalny sposób wyprodukowania korzystając z k+1 parametrów wygląda tak:

SZCZUR

dzięki, o to dokładnie mi chodziło.

@Robson szukałem artykułów na ten temat i większość z nich opisuje ten temat pobieżnie nie zdradzając tajemnic:)

do sortowania mam zamiar użyć sortowania kubełkowego, znacie jakiś lepszy lub widzicie jakieś przeciwwskazania do używania kubełków?
(tablica jest duża ~100000, ilość wartości jest mała ~100)

SZCZUR

mam taki problem mamy "n" ludzi
wszyscy ludzie sie znaja i maja jakies stosunki miedzy soba (float [-1...1] )
-1 nie lubią sie
1 lubią sie

mamy k ludzi i znaleźć dla tych ludzi jak najlepszego negocjatora czyli kogoś kto będzie miał jak najlepsze relacje z tymi k ludźmi..

poszukał bym w google ale nie mam pomysłu co wpisać...

edit:

jak ktos ma linka do podobnego problemu to mi wystarczy...

Pawel Str.

Jak definiujesz najlepszego? Największa suma?

Jeżeli tak, to da się to banalnie zrobić w (n-k)*k (iterujesz po wszystkich ludziach i liczysz sumę ich krawędzi, czyli jak dobrymi byliby negocjatorami + standardowe podejście do znajdowania maksimum). Chyba da się też łatwo pokazać, że nie da się tego zrobić w mniej niż (n-k)*k, bo nie sprawdzając tego zbioru danych nie jesteśmy w stanie sprawdzić poprawności rozwiązania (dowód przez wyrocznię).

SZCZUR

szkoda

myślałem ze dałoby sie jakoś dane o ludziach przygotować wcześniej (bo te dane sie prawie nie będą zmieniać)

Pawel Str.

To czegoś tu nie rozumiem. Co się nie będzie zmieniać, a co owszem? Jak będziesz to wywoływał? Trochę za mało informacji dałeś, więc podałem rozwiązanie dla sytuacji jednorazowego szukania optimum.