Skocz do zawartości


Zdjęcie

[excel]Problem komiwojażera


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

#1 Kai

Kai

    Stały użytkownik

  • 237 postów

Napisano 09 12 2006 - 14:58

Kilka osób, kilka forów - nikt nie potrafi tego zadania rozwiązać. Sam próbowałem, na zerach i jedynkach (dodatkowe tabele), Solverem, makrami - niestety pożądanego skutku nie osiągnąłem. Chodzi o tak zwany problem komiwojażera, czyli najkrótszą drogę. Mam 10 miast i muszę przez wszystkie tylko raz przejechać, a zarazem droga którą przebędę ma być najkrótsza. Zaczynam od miasta pierwszego i nie muszę do niego na końcu wracać. Wystarczy, że przebrnę przez wszystkie miasta w jak najkrótszej drodze. Zadanko jak już wspomniałem jest do zrobienia w Excelu. Można używać wszystkiego co wbudowane. Formuł, pisać makra, czy używać Solvera. I proszę mnie nie odsyłać do wikipedii, czy algorytmów Dijkstry. Przerobiłem to wszystko. Problem w tym, że implementacja tego w C, czy PHP to nie problem. Z Excelem jest już większy. Prosiłbym o pomoc, sugestie, może być nawet gotowiec. Liczę na jakiekolwiek rady.
Z góry dziękuje
Kai

  • 0

#2 Titter

Titter

    Linux I Sieć.

  • 237 postów

Napisano 09 12 2006 - 15:58

Hm...skoro implementacja tego w C to nie problem to zaimplementuj to poprostu w VBA (Visual Basic dla makr) i po sprawie. Wtedy tylko odpalacz makro, które dziala jak program tylko dostaje i oddaje troche inaczej zmienne. Mozesz mi podac implementacje tego w C a ja Ci to przerobie, bo szczerze, z tego co wiem to komiwojażer jest problemem klasy NP-zupełna a to nie są problemy ktore robi się od ręki :P

Ponadto przenosze to do Programowania :/

  • 0

#3 Kai

Kai

    Stały użytkownik

  • 237 postów

Napisano 09 12 2006 - 16:49

Hm...skoro implementacja tego w C to nie problem to zaimplementuj to poprostu w VBA (Visual Basic dla makr) i po sprawie.

Próbowałem. Samo wygenerowanie permutacji to 10! możliwości. Na moim sprzęcie zajęło by to mniej więcej kilka godzin (że tak napiszę wytrwałem do 70mb, a około 300 mega wyników musiał wytworzyć). Możliwe, że nie kieruje się w tą stronę co trzeba, ale to był jeden z moich pomysłów.

Mozesz mi podac implementacje tego w C a ja Ci to przerobie, bo szczerze, z tego co wiem to komiwojażer jest problemem klasy NP-zupełna a to nie są problemy ktore robi się od ręki

Nie pisałem tego w C. Ale wydaje mi się, że wiem jakby to można zrobić (bo łatwiej piszę się na forach, czy ifach niż na jeżeli i przy pomocy Solvera). Co do samego problemu to jest to pierwsza rzecz której rozwiązania, bądź co bądź sprecyzowanej do danego przypadku (Excel) jednoznacznej odpowiedzi nie znalazłem. Fakt, są tego typu xlsowskie pliki w zasobach internetu, ale są one na tyle skomplikowane, że nie ma sensu brać się nawet za ich analizę.
Z tego co wiem, można to zrobić za pomocą dwóch tabel. Z wartościami i z zerami i jedynkami odpowiadającymi za to, czy dane miasto było już odwiedzone, czy nie. Niestety tym sposobem też nie doszedłem do wyniku.
  • 0

#4 Titter

Titter

    Linux I Sieć.

  • 237 postów

Napisano 09 12 2006 - 17:42

Powiem tak. Skoro znasz i masz jakies pomysl to napisz go w C czy czymkolwiek a ja moge ci go przerobic na VBA skro nie miales z tym do czynienia. A nawiasem mowiac w VBA sa rowniez fory itp, to pelnowartosciowy jezyk programowania...
  • 0

#5 Kai

Kai

    Stały użytkownik

  • 237 postów

Napisano 09 12 2006 - 23:05

<?php
//45 wartości dwuwymiarowej tablicy zważając, że droga z miasta a->b == b->a

$table[1][2]=1;
...
$table[9][10]=5;

$v = 1;

for ( $i=3;$i=10;$i++ )
{
	if ( $table[1][$i-1] > $table[1][$i] )
	{
		$city[$v] = $i;
		$city_val[$v] = $table[1][$1];
	}
}

for ( $z=2;$z=9;$z++ )
{
	for ( $j=3;$j=10;$j++ )
	{
		for ( $c=1;$c=9;$c++ )
		{	
			if ( $j != $city[$c] && $j != $city[$v] )
			{
				if ( $table[$city[$v]][$j-1] > $table[$city[$v]][$j] )
				{
					$city[$v+1] = $j;
					$city_val[$v+1] = $table[$city[$v]][$j];
					switch ( $j )
					{
						case '10':
							$v++;
							break;
						default:
							break;
					}
				}	
			}
		}
	}
}
print $city_val[1]+$city_val[2]+$city_val[3]+$city_val[4]+$city_val[5]
+$city_val[6]+$city_val[7]+$city_val[8]+$city_val[9];
?>

Główny zarys jest taki. Możliwe, że są tam błędy - że ogólnie moje podejście jest złe. Jeśli czegoś nie wiesz z tego kodu, pytaj. Jeśli coś jest nie jasne, źle zrobione, jeśli cały pomysł jest zły - proszę pisz. Kod jest w PHP (sorry, że nie w C++, ale ściągam z MSDNAA aktualnie VS i nie mam na czym pisać). Proszę o odpowiedź.

PS: w VB 5, VB .NET'cie pisałem dwa lata ponad. Ale to już było z 3 latka temu więc część rzeczy uszło z głowy.
  • 0

#6 Titter

Titter

    Linux I Sieć.

  • 237 postów

Napisano 10 12 2006 - 00:16

No ale co za problem. Wklepujesz to samo tylko zmieniasz skladnie i odpalasz jako makro. Dane zamiast w tablicy przechowujesz w komorkach arkuszu a wynik wypluwasz do jakies innej komorki i po sprawie. jezeli faktycznie ten kod dziala. jeszczedo nie analizowal bo nie mam czasu. Jutro moze to przejrze :P
  • 0

#7 Kai

Kai

    Stały użytkownik

  • 237 postów

Napisano 11 12 2006 - 02:27

Wydaje mi się, że napisałem. Wreszcie ;) Przetestowałem pobieżnie i niby działa. Zmodyfikowałem znacznie mój kod z php i przepisałem do VBA (i przypomniałem sobie troche vbasica :P). Jutro przetestuje do końca i jak będzie ok to wrzucę na forum. Może komuś się przyda.Bo szczerze powiem, że bardzo trudno znaleźć gotowe rozwiązanie do tego problemu w tym przypadku.
  • 0

#8 Titter

Titter

    Linux I Sieć.

  • 237 postów

Napisano 11 12 2006 - 19:01

Tak zgodze sie, że trudno. Dziekuje w imieniu wlasnym i wszystkich forumowiczow za udostepnienie kodu ;) Napewno sie przyda, a i sam sobie to przetestuje :P Ale w C++ ;)
  • 0

#9 Marek_Bielecki

Marek_Bielecki

    Początkujący

  • 19 postów

Napisano 12 10 2007 - 12:26

Hm...skoro implementacja tego w C to nie problem to zaimplementuj to poprostu w VBA (Visual Basic dla makr) i po sprawie. Wtedy tylko odpalacz makro, które dziala jak program tylko dostaje i oddaje troche inaczej zmienne. Mozesz mi podac implementacje tego w C a ja Ci to przerobie, bo szczerze, z tego co wiem to komiwojażer jest problemem klasy NP-zupełna a to nie są problemy ktore robi się od ręki ;)Ponadto przenosze to do Programowania :/

Hm...skoro implementacja tego w C to nie problem to zaimplementuj to poprostu w VBA (Visual Basic dla makr) i po sprawie. Wtedy tylko odpalacz makro, które dziala jak program tylko dostaje i oddaje troche inaczej zmienne. Mozesz mi podac implementacje tego w C a ja Ci to przerobie, bo szczerze, z tego co wiem to komiwojażer jest problemem klasy NP-zupełna a to nie są problemy ktore robi się od ręki ;)Ponadto przenosze to do Programowania :/

może tak=Jeżeli(a1<a;a1=a1;a2=a2)=Jeżeli(a2<a3;a2=a2;a3=a3);;;;;;;;;;;;;;;;;;;;;;;;itd ażdo 10
  • 0

#10 Jotgie

Jotgie

    Zorientowany

  • 905 postów

Napisano 12 10 2007 - 20:34

może tak=Jeżeli(a1<a;a1=a1;a2=a2)=Jeżeli(a2<a3;a2=a2;a3=a3);;;;;;;;;;;;;;;;;;;;;;;;itd ażdo 10


Problem w tym, że w jednej komórce można zapisać max 255 znaków a to będzie więcej i trzeba by łaczyć formuły a to już się robi ładny "bigos"!
  • 0

#11 Marek_Bielecki

Marek_Bielecki

    Początkujący

  • 19 postów

Napisano 12 10 2007 - 21:25

to może tak
=Jeżeli(a1<a2;b1=a1;b1=a2)
.............................
=Jeżeli(a9<a10;b9=a9;b9=a10)

  • 0

#12 Marek_Bielecki

Marek_Bielecki

    Początkujący

  • 19 postów

Napisano 16 10 2007 - 05:36

Kilka osób, kilka forów - nikt nie potrafi tego zadania rozwiązać. Sam próbowałem, na zerach i jedynkach (dodatkowe tabele), Solverem, makrami - niestety pożądanego skutku nie osiągnąłem. Chodzi o tak zwany problem komiwojażera, czyli najkrótszą drogę. Mam 10 miast i muszę przez wszystkie tylko raz przejechać, a zarazem droga którą przebędę ma być najkrótsza. Zaczynam od miasta pierwszego i nie muszę do niego na końcu wracać. Wystarczy, że przebrnę przez wszystkie miasta w jak najkrótszej drodze. Zadanko jak już wspomniałem jest do zrobienia w Excelu. Można używać wszystkiego co wbudowane. Formuł, pisać makra, czy używać Solvera. I proszę mnie nie odsyłać do wikipedii, czy algorytmów Dijkstry. Przerobiłem to wszystko. Problem w tym, że implementacja tego w C, czy PHP to nie problem. Z Excelem jest już większy. Prosiłbym o pomoc, sugestie, może być nawet gotowiec. Liczę na jakiekolwiek rady.
Z góry dziękuje
Kai

pogadaj z AM w Lublinie kupili ode mnie tablice znaczników w excelu, problem był co prawda inny ale chyba przyda ci sie ona

  • 0

#13 Kai

Kai

    Stały użytkownik

  • 237 postów

Napisano 24 02 2008 - 15:55

Rozwiązałem to już ponad rok temu :confused: Zresztą krótki tutorial na ten temat jest na forum.

  • 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