To mój pierwszy "tutorial" (czy takowy problem można tak nazwać? :>) na tym forum pochodzący z mojej strony m1chu.eu. Mam nadzieję, że będzie prosty i zrozumiały. A więc do dzieła...Problem? Mamy wyznaczyć z pośród 10 miast najkrótszą trasę tak, żeby odwiedzić wszystkie dziesięć miast tylko raz.
Wykonanie? Excel z wszelkimi dostępnymi modułami (wykorzystana tutaj metoda jest na tyle "wszechstronna", że ewentualne przystosowanie jej do php, c++, delphi czy innych języków nie powinno sprawiać problemów)
Nie będę ukrywał, że same tłumaczenie odnosi się do tego tematu. Męczyłem się z nim stosunkowo długo, a wraz ze mną kilkanaście innych osób które te zadanie też chciały wykonać lub po prostu je poprosiłem o jakąś radę, czy pomoc. Pomimo, że było wśród nich wiele osób dobrych w zakresie szerokopojętej informatyki - nikomu się nie udało. Reasumując zakres historyczny - przyznaję też bym pewnie poległ, gdyby nie środek nocy i nagły szalony pomysł. A cała praca przez to, że koniecznie musiało to być w Excelu.2. Kilka słów wstępu o problemie
Samo zadanie można wykonać na kilka różnych sposobów. Co oczywiście nie oznacza, że którykolwiek z nich jest banalniejszy niż inne. Pod uwagę możemy tu zabrać (tak jak i ja mniej więcej brałem kolejno):1. metoda formułowa ze sprawdzaniem binarnym (0, 1 - w celu sprawdzenia czy miasto było już odwiedzone, czy nie),
2. metoda tabelaryczno - "Solverowa" polegająca na utworzeniu warunków ograniczających w Solverze w taki sposób, aby droga była najkrótsza,
3. metoda tabelaryczno - makrowa, czyli utworzenie algorytmu w VBA (Visual Basic for Applications) dzięki któremu zostanie wyliczona najkrótsza ścieżka
Słowami wstępu - nie można nie zauważyć, że sam problem dotyczy grafów. Rozwiązać go można korzystając z różnorodnych metod poczynając od Algorytmu Dijkstry (służący do obliczania najkrótszej ścieżki w wypadku, gdy wszystkie wagi są nieujemne), przechodząc w Cykle Hamiltona (obliczanie poprzez wyznaczenie wszystkich możliwych ścieżek co daje n!/2 cykli), a kończąc na zwykłym przeszukiwaniu dróg. O ile tego pierwszego algorytmu w ogóle nie testowałem, to w drugim przypadku wyliczenie wszystkich możliwych permutacji przy 10 miastach w Excelu zajęło by kilka dobrych godzin, zakładając że w ciągu generowania tych wszystkich permutacji nie wystąpił by żaden błąd. Oczywiście można było wygenerować te permutacje w inny sposób, jak np. poprzez napisaną specjalnie aplikację w C++ do generowania permutacji, jednakże dalsze bawienie się z warunkami w Solverze było dla mnie kompletnym nieporozumieniem. Opcję z formułami także na wstępie odrzucamy, gdyż moim zdaniem jest to zbyt manualny sposób jak na tego typu zadanie.
Ostatecznie (tak wtedy w środku nocy ) doszedłem do wniosku, iż najrozsądniej będzie napisać makro w celu rozwiązania tego problemu - który można nazwać problemem komiwojażera. Algorytm który tutaj wykorzystałem jest tzw. algorytmem przybliżonym co za tym idzie jest bardziej zbliżony realistycznym sytuacjom kiedy to znane są tylko odległości z danego miasta do wszystkich innych, a z kolejnego do reszty zostają poznane dopiero przy następnym spełnieniu pętli.3. Jak wykonać część arkuszową?
Po pierwsze utwórzcie sobie dwa arkusze. Jeden powiedzmy o nazwie pr_komiwojażera_tab (z tabelą i miejscem na wyniki, a także przyciskiem na wykonanie makra) i pr_komiwojażera_wyk (na wykres wyników). Powinno to wyglądać mniej więcej tak:
(pr_komiwojażera_tab - na czerwono przypisy i ramki dla wyjaśnienia)
(pr_komiwojażera_wyk)
Co do wstawiania pól, buttonu, kolorowania - nie ma co pisać. Każdy chyba wie jak to zrobić? Skupie się tu tylko po krótku na wykresie. Dobrze byłoby wybrać jego typ na XY Punktowy. Ważniejsze jest jednak to by wybrać poprawnie dane wartości:Seria X: dane miast odwiedzonych w kolejności, czyli część kolumny zaznaczonej na pomarańczowej obok Odwiedzone miasta:
Seria Y: dane odległości zaznaczone na pomarańczowo jako odległości pomiędzy miastami
Odnośnie wykresu i podstaw utworzenia arkuszów to chyba wszystko w czym możecie mieć problem.4. Tworzenie algorytmu
Sprawa w miarę prosta, dla Was Bo ja musiałem ten algorytm napisać, Wy dostaniecie go na tacy z krótkim przypisem. Przede wszystkim to musicie z menu Excela utworzyć nowe makro. Otworzy Wam się okienko Microsoft Visual Basic z modułką (Module1 za pewnie). I to kod który musicie wstawić dokładnie dla takiego układu jaki pokazałem powyżej na screenach:
Sub komi() ' ' komi Makro ' Makro zarejestrowane 2006-12-10, autor m1chu, www.m1chu.eu ' ' Licencja: Freeware => http://pl.wikipedia.org/wiki/Freeware ' ' Deklaracja typu i wielkośći tablicy dwuwymiarowej Dim Table(10, 10) ' Dwuwymiarowa tablica odległości miast Table(1, 2) = Range("D5").Value Table(1, 3) = Range("E5").Value Table(1, 4) = Range("F5").Value Table(1, 5) = Range("G5").Value Table(1, 6) = Range("H5").Value Table(1, 7) = Range("I5").Value Table(1, 8) = Range("J5").Value Table(1, 9) = Range("K5").Value Table(1, 10) = Range("L5").Value Table(2, 3) = Range("E6").Value Table(2, 4) = Range("F6").Value Table(2, 5) = Range("G6").Value Table(2, 6) = Range("H6").Value Table(2, 7) = Range("I6").Value Table(2, 8) = Range("J6").Value Table(2, 9) = Range("K6").Value Table(2, 10) = Range("L6").Value Table(3, 4) = Range("F7").Value Table(3, 5) = Range("G7").Value Table(3, 6) = Range("H7").Value Table(3, 7) = Range("I7").Value Table(3, 8) = Range("J7").Value Table(3, 9) = Range("K7").Value Table(3, 10) = Range("L7").Value Table(4, 5) = Range("G8").Value Table(4, 6) = Range("H8").Value Table(4, 7) = Range("I8").Value Table(4, 8) = Range("J8").Value Table(4, 9) = Range("K8").Value Table(4, 10) = Range("L8").Value Table(5, 6) = Range("H9").Value Table(5, 7) = Range("I9").Value Table(5, 8) = Range("J9").Value Table(5, 9) = Range("K9").Value Table(5, 10) = Range("L9").Value Table(6, 7) = Range("I10").Value Table(6, 8) = Range("J10").Value Table(6, 9) = Range("K10").Value Table(6, 10) = Range("L10").Value Table(7, 8) = Range("J11").Value Table(7, 9) = Range("K11").Value Table(7, 10) = Range("L11").Value Table(8, 9) = Range("K12").Value Table(8, 10) = Range("L12").Value Table(9, 10) = Range("L13").Value ' Dwuwymiarowa tablica odległości - odwrotna Table(2, 1) = Range("C6").Value Table(3, 1) = Range("C7").Value Table(4, 1) = Range("C8").Value Table(5, 1) = Range("C9").Value Table(6, 1) = Range("C10").Value Table(7, 1) = Range("C11").Value Table(8, 1) = Range("C12").Value Table(9, 1) = Range("C13").Value Table(10, 1) = Range("C14").Value Table(3, 2) = Range("D7").Value Table(4, 2) = Range("D8").Value Table(5, 2) = Range("D9").Value Table(6, 2) = Range("D10").Value Table(7, 2) = Range("D11").Value Table(8, 2) = Range("D12").Value Table(9, 2) = Range("D13").Value Table(10, 2) = Range("D14").Value Table(4, 3) = Range("E8").Value Table(5, 3) = Range("E9").Value Table(6, 3) = Range("E10").Value Table(7, 3) = Range("E11").Value Table(8, 3) = Range("E12").Value Table(9, 3) = Range("E13").Value Table(10, 3) = Range("E14").Value Table(5, 4) = Range("F9").Value Table(6, 4) = Range("F10").Value Table(7, 4) = Range("F11").Value Table(8, 4) = Range("F12").Value Table(9, 4) = Range("F13").Value Table(10, 4) = Range("F14").Value Table(6, 5) = Range("G10").Value Table(7, 5) = Range("G11").Value Table(8, 5) = Range("G12").Value Table(9, 5) = Range("G13").Value Table(10, 5) = Range("G14").Value Table(7, 6) = Range("H11").Value Table(8, 6) = Range("H12").Value Table(9, 6) = Range("H13").Value Table(10, 6) = Range("H14").Value Table(8, 7) = Range("I12").Value Table(9, 7) = Range("I13").Value Table(10, 7) = Range("I14").Value Table(9, 8) = Range("J13").Value Table(9, 8) = Range("J14").Value Table(10, 9) = Range("K14").Value ' Usuwanie wartości komórek (unset) Range("F21").Value = "" Range("F22").Value = "" Range("F23").Value = "" Range("F24").Value = "" Range("F25").Value = "" Range("F26").Value = "" Range("F27").Value = "" Range("F28").Value = "" Range("F29").Value = "" Range("H21").Value = "" Range("H22").Value = "" Range("H23").Value = "" Range("H24").Value = "" Range("H25").Value = "" Range("H26").Value = "" Range("H27").Value = "" Range("H28").Value = "" Range("H29").Value = "" ' Zerowanie komórek (nulled) Range("C5").Value = 0 Range("D6").Value = 0 Range("E7").Value = 0 Range("F8").Value = 0 Range("G9").Value = 0 Range("H10").Value = 0 Range("I11").Value = 0 Range("J12").Value = 0 Range("K13").Value = 0 Range("L14").Value = 0 ' Deklaracja uruchomienia okna pomocy Dim helpme As String helpme = Range("E17").Value Select Case helpme Case "help" MsgBox ("Problem komiwojażera został rozwiązany za pomocą makra poprzez utworzenie algorytmu przybliżonego, co w dużym stopniu zoptymalizowało czas jego działania." & vbCrLf & "Pełna specyfikacja projektu znajduję się na forum;]." & vbCrLf & vbCrLf & "Wpisz 'author' w komórkę komend, aby wyświetlić autor projektu") Case "author" MsgBox ("copyright, m1chu 2006, www.m1chu.eu" & vbCrLf & "rok 1 - Politechnika Poznańska") End Select ' Deklaracja zmiennej całkowitej inkrementowanej jako argument tablicy city Dim y As Integer y = 1 ' Deklaracja zmiennej całkowitej i potrzebnej do pętli odpowiadającej za ' wyznaczenie minimum drogi z 1 miasta Dim i As Integer ' Deklaracja tablic jednowymiarowych i ilości ich elementów Dim city(9) ' Tablica przechowująca indeksy odwiedzonych miast Dim city_val(9) ' Tablica przechowująca odległości pomiędzy odwiedzonymi miastami ' Przypisanie pierwotnych wartości do poniższych zmiennych city(y) = 2 city_val(y) = Table(1, 2) ' Pętla odpowiadająca za wyznaczenie najbliższego miasta z pierwszego miasta For i = 3 To 10 If (Table(1, city(y)) > Table(1, i)) Then city(y) = i city_val(y) = Table(1, i) End If Next ' Deklaracja zmiennych potrzebnych do wyszukania najkrótszej drogi Dim z As Integer Dim j As Integer Dim is_used As Integer is_used = 0 Range("F21").Value = city(1) Range("H21").Value = city_val(1) ' Pętle odpowiadające za wyszukanie najkrótszej drogi For z = 2 To 10 For j = 2 To 10 If j <> city(1) And j <> city(2) And j <> city(3) And j <> city(4) And j <> city(5) And j <> city(6) And j <> city(7) And j <> city(8) And j <> city(9) Then If (is_used = 0) Then city(y + 1) = j city_val(y + 1) = Table(city(y), j) is_used = j ElseIf (is_used <> 0) Then If (Table(city(y), is_used) > Table(city(y), j) And Table(city(y), j) <> "0") Then city(y + 1) = j city_val(y + 1) = Table(city(y), j) is_used = j Select Case j Case "10" If (city(1) <> "" And Range("F21").Value = "") Then Range("F21").Value = city(1) Range("H21").Value = city_val(1) ElseIf (city(2) <> "" And Range("F22").Value = "") Then Range("F22").Value = city(2) Range("H22").Value = city_val(2) ElseIf (city(3) <> "" And Range("F23").Value = "") Then Range("F23").Value = city(3) Range("H23").Value = city_val(3) ElseIf (city(4) <> "" And Range("F24").Value = "") Then Range("F24").Value = city(4) Range("H24").Value = city_val(4) ElseIf (city(5) <> "" And Range("F25").Value = "") Then Range("F25").Value = city(5) Range("H25").Value = city_val(5) ElseIf (city(6) <> "" And Range("F26").Value = "") Then Range("F26").Value = city(6) Range("H26").Value = city_val(6) ElseIf (city(7) <> "" And Range("F27").Value = "") Then Range("F27").Value = city(7) Range("H27").Value = city_val(7) ElseIf (city(8) <> "" And Range("F28").Value = "") Then Range("F28").Value = city(8) Range("H28").Value = city_val(8) ElseIf (city(9) <> "" And Range("F29").Value = "") Then Range("F29").Value = city(9) Range("H29").Value = city_val(9) End If y = y + 1 is_used = 0 End Select Else Select Case j Case "10" If (city(1) <> "" And Range("F21").Value = "") Then Range("F21").Value = city(1) Range("H21").Value = city_val(1) ElseIf (city(2) <> "" And Range("F22").Value = "") Then Range("F22").Value = city(2) Range("H22").Value = city_val(2) ElseIf (city(3) <> "" And Range("F23").Value = "") Then Range("F23").Value = city(3) Range("H23").Value = city_val(3) ElseIf (city(4) <> "" And Range("F24").Value = "") Then Range("F24").Value = city(4) Range("H24").Value = city_val(4) ElseIf (city(5) <> "" And Range("F25").Value = "") Then Range("F25").Value = city(5) Range("H25").Value = city_val(5) ElseIf (city(6) <> "" And Range("F26").Value = "") Then Range("F26").Value = city(6) Range("H26").Value = city_val(6) ElseIf (city(7) <> "" And Range("F27").Value = "") Then Range("F27").Value = city(7) Range("H27").Value = city_val(7) ElseIf (city(8) <> "" And Range("F28").Value = "") Then Range("F28").Value = city(8) Range("H28").Value = city_val(8) ElseIf (city(9) <> "" And Range("F29").Value = "") Then Range("F29").Value = city(9) Range("H29").Value = city_val(9) End If y = y + 1 is_used = 0 End Select End If End If Else Select Case j Case "10" If (city(1) <> "" And Range("F21").Value = "") Then Range("F21").Value = city(1) Range("H21").Value = city_val(1) ElseIf (city(2) <> "" And Range("F22").Value = "") Then Range("F22").Value = city(2) Range("H22").Value = city_val(2) ElseIf (city(3) <> "" And Range("F23").Value = "") Then Range("F23").Value = city(3) Range("H23").Value = city_val(3) ElseIf (city(4) <> "" And Range("F24").Value = "") Then Range("F24").Value = city(4) Range("H24").Value = city_val(4) ElseIf (city(5) <> "" And Range("F25").Value = "") Then Range("F25").Value = city(5) Range("H25").Value = city_val(5) ElseIf (city(6) <> "" And Range("F26").Value = "") Then Range("F26").Value = city(6) Range("H26").Value = city_val(6) ElseIf (city(7) <> "" And Range("F27").Value = "") Then Range("F27").Value = city(7) Range("H27").Value = city_val(7) ElseIf (city(8) <> "" And Range("F28").Value = "") Then Range("F28").Value = city(8) Range("H28").Value = city_val(8) ElseIf (city(9) <> "" And Range("F29").Value = "") Then Range("F29").Value = city(9) Range("H29").Value = city_val(9) End If y = y + 1 is_used = 0 End Select End If Next Next End SubPrzypisy macie w samym kodzie. I ostatnie co Wam zostało to przypisanie makra do utworzonego wcześniej buttona. Wystarczy kliknąć na nim prawym przyciskiem myszy i wybrać Przypisz makro... po czym wybrać nasze makro.4. Reasumując...
No właśnie. Jak widzicie nie ma tutaj kawy na ławę. Nie ma krok po kroku skrupulatnie, dlaczego? Wychodzę z prostego założenia jeśli ktoś nie zna tych podstaw obsługi Excela to nie ma co bawić się w rozwiązywanie tego typu problemów. Jeśli ktoś je zna to powinien sobie wg. tego poradzić z nim. A jeśli nadal ma problemy, proszę śmiało pytać tutaj na forum. Chętnie odpowiem.
Chcecie rady? Zanalizujcie dokładnie problem, swój arkusz i ten kod - bo jest on chyba najprościej napisany jak się da. I będzie po kłopocie. Po za tym macie tutaj kilka linków dla tych co wiedzą mniej:
http://office.microsoft.com/pl-pl/training...1831141045.aspx
http://www.excelforum.pl/light.php
http://www.google.pl
No i na koniec... nie wyrażam zgody na redystrybuowanie, kopiowanie nawet w częściach tego tekstu czy kodu na innych forach, stronach - gdziekolwiek. Używać we własnym użytku można jak najbardziej, w niezmienionej formie (chodzi o kod) :]
PS: jakbym o czymś zapomniał, coś zgubił - też piszcie w tym temacie.
© 2006, m1chu.eu