Optymalny algorytm cięcia odcinków

Odpowiedz Nowy wątek
2003-05-29 11:35

Rejestracja: 17 lat temu

Ostatnio: 17 lat temu

0

WItam. Problem jest taki:
Istnieje n odcinków (np. kabla) o różnych długościach. A ja potrzebuję x odcinków też o różnych długościach, Jak wybrać OPTYMALNIE potrzebne mi x odcinków z n odcinków ? Oczywiście mogę sobie ciąć n odcinki lecz nie mogę ich sklejać. Jak wybrać i ew. pociąć n odcinki aby straty (czylki odpady po pociętych odcinkach) były jak najmniejsze.
Mam nadzieję że dosyć jasno wytłumaczyłem problem. Poszukuje po prostu takiego algorytmu. Ważne jest aby liczenie nie trwało zbyt długo, czyli próba wszystkich kombinacji i późniejsza analiza najmniejszych strat odpada.

dzięki, pozdrawiam
Darek W.

Pozostało 580 znaków

2003-05-29 21:25

Rejestracja: 17 lat temu

Ostatnio: 2 lata temu

0

Widzę tylko jedną możliwość: zrób to dynamicznie. Jako, że jestem leniwy, nie napiszę jak konkretnie (nie chce mi się myśleć) - ale ta metoda wydaje się pasować do problemu.


Life is just a dream, you know...
[Cowboy Bebop]

Pozostało 580 znaków

2003-05-30 16:38
Administrator

Rejestracja: 17 lat temu

Ostatnio: 48 sekund temu

Lokalizacja: Poznań

0

Ja bym się raczej rozejrzał za algorytmami zachłannymi lub genetycznymi. One nie przeglądają całej przestrzeni rozwiązań, ale dają prawie optymalny wynik w znacznie krótszym czasie niż algorytmy wyczerpujące całą przestrzeń rozwiązań.
Jednak nie podam żadnych konkretnych przykładów, gdyż jestem w trakcie sesji i nie mam czasu :-(.


Pozostało 580 znaków

Odpowiedz

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