[excel]Problem komiwojażera

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

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.

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.

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...

<?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.

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

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 ). 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.

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

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

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"!

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

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

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