Skocz do zawartości


Zdjęcie

Problem komiwojażera (najkrótszej drogi)


  • Zamknięty Temat jest zamknięty
2 odpowiedzi w tym temacie

#1 Kai

Kai

    Stały użytkownik

  • 237 postów

Napisano 29 03 2007 - 20:11

1. Tematyka problemu i wykonanie (zakres historyczny :rolleyes:)
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)
Dołączona grafika

(pr_komiwojażera_wyk)
Dołączona grafika

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 Sub
Przypisy 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

  • 0

#2 d_stachowiak86

d_stachowiak86

    Nowy

  • 1 postów

Napisano 11 01 2011 - 14:21

Witam.

Szukam pomocy, mam problem z "problemem komiwojażera",
Wyjaśniłeś problem, ale metodą tabelaryczno - makrową, ja muszę rozwiązać ten problem
metodą tabelaryczno - "Solverową" czyli wykorzystując dodatek "Solver".
Czy jesteś w stanie mi pomóc??

Użytkownik Wujek Celdur edytował ten post 11 01 2011 - 19:02
komuś się chyba pomyliło "odpowiedz" z "cytuj" itd.. Edycja.

  • 0

#3 Kantoro

Kantoro

    Zaawansowany użytkownik

  • 550 postów

Napisano 11 01 2011 - 18:40

Po pierwsze wątek z 2007 roku.

Po drugie cytowanie nieczytelne.

Zamykam.

  • 0

Zobacz więcej tematów z tagiem: Microsoft Excel



Użytkownicy przeglądający ten temat: 0

0 użytkowników, 0 gości, 0 anonimowych