Najkrótsza droga - Algorytm Mrówkowy Opcje

[Landon]

Witam czy ktoś wie w jaki sposób napisać algorytm mrówkowy dla grafu najkrótszej drogi miedzy miastem a i b z ominięciem przeszkód x, y , z? Jeśli tak to proszę o pomoc (IMG:http://forum.php.pl/style_emoticons/default/smile.gif)

Ten post edytował Landon 5.05.2008, 13:17:21

[Babcia@Stefa]

Myślę że w PHP będzie to ciężkie do napisania.
Wiem że w flashu istnieje coś takiego ( mapa Google ).

Popraw nazwę tematu (IMG:http://forum.php.pl/style_emoticons/default/winksmiley.jpg)

Dziękuję, Babcia@Stefa

Ten post edytował batman 11.06.2008, 12:04:01

Powód edycji: nie bawimy się w moderatora. takie rzeczy się zgłasza.

[carbolymer]

@up: myślę że nie wiesz o czym mówisz.

Zbyt ogólne pytanie zadałeś. Niby jak mamy ci pomóc skoro nie wiemy jak ma wyglądać ten graf (chociażby jakimi prawami się rządzi)?

[wlamywacz]

Algorytm ACO

I poszukaj w google pod hasłem algorytm ACO ten pierwszy link to wynik z wielkiego G

[Landon]

No tak nie powiedziałem o co chodzi więc tak (a i dzięki za ten link) (IMG:http://forum.php.pl/style_emoticons/default/smile.gif) ...

Operuje na układzie współrzędnych z ustawionymi przeszkodami które muszą zostać ominięte... mam podany punkt początkowy i końcowy. Moim zadaniem jest przejście przez najkrótszą drogę pomiędzy tymi punktami. Następnie wyliczenie długości trasy i średniej szybkości z danych przypisanych do współrzędnych (IMG:http://forum.php.pl/style_emoticons/default/tongue.gif)

[wlamywacz]

Może przeczytaj to i poszukaj w google dalej:
http://www.google.pl/search?q=ant-cycle&am...lient=firefox-a

[Landon]

Nie wiem czy zauważyłeś http://www.google.pl/search?q=ant-cycle to link do google szukam tam lecz zbyt wiele nie mogę znaleźć (IMG:http://forum.php.pl/style_emoticons/default/tongue.gif)

[wlamywacz]

ant-cycle to nazwa najwydajniejszej wersji algorytmu mrówkowego

[Landon]

Po wielu trudach i zmaganiach zrozumiałem zasadę działania tego algorytmu no ale mam problem z zastosowaniem.

Mam tablicę 2 wymiarową

[PHP] pobierz, plaintext 
<?php
$tablica = array();
$tablica[0][0] = 0;
$tablica[0][1] = 'woda';
$tablica[0][2] = 'woda';
$tablica[0][3] = 'woda';
$tablica[0][4] = 'woda';
$tablica[0][5] = 'woda';
?>
[PHP] pobierz, plaintext 

itd...

muszę odpalić pętle do {} while aż do wykonania warunku
następnie puścić pierwszą mrówkę i zapisać jej pokonaną drogę do tablicy
no i zwiększyć w tablicy wartość o 1 $tablica[0][0] = 0;

i doszedłem do czegoś takiego:

[PHP] pobierz, plaintext 
<?
 
$tablica = array();
$tablica[0][0] = 1;
$tablica[1][0] = 'woda';
$tablica[2][0] = 'woda';
$tablica[3][0] = 'woda';
$tablica[4][0] = 'woda';
$tablica[5][0] = 'woda';
 
$tablica[0][1] = 1;
$tablica[1][1] = 1;
$tablica[2][1] = 1;
$tablica[3][1] = 1;
$tablica[4][1] = 'woda';
$tablica[5][1] = 'woda';
 
$tablica[0][2] = 1;
$tablica[1][2] = 1;
$tablica[2][2] = 1;
$tablica[3][2] = 1;
$tablica[4][2] = 'woda';
$tablica[5][2] = 'woda';
 
$tablica[0][3] = 1;
$tablica[1][3] = 1;
$tablica[2][3] = 1;
$tablica[3][3] = 1;
$tablica[4][3] = 'woda';
$tablica[5][3] = 'woda';
 
$tablica[0][4] = 1;
$tablica[1][4] = 'woda';
$tablica[2][4] = 'woda';
$tablica[3][4] = 1;
$tablica[4][4] = 'woda';
$tablica[5][4] = 'woda';
 
$tablica[0][5] = 1;
$tablica[1][5] = 1;
$tablica[2][5] = 1;
$tablica[3][5] = 1;
$tablica[4][5] = 'woda';
$tablica[5][5] = 'woda';
 
$tablica[0][6] = 'woda';
$tablica[1][6] = 'woda';
$tablica[2][6] = 'woda';
$tablica[3][6] = 1;
$tablica[4][6] = 'woda';
$tablica[5][6] = 'woda';
 
$tablica[0][7] = 'woda';
$tablica[1][7] = 'woda';
$tablica[2][7] = 'woda';
$tablica[3][7] = 1;
$tablica[4][7] = 'woda';
$tablica[5][7] = 'woda';
 
$tablica[0][8] = 'woda';
$tablica[1][8] = 'woda';
$tablica[2][8] = 'woda';
$tablica[3][8] = 1;
$tablica[4][8] = 'woda';
$tablica[5][8] = 'woda';
 
$tablica[0][9] = 1;
$tablica[1][9] = 1;
$tablica[2][9] = 1;
$tablica[3][9] = 1;
$tablica[4][9] = 'woda';
$tablica[5][9] = 'woda';
 
$start_x = 0;
$start_y = 0;
$stop_x = $_GET['x'];
$stop_y = $_GET['y'];
 
if ($tablica[$stop_x][$stop_y] == 'woda') {
  echo 'Wskazany punkt jest w wodzie<br />';
} else {
  $op = 0;
  $dlogosc = array();
  $i = 0;
  do {
	$o_x = $start_x;
	$o_y = $start_y;
	$tablica[$o_x][$o_y]++;
	$i++;
	$dlogosc[$i] = 1;
	do {
	  if ($o_x < $stop_x) $o_x++;
	  elseif ($o_x > $stop_x) $o_x--;
 
	  if ($o_y < $stop_y) $o_y++;
	  elseif ($o_y > $stop_y) $o_y--;
 
	  $tablica[$o_x][$o_y]++;
	  $dlogosc[$i]++;
	} while ($o_x != $stop_x || $o_y != $stop_y);
  } while ($op == 1);
  if ($stop_x == $start_x && $start_y == $stop_y) {
	echo 'Wskazane współrzędne są na poczatku<br />';
  } else {
	echo 'Długość '.$dlogosc[$i].' kratek<br />';
  }
}
 
echo '<meta http-equiv="Content-Type" content="text/html; charset=UTF-8" />
<table cellspacing="0" cellpadding="0">';
foreach ($tablica as $k => $w) {
  echo '<tr>';
  foreach ($w as $k2 => $w2) {
	echo '<td style="background-color:'.($w2 != 'woda' ? $w2 == 1 ? 'green' : 'red' : 'blue').'; 
		width: 50px; height: 50px;">&nbsp;</td>';
  }
  echo '</tr>';
}
echo '</table>';
?>
[PHP] pobierz, plaintext 

Powoli idę do przodu... (próbuje dopisać by mijał ale chyba funkcje muszę wprowadzić do tego)

http://rdzen.osadnicy.net/table.php?x=2&y=5

Ten post edytował Landon 11.06.2008, 12:51:05

[legorek]

Czy to nie jest klastyczny problem najkrótszej ścieżki ? Zobacz to: A*

[dr_bonzo]

Algorytm mrowkowy to NIE jest A*

[legorek]

Gdzie ja napisałem że jest (IMG:http://forum.php.pl/style_emoticons/default/smile.gif) ? Po prostu chciałem zasugerować autorowi tematu, że to typowy problem rozwiązywany przez algorytm A star, więc może łatwiej będzie o przykłady implementacji.

[Landon]

jeśli chodzi o A* to tu jest ciekawy link:

http://www.policyalmanac.org/games/aStarTutorial_pl.htm

muszę się przyjrzeć temu dokładniej (IMG:http://forum.php.pl/style_emoticons/default/smile.gif)

Mam teraz coś takiego:
http://test.osadnicy.net/astar/

teraz tylko zostało uprościć kod i przenieść do js (IMG:http://forum.php.pl/style_emoticons/default/winksmiley.jpg)

o całe 500ms przyśpieszony ale i tak zbyt wolno (IMG:http://forum.php.pl/style_emoticons/default/smile.gif) średnio wypada koło 150-200ms

Ten post edytował Landon 11.06.2008, 19:46:55