Algorytm doboru desek :)

Witam wszystkich,
czy ktoś mógłby podpowiedzieć jaki algorytm użyć do następującego tematu.
Mam pale wbite w wodę w równej odległości od siebie (A) przy założeniu że pierwszy i ostatni od brzegu mają te same odległości (od brzegu B)
oraz mam 4 długości profili stalowych już przyciętych na wymiar. 1 2 3 4 łączonych łącznikiem L
Jak określić ilość i kolejność układania poszczególnych profili stalowych na palach tak aby był jak najmniejszy odpad z ostatniego profilu docinanego do brzegu przy jak najmniejszej ilości łączników profili.
Obecnie rysuje to w programie CAD oczywiście zaczynając od najdłuższych profili ( załóżmy 4-4-4-4-4-4-4-4 a potem już 3-2-1 lub 3-3-2 gdzie "-" = L) i od ostatniej 1 lub 2 odcinam
Ale temat się skomplikował jak okazało się że łączenie profili łącznikiem L nie może opierać się na palu który ma średnice 20cm (może być za lub przed palem).
Wtedy w CAD rysowanie sporo się wydłuża :)
A ... co ważne ... rozstaw pali nigdy nie jest większy niż 3/4 długości największego profilu stalowego "4" nie będzie ze to 4 metry.

Nie jestem informatykiem więc poproszę powoli pisać jeżeli to nie problem :)
Dzięki i pozdrawiam.Rysunek2-Layout1.pdf

Gdybyś dodał jakieś przykłady w obrazkach to może by można zacząć coś kombinować. Od samego czytania to zwoje w głowie zaczynają iskrzyć.

4w0rX4t4X napisał(a):

Gdybyś dodał jakieś przykłady w obrazkach to może by można zacząć coś kombinować. Od samego czytania to zwoje w głowie zaczynają iskrzyć.

Zedytowałem post - sroki za jakość

kapsuz napisał(a):

Nie jestem informatykiem więc poproszę powoli pisać jeżeli to nie problem :)

My też nie rozumiemy o co Ci dokładnie chodzi...
Rzucasz jakieś liczby, podajesz jakieś typy łączników.
Ale mi to zbyt wiele nie mówi.

Opisz problem tak jak na konkursach informatycznych.
Co dajesz na wejściu? Co chcesz uzyskać na wyjściu?

Na pierwszy rzut oka problem wygląda jak Cutting Stock Problem:
https://en.wikipedia.org/wiki/Cutting_stock_problem

Na studiach rozwiązywaliśmy to algorytmem genetycznym.

Ale z dodatkowymi warunkami, jeśli naprawdę są konieczne, robi się z tego jakiś specjalny wariant tego algorytmu.

Jeśli wszystko jest zawsze w tej samej odległości i masz o zgrozo 4 wymiary prętów oraz nie jest to problem informatyczny tylko praktyczny, to praktyczny algorytm, jest taki.
Rozrysuj, sobie to dla każdej możliwej pary prętów - jest tylko 8 kombinacji do sprawdzenia,
wybierz najlepsza,
powtórz na całą długość mostu,
Odcinki łączące się z brzegiem dosztukuj.

Na 80-90% dostaniesz rozwiązanie mniej więcej optymalne, nawet jeśli nie z punktu widzenia stali, to z punktu widzenia takiego ze nikt źle nie potnie skoro wszystkie są cięte tak samo.

Jest 10-20% szans ze istnieje rozwiązanie w którym skrawek jednej długości łączy się ze skrawkiem drugiej długości, a w każdym prześle długości są różne, za to potrzebujesz najmniej stali. Żeby to policzyć musiałbyś sprawdzić albo wszystkie kombinacje, albo mieć algorytm znajdujący coś wystarczająco blisko optymalnego rozwiązania, ale tu wracamy do problemu 1 nikt nie rozumie jaki problem tak naprawdę rozwiązujesz.

4w0rX4t4X napisał(a):

Gdybyś dodał jakieś przykłady w obrazkach to może by można zacząć coś kombinować. Od samego czytania to zwoje w głowie zaczynają iskrzyć.

Skoro jest niezrozumiałe to oczywiście poprawiam - dodałem wersje z CAD w pdf 1 poście.

_flamingAccount napisał(a):

Jeśli wszystko jest zawsze w tej samej odległości i masz o zgrozo 4 wymiary prętów oraz nie jest to problem informatyczny tylko praktyczny, to praktyczny algorytm, jest taki.
Rozrysuj, sobie to dla każdej możliwej pary prętów - jest tylko 8 kombinacji do sprawdzenia,
wybierz najlepsza,
powtórz na całą długość mostu,
Odcinki łączące się z brzegiem dosztukuj.

Na 80-90% dostaniesz rozwiązanie mniej więcej optymalne, nawet jeśli nie z punktu widzenia stali, to z punktu widzenia takiego ze nikt źle nie potnie skoro wszystkie są cięte tak samo.

Jest 10-20% szans ze istnieje rozwiązanie w którym skrawek jednej długości łączy się ze skrawkiem drugiej długości, a w każdym prześle długości są różne, za to potrzebujesz najmniej stali. Żeby to policzyć musiałbyś sprawdzić albo wszystkie kombinacje, albo mieć algorytm znajdujący coś wystarczająco blisko optymalnego rozwiązania, ale tu wracamy do problemu 1 nikt nie rozumie jaki problem tak naprawdę rozwiązujesz.

:) i tak tez robię - ogólnie ja sobie z tym radze. Ale pomyślałem ze można zrobić algorytm który dobierze poszczególne długości - rozstawi je w odpowiedniej kolejności tak aby łączniki nie były na palach i od razu będę wiedział ile mam odciąć z ostatniego - bo tak je dobierze że odpad będzie najmniejszy.
Takie niby g ale czas oszczędzi.
K.

1. czy "grubość" łącznika jest brana pod uwagę?
2. czy pale mogą mieć różną grubość
3. czy zawsze najpierw chcemy pozbyć się najdłuższych
4. czy mamy określoną liczbę profili
5. na rysunku w pdfie na 4 palu od lewej i na 3 od prawej (szczegół B) wypada łącznik - pisałeś, że to jest niepoprawna sytuacja - to jak to w końcu jest?

1 - Nie
2 - zakładamy że nie
3 - Tak zazwyczaj robię na chłopski rozum
4 - Na rys pokazałem profil na palu co jest złym rozwiązaniem - koniec łącznika licząc np. od lewej nie powinien nachodzić na początek pala pal lub początek łącznika na koniec pala . Łącznik nie powinien pokrywać się (dotykać) z palem. Może być przez lub za.

no to jest banalne do rozwiązania:

1. bierzesz od najdłuższego
2. sprawdzasz czy jak go położysz od ostatniego po lewej (jak jest pierwszy to od zera) to wypadnie na palu
3. jak nie to ok, przesuwasz się na koniec położonego
4. jak tak to bierzesz kolejny krótszy i goto 2. Jak każdy wypada na palu to wracasz do najdłuższego i go skracasz o np. 2x grubość pala
5. jak jest koniec to docinasz ostatni

Do zaklepania razem z testowaniem w jakieś 30 minut

Nie wiem jakiej długości są te pomosty ale wdaje mi się, że ten problem najszybciej rozwiązałbym korzystając z kartki, linijki i cyrkla.
Zrobiłbym to tak:

Na kartce rysuję (oczywiście w odpowiednio mniejszej skali):

1. Pale.
2. odcinki odpowiadające dostępnym profilom.

Dalej postępuję wg algorytmu:

1. Biorę długość profilu "najdłuższego".
2. Odmierzam go tak długo aż "zajdzie kolizja ze słupem".
3. Jeśli zajdzie kolizja ze słupkiem zmieniam długość jednego profilu. (prawdopodobnie optymalne będzie zawsze wybranie najkrótszego ale to muszę jeszcze sobie sprawdzić ).
4. Powtarzam algorytm do końca ( do drugiego brzegu ).

Jak bym pisał program to najpierw wyznaczyłbym zbiór, który wyznacza gdzie stoją słupy.

Mamy dane:

• $profile : array [ l1, l2, l3 l4 ] - zakładam, że l1 to najdłuższy a l4 najkrótszy długośći w centymetrach.
• dległości pomiędzy słupami $distance
• grubość słupa $width
• odległość pierwszego słupa od pierwszego brzegu $startMargin
• odległość ostatniego słupa od drugiego brzegu $endMargin
• długość łącznika $connLength

Czyli pozycje słupów (możemy je nazwać obszarami zakazanymi, w których nie może wystąpić połączenie) opisuje nam wzór:

Te obszary zakazane, w których nie możemy mieć łącznika to:
( $startMargin + $n * ( $distance ) - $connLength/2, $startMargin + $n * ( $distance ) + $width + $connLength/2 )
gdzie $n oznacza kolejne słupy.

i tyle... łączenia nie mogą wystąpić w obszarach określonych powyższym zbiorem.

Czy tylko profil numer 4 posiada łącznik profili czy można go dostawić do każdego z profili?

kapsuz napisał(a):

czy ktoś mógłby podpowiedzieć jaki algorytm użyć do następującego tematu.

Bądź zachłanny - najpierw największe, jak nie pasuje to mniejszy i znowu największy i tak do końca!

Jeśli dobrze rozumiem problem, to da się to rozwiązać, ale robienie tego na "pieszo" zajmie olbrzymią ilość czasu.

Opisując problem po swojemu:

• mamy długość np. 120 metrów i profile o długości np. 2, 3, 4 metry chcemy uzyskać jak najmniejszy odpad

Rozwiązaniem jest backtracking:

• mamy do ułożenia długość 120 metrów więc bierzemy pierwszy możliwy profil 2 metry i mamy nowy problem pod tytułem "mamy długość 118 metrów"
• mamy do ułożenia długość 120 metrów, więc bierzemy drugi możliwy profil 3 metry i mamy nowy problem pod tytułem "mamy długość 117 metrów"
• mamy do ułożenia długość 120 metrów, więc bierzemy drugi możliwy profil 4 metry i mamy nowy problem pod tytułem "mamy długość 116 metrów"
  ...

Powtarzamy do momentu aż, "możliwy profil" jest dłuższy niż liczba metrów do ułożenia, wtedy możemy policzyć odpad.

Po wykonaniu tego algortymu będziemy mieli listę możliwych kombinacji i jaki odpad wyprodukują. Wystarczy wybrać kombinajcę z najmniejszym odpadem, ale...

... masz jeszcze jeden warunek "Ale temat się skomplikował jak okazało się że łączenie profili łącznikiem L nie może opierać się na palu który ma średnice 20cm (może być za lub przed palem)." to możesz sprawdzić które kombinacje spełniają wymagany warunek. Jeżeli pale możesz przesuwać, to masz ileś kombinacji i wtedy masz jeszcze więcej możliwych rozwiązań...

GuepygR7vR8EPm napisał(a):

Jeśli dobrze rozumiem problem, to da się to rozwiązać, ale robienie tego na "pieszo" zajmie olbrzymią ilość czasu.

Opisując problem po swojemu:

• mamy długość np. 120 metrów i profile o długości np. 2, 3, 4 metry chcemy uzyskać jak najmniejszy odpad

Rozwiązaniem jest backtracking:

• mamy do ułożenia długość 120 metrów więc bierzemy pierwszy możliwy profil 2 metry i mamy nowy problem pod tytułem "mamy długość 118 metrów"
• mamy do ułożenia długość 120 metrów, więc bierzemy drugi możliwy profil 3 metry i mamy nowy problem pod tytułem "mamy długość 117 metrów"
• mamy do ułożenia długość 120 metrów, więc bierzemy drugi możliwy profil 4 metry i mamy nowy problem pod tytułem "mamy długość 116 metrów"
  ...

Powtarzamy do momentu aż, "możliwy profil" jest dłuższy niż liczba metrów do ułożenia, wtedy możemy policzyć odpad.

Po wykonaniu tego algortymu będziemy mieli listę możliwych kombinacji i jaki odpad wyprodukują. Wystarczy wybrać kombinajcę z najmniejszym odpadem, ale...

... masz jeszcze jeden warunek "Ale temat się skomplikował jak okazało się że łączenie profili łącznikiem L nie może opierać się na palu który ma średnice 20cm (może być za lub przed palem)." to możesz sprawdzić które kombinacje spełniają wymagany warunek. Jeżeli pale możesz przesuwać, to masz ileś kombinacji i wtedy masz jeszcze więcej możliwych rozwiązań...

Tylko będzie trochę tych opcji.
Ogólnie trzeba by sprawdzić wszystkie warianty które nachodzą na pal i je odrzucić. Potem z pozostałych wariantów wybrać najkrótsze ułożenie przy którym jest najmniejsze odcięcie odpad.
To nawet by się trzymało kupy ale dodatkowo jak uwzględnić czy dać więcej łączników i mniejszy odpad czy mniej łączników i większy odpad bo będzie się kalkulowało.
Ogólnie odcinki miedzy palami nie są większe niż 2,6m . Można by ustalić maksymalny odcinek 2,6 odjąć po obu stronach 2x odcinek B i obliczyć rozstaw już docelowy jak będzie większy niż 2,6m do dogadać do kalkulacji jeden pal i wtedy wyjdzie np. 2,4 wtedy można już puszczać algorytm ale i tak trochę będzie tych możliwości .
Wydaje mi się że mały problem wcale nie jest taki prosty - bynajmniej dla mnie.
Ale spoko - dziękuje wszystkim bardzo - skorzystam odpisując - Przynajmniej poczytałem sobie trochę o algorytmach
K.