Elektroda.pl
Elektroda.pl
X
Proszę, dodaj wyjątek www.elektroda.pl do Adblock.
Dzięki temu, że oglądasz reklamy, wspierasz portal i użytkowników.

Excel VBA - Szukanie najlepszej kombinacji połączeń z matrycy

Drzemek 30 Kwi 2013 11:41 1458 2
  • #1 30 Kwi 2013 11:41
    Drzemek
    Poziom 2  

    Witam,
     
    mam dość złożony problem, z którym borykam się już od jakiegoś czasu. Przeszukałem różne fora ale nie znalazłem niczego co byłoby pomocne w poniższym przypadku (być może szukając użyłem złych sformułowań).
    Mam matrycę prezentującą koszty transportu pomiędzy miastami (jeśli występuje połączenie bezpośrednie, koszt występuje na przecięciu się wiersza [miasto startowe] i kolumny [miasto końcowe]). Staram się znaleźć sposób na wyszukiwanie najoptymalniejszych kombinacji połączeń pomiędzy miastami w przypadku gdy nie występuje miedzy nimi połączenie bezpośrednie.
     
    np. poszukuję połączeń z miasta B do miasta L. Ponieważ nie ma miedzy nimi bezpośredniego połączenia (nie występuje koszt na przecięciu się wiersza B z kolumną L), muszę znaleźć kilka możliwie najlepszych kombinacji (np. B→C, C→E i E→L lub B→D, D→F, F→K i K→L) i wybrać z nich tą najbardziej mi pasująca. Ponieważ możliwych kombinacji może być bardzo dużo, myślałem o jakimś ograniczeniu (np. max 4 połączenia).
    Nie wiem czy da się to zrobić za pomocą jakichś funkcji czy jednak bez VBA się nie obejdzie.
    z góry dzięki za wszelkie sugestie.
    Przemek

    0 2
  • #2 30 Kwi 2013 13:10
    marcinj12
    Poziom 40  

    Problem na pierwszy rzut oka podobny do "problemu komiwojażera", z tą różnicą, że nie musisz odwiedzić wszystkich miast... To jakieś realne zagadnienie czy projekt teoretyczny na uczelnię?

    Po mojemu widzę dwie możliwości:
    - możesz spróbować kombinatoryki, z miasta "docelowego" patrzysz, gdzie możesz się dostać i za ile, w drugim kroku - dla każdego z tych punktów patrzysz, dokąd i za ile możesz się z niego dostać etc, aż znajdziesz ten właściwy. Nie wiem jak z wydajnością, może być problem.
    - ja osobiście bym użył któregoś z algorytmów przybliżonych, np. genetyczny lub mrówkowy. Nie dają one gwarancji znalezienia optymalnego rozwiązania, ale im dłużej działają, tym większe na to szanse.
    - zawsze możesz też zdać się na łut szczęścia i poruszać się "losowo". Z miasta początkowego jedziesz do losowo wybranego, połączonego z nim miasta i tak dalej, aż znajdziesz się w mieście docelowym, przekroczysz założoną ilość "skoków", np. 100, lub najbardziej optymalne znalezione dotychczas rozwiązanie. Dodatkowo możesz np. unikać poruszania się do miast, w których już byłeś.

    To, że bez VBA się nie obejdzie, to za mało powiedziane - o funkcjach excela zapomnij. W obydwu wypadkach czeka Cię sporo kodowania i konieczność zgłębienia algorytmu, które na szczęście są popularne i dobrze opisane. Może nawet znajdziesz gotowy kod, choć chyba lepiej będzie ja samemu go wymyślisz, bo będzie wymagał modyfikacji.

    Na gotowca bym nie liczył, temat zbyt skomplikowany żeby ktoś nad tym siedział, przynajmniej za darmo :).

    0
  • #3 30 Kwi 2013 15:04
    Drzemek
    Poziom 2  

    Cześć,

    na gotowca nie liczyłem, raczej na ukierunkowanie gdzie szukać.
    Zacząłem sobie robić plik który dziła mniej więcje zgodnie z pierwszym ze sposobów przedstawionych przez Ciebie, ale to nie jest dobre rozwiązanie gdy matryca się zwiększy i bedzie więcej mozliwych kombinacji połączeń.
    Ok, poczytam sobie o algorytmach, może mi coś zakiełkuje w głowie :)

    0