Algorytm do określenia co można zbudować z określonych części. LEGO

0

Hej szukam algorytmu który pozwoli ustalić o można określonych części, na przykładzie lego.
Posiadamy:
22 części A,
12 części B
13 części C

Model AUTA wymaga
10A 10B 4C
Model MOTORU wymaga
5A 5B 2C
Za to model SAMOLOTU wymaga:
10A 10B 55C

Odpytując nasz algorytm powinniśmy dostać AUTO, MOTOR

Ilość części jest racjonalnie mała, np 5-10 typów, [ed] z np. 100-200 możliwych.
Za to ilość modeli to tysiace.

Nie wiem jak się za to zabrać, wygląda na częsty problem ale nie znam tak na szybko żadnego gotowego algorytmu.

2

models.where(m => m.requirements.every(r => r.value <= storage[r.key])).select(m => m.name)

jakoś tak?

2

Wygląda podobnie do problemu plecakowego:
https://en.wikipedia.org/wiki/Knapsack_problem

0

@models.where(m => m.requirements.every(r => r.value <= storage[r.key]).select(m => m.name)

jakoś tak?

W sumie tak najprostszy możliwy algorytm to sprawdzić wszystkie parametry dla wszystkich modeli. Pewnie dlateg nie znam nazyw algorytmu bo to zbyt trywialne. Z drugiej strony takie podejście daje złożność n*k, gdzie a to liczba modeli, a k to liczba typ części. Nie jest to optymalne(dodałem do oryginalnego że typów cześci ogólnie jest wiele wiecej niż typów używanych).
Jeżeli zapisywali byśmy modele na 2 listach jednej która ma wysztkie modele które wymagają A i B to dostali byśmy niższą złożoność. Wiec moze można zrobic to optymalniej. A moze wystarczy dać ParticionKey, liczacy hash z A,B,C wrzucić to do bazy danych i zapomnieć o problemie?
A może załadować wszystko do ramu, bo mniej niz 100MB i mielić.

Wygląda jak problem plecakowy:

Skoro ma rozwiązanie wielomianowe to nie jest to problem plecakowy. Problem plecakowym była by wersja jakie modele wybrać by zużyć wszystkie częśc, wszystkich typów.

1

a jak się da np AUTO, MOTOR albo 2x MOTOR albo np. auto, motor albo samolot to co wtedy? Chodzi o każdy model, który się da z podanych części zbudować (dla każdego modelu jest osobna, TAKA SAMA kupka części) czy o modele, które NA RAZ można zbudować z podanych części.

Strasznie nieprecyzyjnie opisałeś co chcesz zrobić

0

a jak się da np AUTO, MOTOR albo 2x MOTOR albo np. auto, motor albo samolot to co wtedy? Chodzi o każdy model, który się da z podanych części zbudować (dla każdego modelu jest osobna, TAKA SAMA kupka części) czy o modele, które NA RAZ można zbudować z podanych części.

Chodzi o znalezie wszystkich modeli które da się zbudować. Nie ważne ile razy razy ten sam model mozna złozyć, oraz jak bardzo wykorzystane są czeście.
Jedyna informacja jaką chce uzyskać, to "TAK z tych cześci da sie zbudować AUTO", "Tak z tych cześci da sie z budować MOTOR".

1

no to gdzie widzisz problem? - lecisz po wszystkich modelach i sprawdzasz po kolei wymagania dla każdego. Jak wszystkie spełnione to się da a jak któryś nie spełniony to przerywasz bo się nie da. Koniec, kropka. Dwie pętle i dictionary i tyle

0

no to gdzie widzisz problem? - lecisz po wszystkich modelach i sprawdzasz po kolei wymagania dla każdego. Jak wszystkie spełnione to się da a jak któryś nie spełniony to przerywasz bo się nie da. Koniec, kropka. Dwie pętle i dictionary i tyle

Bo ciągle na pałe to ~100tys sprawdzeń co za pytania, petla w pętli z głową głową ~10 tys, sprawdzeń co zapytanie, a pewno można zrobić to sprawniej niż pętla w pętli. Na przykład dzieląc na 10 bucketów, które z grubsza filtrują dane, a potem pętla w pętli na to juz tylko ~1tys. Jeżeli okaże sie ze typów cześci jest nie 100-200 tylko 1000-2000, a modeli 10 tysiecy. To 2 algorym będzie działać, a pierwszy bedzie za wolny.

@abrakadaber Problem jest za trywialny zeby wymagał własnego wątku, prosty hash i lista powinny wystarczyć.

1

no i niby jak będziesz sprawdzał te "buckety"? Jak za wolno to odpal to w kilku wątkach. Co byś nie robił to musisz sprawdzić wszystkie wymagania dla danego zestawu i koniec.

1

No pewnie byłoby kilka myków, które można by zastosować w zależności od tego jak wyglądają dane np. jak wiesz, że dany klocek rzadko ktoś posiada to od razu możesz odrzucić zestawy, które go wymagają.

Albo na każdą część stworzyć zbiór, które modele da się zrobić i potem łączysz zbiory na podstawie wprowadzonych części.

Kwestia realnych danych oraz tego czy warto. Najlepiej napisać na próbę prostą wersję i zobaczyć czy w ogóle jest problem wydajnościowy

0

no i niby jak będziesz sprawdzał te "buckety"? Jak za wolno to odpal to w kilku wątkach. Co byś nie robił to musisz sprawdzić wszystkie wymagania dla danego zestawu i koniec.

Pętla w pętli ale na 1/10 czy 1/64 ilości danych. Jak dać drugi rząd buketów, np. bazujący na ilości części, a pierwszy na typach to bedzie to 1/100 czy 1/640 ilości danych. 1/640 przy kilku tysiącach to prawie bezpośredni dostęp.

1

Do rozważania optymalizacja (może samo budowanie grafu byłoby cięższe niż problem ;-) )

Zbudować graf skierowany dla zestawów: da się zbudować X -> to da się zbudować Y i zacząć od węzłów do których nic nie wchodzi. Jak da się zbudować coś na początku ścieżki, to może obciąć część sprawdzeń, dla zestawów "po drodze".

1

mam propozycję - zrób po mojemu (czyli najprościej jak się da) następnie zrób tak jak mówisz, sprawdź co jest szybsze i pokaż rezultaty. Nie mówię tego wcale złośliwie, po prostu jestem ciekaw wyników. Tylko pamiętaj, że dla obu wersji masz dane wejściowe takie same - mapa typ klocka -> dostępna ilość. Jeśli w zoptymalizowanej wersji będziesz się opierał na danych inaczej ułożonych to proces zmiany mapy na cokolwiek innego też musi się wliczać do czasu całego sprawdzania. Tak samo proponuję wszystko robić w pierwszym rzucie jednowątkowo.

0

hmmm ja bym posluzyl sie tym problemem plecakowym tyle tylko ze skupilbym sie na ksztalcie to znaczy potworzyl wzorce bryly przedmiotow np rower auto motor piechur ... a potem poprzez skalowanie dopasowywal klocki ukladal i sprawdzal na ile pokrywaja sie(wypelniaja) z moja bryla -ten przypadek co najbardziej procenutalnie wypelnia moja bryle oznaczylbym wieksza waga ... fajny projekt faajny pomysl z tymi klockami - fajny AI :)legoBrylaSztucznaIngteligencja.png

0

Dla mnie najprościej by było zrobić w bazie tabele i np. wybrać jakąś część np. A element, posortować ją po ilości potrzebnych elementów + każdy element ma relację do reszty danych o danym elemencie.

Potem zrobić second level sortowanie czyli wszystkie modele spłaszczyć do 1 elementu, które wymagają tej samej ilości elementów, żeby nie było duplikacji przy wyszukiwaniu biarnym, który jest po prostu zakresem, coś jak highway pointers.
Teraz robimy wyłuskanie elementu ze struktury czyli jak A jest 22 elementy, to szukamy w highway pointers warstwie posortowanej elementu i dostajemy zakres elementów w zwykłej tablicy posortowanej.
Tam mamy pewność, że te elementy spełniają dla A elementu wymaganego, potem trzeba dla każdego z nich sprawdzić resztę elementów.
Ten sposób sprawia, że nie trzeba całej bazy przeszukiwać, tylko od razu mamy potencjalne elementy, które spełniają pierwszy warunek.

Drugie podejście to dla każdego elementu zrobić takie wybranie zakresu elementów <= 22 dostępnych.
Dla A, B i C itp.
Potem mając te listy elementów to zrobić intersekcję między tymi trzeba wytypowanymi zbiorami i też powinno dać tylko spełniające warunki elementy.

Też jeszcze prościej można w bazie danych zrobić where A < 22 and B < 11 and C < 5, ale to wtedy będzie wykonane najpierw cała baza danych względem pierwszego warunku i te co zostaną zostanie na nich przeprowadzony drugi warunek i te co zostanie to następny i pozostała lista przefiltrowana to elementy spełniające kryteria.

Też jak się zrobi 1-2 rozwiązania to pewnie się wpadnie na jakieś optymalizacje, tak jak we wszystkich problemach algorytmicznych.

0

Dzieki za odzew, Temat umarł na dłuższy czas, bo przefiltrowanie danych w języku polski tak by dostać "klocki" A, B, C wymaga kilku dni roboczo okropnej ręcznej pracy, lub zatrudnia studenta na zlecenie, którego na koniec dnia trzeba bedzie sprawdzić...

0
_flamingAccount napisał(a):

Nie wiem jak się za to zabrać, wygląda na częsty problem ale nie znam tak na szybko żadnego gotowego algorytmu.

Teraz nie mamy algorytmów tylko AI. Co prawda ten algorytm działa w przestrzeni 2D ale z pewnością nie będzie to problematyczne żeby uogólnić go dla przestrzeni 3D i zadanych kształtów.

Powodzenia!

1 użytkowników online, w tym zalogowanych: 0, gości: 1