[PHP] Komiwojager. Przetrzymywanie odwiedzonych miast w pamięci Opcje

[emillo91]

Witam. Piszę program, który wyznacza najkrótszą drogę do wszystkich miast za pomocą algorytmu najbliższego sąsiada. Mój problem polega na tym, że nie wiem w jaki sposób kazać algorytmowi ignorować już odwiedzone miasta. Program, który już napisałem działa poprawnie do momentu aż napotka miasto które odwiedził a następnie się zapętla z poprzednim miastem. Wiem że muszę odwiedzone miasta trzymać w tablicach i z nich pobierać dane ale nie umiem sobie poradzić kiedy dane są pobierane z tablic w pętli while. Próbowałem też usuwać indeksy ze wszystkich tablic gdzie występuje nazwa odwiedzonego miasta (podczas każdego przejścia pętli) ale nie wiem jak wyznaczyć i usunąć indeks z tablicy typu $tablica[0] = array{....};( indeksy przy tablicach są mi potrzebne do wyznaczania kolejnego miasta z którego mają być pobierane dane).
Poniżej kod:

CODE

[PHP] pobierz, plaintext 
<?php
$miasto[0] = 'wroclaw';
$miasto[1] = 'krakow';
$miasto[2] = 'gdansk';
$miasto[3] = 'poznan';
$miasto[4] = 'lodz';
    $wybor[0] = array(
	'krakow' => '150',
	'gdansk' => '300',
	'poznan' => '276',
        'lodz' => '290'
	);
	$wybor[1] = array(
	'wroclaw' => '150',
	'gdansk' => '236',
	'poznan' => '125',
        'lodz' => '185',
	);
	$wybor[2] = array(
	'wroclaw' => '300',
	'krakow' => '236',
	'poznan' => '100',
        'lodz' => '150',
	);
	$wybor[3] = array(
	'wroclaw' => '276',
	'gdansk' => '100',
	'krakow' => '125',
        'lodz' => '130',
	);
$wybor[4] = array(
	'wroclaw' => '290',
	'gdansk' => '150',
	'krakow' => '185',
        'poznan' => '130',
	);
 
$miasto_poczatek = 'wroclaw';
for($a = 0; $a < sizeof($miasto); $a++){
 
if($miasto[$a] == $miasto_poczatek){
	$start = $a;
}
}
echo 'Miasto startowe to:'.$miasto[$start].'<br>';
 
$zlicz = 0;
$miasto_koniec[] = array();
 
asort ($wybor[$start]);
reset ($wybor[$start]); // Funkcja ta powoduje powrót do pierwszego elementu tablicy
 
while (list ($klucz, $wartosc) = each ($wybor[$start])) {
 
 $miasto_koniec[$zlicz] = $klucz;
 
$miasto_koncowe = $miasto_koniec[0];
$zlicz++;
}
$zlicz = 0;
for($b = 0; $b < sizeof($miasto); $b++){
 
$miasto[$b] = $miasto_koncowe;
 echo 'Kolejne miasto to:'.$miasto[$b].'<br>';
 
for($c = 0; $c < sizeof($miasto); $c++){
 
if(($miasto[$c] == $miasto[$b])){
 
asort ($wybor[$c]);
reset ($wybor[$c]); // Funkcja ta powoduje powrót do pierwszego elementu tablicy
 
while (list ($klucz2, $wartosc2) = each ($wybor[$c])) {
 
 $miasto_koniec[$zlicz] = $klucz2;
$najmniejsze = $miasto_koniec[0];
$zlicz++;
}
}
$miasto_koncowe = $najmniejsze;
 
$zlicz = 0;
}
}
 
 
 
 
?>
[PHP] pobierz, plaintext 

Odnośnie odpowiedzi to chciałbym się dowiedzieć czy jest możliwe usuwanie indeksów z wybranych tablic w takiej postaci jak są tutaj przedstawione, czy muszę całkowicie przerobić kod?
Ewentualnie jakim warunkiem bądź funkcją mogę sprawdzić czy istnieje dany indeks w danej tablicy i wyświetlić numer indeksu.

[Pyton_000]

Grafy to dość skomplikowany temat.

Tu masz fajny artykuł z tym co i jak.
https://www.sitepoint.com/data-structures-4/

Ten post edytował Pyton_000 4.12.2016, 16:24:26

[phpamator]

Zrobiłbym to tak:

[PHP] pobierz, plaintext 
 
if (($key = array_search('wartosc', $array)) !== false) {
    unset($array[$key]);
}
 
// albo
 
if(in_array($twoj_array, 'wartosc')){
    unset($array[$key]);
}
 
//albo
 
if (in_array('wartosc', $array)) 
{
    unset($array[array_search('wartosc',$array)]);
}
 
[PHP] pobierz, plaintext 

Ale ja jestem amator/newbie, czy usunięcie klucza wystarczy?

Ten post edytował PHPRexio 4.12.2016, 18:28:13

[emillo91]

chodzi o to żeby algorytm nie uznawał odwiedzonego miasta z najmniejszą odległością za miasto które musi odwiedzić. Jutro będę kombinował. Dzięki za pomoc i życzę udanego wieczoru (IMG:style_emoticons/default/wink.gif)

Witam. Przepraszam że tak późno odpisuję ale wyleciało mi z głowy że miałem dać znać co mi wyszło z tym algorytmem. Odnośnie mojego problemu to musiałem stworzyć dodatkową tablicę w której przetrzymywałem odwiedzone miasta i do której algorytm odwoływał się za każdym razem gdy wybierał kolejne miasto do odwiedzenia. Poniżej kod gotowego algorytmu.

[PHP] pobierz, plaintext 
<?php
$miasto[0] = 'wroclaw';
$miasto[1] = 'krakow';
$miasto[2] = 'gdansk';
$miasto[3] = 'poznan';
$miasto[4] = 'lodz';
    $wybor[0] = array(
	'krakow' => '150',
	'gdansk' => '300',
	'poznan' => '276',
        'lodz' => '290'
	);
	$wybor[1] = array(
	'wroclaw' => '150',
	'gdansk' => '236',
	'poznan' => '125',
        'lodz' => '185',
	);
	$wybor[2] = array(
	'wroclaw' => '300',
	'krakow' => '236',
	'poznan' => '100',
        'lodz' => '150',
	);
	$wybor[3] = array(
	'wroclaw' => '276',
	'gdansk' => '100',
	'krakow' => '125',
        'lodz' => '130',
	);
$wybor[4] = array(
	'wroclaw' => '290',
	'gdansk' => '150',
	'krakow' => '185',
        'poznan' => '130',
	);
 
$miasto_poczatek = 'poznan'; // inicjacja miasta startowego
 
 
for($a = 0; $a < sizeof($miasto); $a++){
 
     if($miasto[$a] == $miasto_poczatek){
	 $start = $a;
     }
}
 
$zlicz = 0;
$zlicz2 = 0;
$zlicz3 = 1;
 
$miasto_koniec[] = array();
$niemamiast[] = array();
$odwiedzone[] = array();
 
asort ($wybor[$start]);
reset ($wybor[$start]); // Funkcja ta powoduje powrót do pierwszego elementu tablicy
 
while (list ($klucz, $wartosc) = each ($wybor[$start])) {
 
     $miasto_koniec[$zlicz] = $klucz;
 
     $miasto_koncowe = $miasto_koniec[0];
     $pomocnicza = $miasto_koniec[0];
     $zlicz++;
}
$zlicz = 0;
for($b = 0; $b < sizeof($miasto); $b++){
 
     $miasto[$b] = $miasto_koncowe; // inicjacja kolejnych miast
 
     for($c = 0; $c < sizeof($miasto); $c++){
 
         if(($miasto[$c] == $miasto[$b])){
             $odwiedzone[0] = $miasto_poczatek; // miasta
             $odwiedzone[1] = $pomocnicza;      // nie włączone do poniższej pętli
             asort ($wybor[$c]);
             reset ($wybor[$c]); // Funkcja ta powoduje powrót do pierwszego elementu tablicy
 
             while (list ($klucz2, $wartosc2) = each ($wybor[$c])) {
 
                 $miasto_koniec[$zlicz] = $klucz2;
                 $zlicz++;
             }
             for($d = 0; $d < sizeof($miasto); $d++){
                 if (!in_array($miasto_koniec[$d], $odwiedzone)) {
                     $niemamiast[$zlicz2] = $miasto_koniec[$d];
                     $zlicz2 += 1;
                 }
                 $nowypunkt = $niemamiast[0];
             }
             $odwiedzone[$zlicz3] = $nowypunkt;
             $zlicz3 += 1;
             $zlicz2 = 0;
         }
         $miasto_koncowe = $odwiedzone[$b+1];
         $zlicz = 0;
     }
 
}
echo 'Odwiedzone miasta to: </br>';
for($e = 0; $e < sizeof($miasto); $e++){
if($e != 4){
$znak = "->";
}
else{
$znak = ".";
}
echo $odwiedzone[$e].$znak;
}
 
 
 
?>
[PHP] pobierz, plaintext 

Program działa poprawnie pod warunkiem że za miasto startowe nie wybierzemy pierwszego miasta z listy. Jeżeli miastem startowym w tym przypadku będzie Wrocław to algorytm weźmie kilka razy pod uwagę pierwszą tablicę. Wrzucam algorytm bo może komuś się przyda. Wydaje mi się że wystarczy usuwać tablice które zostały już odwiedzone ale nie jestem do końca pewien. phpamator dzięki za twoją pomoc, która rozwiązała mój problem ze sprawdzaniem czy dane miasto zostało odwiedzone. Temat do zamknięcia. Dziękuję (IMG:style_emoticons/default/smile.gif)