Написание алгоритма на php (поиск пути между точками) - Помощь студентам

s88s · 03.06.2016, 10:47

Доброго времени суток!

Помогите понять как можно написать алгоритм поиска пути самому ?

задача есть скажем так 5 точек А, Б, В, Г, Д. и мне нужно найти путь между ними

risunok.jpg

За рисунок сори нарисовал как мог ...

Мне надо что бы при выборе точки допустим точка старта А и точка прибытия Д мне выдало все маршруты

то есть вывод был таким

1. А - Б - Д
2 А - В - Д
3 А - Г - Д
4 А- Б - В - Г - Д

или же мне надо попасть от тачки А до точки Г

Вывод

1 А - Г
2. А - Б - В - Г

я просто не могу понять как это реализовать самому с нуля.

Serge_Bliznykov · 03.06.2016, 10:52

Гуглите теорию графов.
Помимо точек должна быть ещё заданы связи между ними (см. например, матрица смежности).

s88s · 03.06.2016, 11:41

Цитата:

Сообщение от Serge_Bliznykov

Гуглите теорию графов.
Помимо точек должна быть ещё заданы связи между ними (см. например, матрица смежности).

Я так понимаю мне нужно создать точку и между ними построить эту матрицу смежности ... все верно понял?

Serge_Bliznykov · 03.06.2016, 12:02

не совсем. матрица смежности описывает - какие есть точки (это размер матрицы) и какие между этими точками связи (на пересечении I-й строки и J-го столбца заносится информация о наличии (и свойстве) связи между I-й и J-й точками.

s88s · 03.06.2016, 16:27

Цитата:

Сообщение от Serge_Bliznykov

не совсем. матрица смежности описывает - какие есть точки (это размер матрицы) и какие между этими точками связи (на пересечении I-й строки и J-го столбца заносится информация о наличии (и свойстве) связи между I-й и J-й точками.

Блин вообще не понимаю как делать (((

s88s · 10.06.2016, 16:30

Помогите с решением вопроса с поиска пути ... не как не могу догнать как сделать ?

У меня есть скрипт который ищет путь вот как мне сделать так что бы скрипт искал все пути прохода .

вот сам скрипт

s88s · 10.06.2016, 16:32

Код:


<?php
header("Content-Type:text/html; charset=utf8");

function canGet($time, $byWhat) {
    return array('time'     =>  $time, 'by' =>  $byWhat);
}
function find_way($from,$where,$way,$pointNames){
global $pointNames;
$pointNames = array(
    'pet'   =>  'ст. м. Петроградская',
    'chk'   =>  'ст. м. Чкаловская',
    'gor'   =>  'ст. м. Горьковская',
    'spo'   =>  'ст. м. Спортивная',
    'vas'   =>  'ст. м. Василеостровская',
    'kre'   =>  'Петропавловская крепость',
    'let'   =>  'Летний сад',
    'dvo'   =>  'Дворцовая площадь',
    'isa'   =>  'Исакиевский собор',
    'nov'   =>  'Новая Голландия',
    'ras'   =>  'Дом Раскольникова',
    'gos'   =>  'Гостиный Двор',
    'sen'   =>  'Сенная Площадь',
    'vla'   =>  'ст. м. Владимирская',
    'vit'   =>  'Витебский вокзал',
    'teh'   =>  'Технологический Институт'
);

s88s · 10.06.2016, 16:33

Код:

$paths = array(
    'pet'   =>  array(
        'pet'   =>  canGet(10),
        'chk'   =>  canGet(10),
        'gor'   =>  canGet(3),
        'vas'   =>  canGet(10),
        'kre'   =>  canGet(5),
        'spo'   =>  canGet(3),
        'nov'   =>  canGet(5),
        'ras'   =>  canGet(7),
        'isa'   =>  canGet(6),
        'gos'   =>  canGet(6),
        'dvo'   =>  canGet(6),
        'vit'   =>  canGet(3),
        'sen'   =>  canGet(3),
        'vla'   =>  canGet(4),
        'let'   =>  canGet(6),
        'teh'   =>  canGet(3)
    ),
    'chk'   =>  array(
        'pet'   =>  canGet(10),
        'chk'   =>  canGet(10),
        'gor'   =>  canGet(3),
        'vas'   =>  canGet(10),
        'kre'   =>  canGet(5),
        'spo'   =>  canGet(3),
        'nov'   =>  canGet(5),
        'ras'   =>  canGet(7),
        'isa'   =>  canGet(6),
        'gos'   =>  canGet(6),
        'dvo'   =>  canGet(6),
        'vit'   =>  canGet(3),
        'sen'   =>  canGet(3),
        'vla'   =>  canGet(4),
        'let'   =>  canGet(6),
        'teh'   =>  canGet(3)
    ),
    'gor'   =>  array(
        'pet'   =>  canGet(10),
        'chk'   =>  canGet(10),
        'gor'   =>  canGet(3),
        'vas'   =>  canGet(10),
        'kre'   =>  canGet(5),
        'spo'   =>  canGet(3),
        'nov'   =>  canGet(5),
        'ras'   =>  canGet(7),
        'isa'   =>  canGet(6),
        'gos'   =>  canGet(6),
        'dvo'   =>  canGet(6),
        'vit'   =>  canGet(3),
        'sen'   =>  canGet(3),
        'vla'   =>  canGet(4),
        'let'   =>  canGet(6),
        'teh'   =>  canGet(3)
    ),
    'spo'   =>  array(
        'pet'   =>  canGet(10),
        'chk'   =>  canGet(10),
        'gor'   =>  canGet(3),
        'vas'   =>  canGet(10),
        'kre'   =>  canGet(5),
        'spo'   =>  canGet(3),
        'nov'   =>  canGet(5),
        'ras'   =>  canGet(7),
        'isa'   =>  canGet(6),
        'gos'   =>  canGet(6),
        'dvo'   =>  canGet(6),
        'vit'   =>  canGet(3),
        'sen'   =>  canGet(3),
        'vla'   =>  canGet(4),
        'let'   =>  canGet(6),
        'teh'   =>  canGet(3)
    ),
    'vas'   =>  array(
        'pet'   =>  canGet(10),
        'chk'   =>  canGet(10),
        'gor'   =>  canGet(3),
        'vas'   =>  canGet(10),
        'kre'   =>  canGet(5),
        'spo'   =>  canGet(3),
        'nov'   =>  canGet(5),
        'ras'   =>  canGet(7),
        'isa'   =>  canGet(6),
        'gos'   =>  canGet(6),
        'dvo'   =>  canGet(6),
        'vit'   =>  canGet(3),
        'sen'   =>  canGet(3),
        'vla'   =>  canGet(4),
        'let'   =>  canGet(6),
        'teh'   =>  canGet(3)
    ),
    'kre'   =>  array(
        'pet'   =>  canGet(10),
        'chk'   =>  canGet(10),
        'gor'   =>  canGet(3),
        'vas'   =>  canGet(10),
        'kre'   =>  canGet(5),
        'spo'   =>  canGet(3),
        'nov'   =>  canGet(5),
        'ras'   =>  canGet(7),
        'isa'   =>  canGet(6),
        'gos'   =>  canGet(6),
        'dvo'   =>  canGet(6),
        'vit'   =>  canGet(3),
        'sen'   =>  canGet(3),
        'vla'   =>  canGet(4),
        'let'   =>  canGet(6),
        'teh'   =>  canGet(3)
    ),
    'let'   =>  array(
        'pet'   =>  canGet(10),
        'chk'   =>  canGet(10),
        'gor'   =>  canGet(3),
        'vas'   =>  canGet(10),
        'kre'   =>  canGet(5),
        'spo'   =>  canGet(3),
        'nov'   =>  canGet(5),
        'ras'   =>  canGet(7),
        'isa'   =>  canGet(6),
        'gos'   =>  canGet(6),
        'dvo'   =>  canGet(6),
        'vit'   =>  canGet(3),
        'sen'   =>  canGet(3),
        'vla'   =>  canGet(4),
        'let'   =>  canGet(6),
        'teh'   =>  canGet(3)
    ),
    'dvo'   =>  array(
        'pet'   =>  canGet(10),
        'chk'   =>  canGet(10),
        'gor'   =>  canGet(3),
        'vas'   =>  canGet(10),
        'kre'   =>  canGet(5),
        'spo'   =>  canGet(3),
        'nov'   =>  canGet(5),
        'ras'   =>  canGet(7),
        'isa'   =>  canGet(6),
        'gos'   =>  canGet(6),
        'dvo'   =>  canGet(6),
        'vit'   =>  canGet(3),
        'sen'   =>  canGet(3),
        'vla'   =>  canGet(4),
        'let'   =>  canGet(6),
        'teh'   =>  canGet(3)
    ),
    'isa'   =>  array(
        'pet'   =>  canGet(10),
        'chk'   =>  canGet(10),
        'gor'   =>  canGet(3),
        'vas'   =>  canGet(10),
        'kre'   =>  canGet(5),
        'spo'   =>  canGet(3),
        'nov'   =>  canGet(5),
        'ras'   =>  canGet(7),
        'isa'   =>  canGet(6),
        'gos'   =>  canGet(6),
        'dvo'   =>  canGet(6),
        'vit'   =>  canGet(3),
        'sen'   =>  canGet(3),
        'vla'   =>  canGet(4),
        'let'   =>  canGet(6),
        'teh'   =>  canGet(3)
    ),

s88s · 10.06.2016, 16:33

Код:

    'nov'   =>  array(
        'pet'   =>  canGet(10),
        'chk'   =>  canGet(10),
        'gor'   =>  canGet(3),
        'vas'   =>  canGet(10),
        'kre'   =>  canGet(5),
        'spo'   =>  canGet(3),
        'nov'   =>  canGet(5),
        'ras'   =>  canGet(7),
        'isa'   =>  canGet(6),
        'gos'   =>  canGet(6),
        'dvo'   =>  canGet(6),
        'vit'   =>  canGet(3),
        'sen'   =>  canGet(3),
        'vla'   =>  canGet(4),
        'let'   =>  canGet(6),
        'teh'   =>  canGet(3)
    ),
    'ras'   =>  array(
        'pet'   =>  canGet(10),
        'chk'   =>  canGet(10),
        'gor'   =>  canGet(3),
        'vas'   =>  canGet(10),
        'kre'   =>  canGet(5),
        'spo'   =>  canGet(3),
        'nov'   =>  canGet(5),
        'ras'   =>  canGet(7),
        'isa'   =>  canGet(6),
        'gos'   =>  canGet(6),
        'dvo'   =>  canGet(6),
        'vit'   =>  canGet(3),
        'sen'   =>  canGet(3),
        'vla'   =>  canGet(4),
        'let'   =>  canGet(6),
        'teh'   =>  canGet(3)
    ),
    'gos'   =>  array(
        'pet'   =>  canGet(10),
        'chk'   =>  canGet(10),
        'gor'   =>  canGet(3),
        'vas'   =>  canGet(10),
        'kre'   =>  canGet(5),
        'spo'   =>  canGet(3),
        'nov'   =>  canGet(5),
        'ras'   =>  canGet(7),
        'isa'   =>  canGet(6),
        'gos'   =>  canGet(6),
        'dvo'   =>  canGet(6),
        'vit'   =>  canGet(3),
        'sen'   =>  canGet(3),
        'vla'   =>  canGet(4),
        'let'   =>  canGet(6),
        'teh'   =>  canGet(3)        
    ),
    'sen'   =>  array(
        'pet'   =>  canGet(10),
        'chk'   =>  canGet(10),
        'gor'   =>  canGet(3),
        'vas'   =>  canGet(10),
        'kre'   =>  canGet(5),
        'spo'   =>  canGet(3),
        'nov'   =>  canGet(5),
        'ras'   =>  canGet(7),
        'isa'   =>  canGet(6),
        'gos'   =>  canGet(6),
        'dvo'   =>  canGet(6),
        'vit'   =>  canGet(3),
        'sen'   =>  canGet(3),
        'vla'   =>  canGet(4),
        'let'   =>  canGet(6),
        'teh'   =>  canGet(3)
    ),
    'vla'   =>  array(
        'pet'   =>  canGet(10),
        'chk'   =>  canGet(10),
        'gor'   =>  canGet(3),
        'vas'   =>  canGet(10),
        'kre'   =>  canGet(5),
        'spo'   =>  canGet(3),
        'nov'   =>  canGet(5),
        'ras'   =>  canGet(7),
        'isa'   =>  canGet(6),
        'gos'   =>  canGet(6),
        'dvo'   =>  canGet(6),
        'vit'   =>  canGet(3),
        'sen'   =>  canGet(3),
        'vla'   =>  canGet(4),
        'let'   =>  canGet(6),
        'teh'   =>  canGet(3)
    ),
    'vit'   =>  array(
        'pet'   =>  canGet(10),
        'chk'   =>  canGet(10),
        'gor'   =>  canGet(3),
        'vas'   =>  canGet(10),
        'kre'   =>  canGet(5),
        'spo'   =>  canGet(3),
        'nov'   =>  canGet(5),
        'ras'   =>  canGet(7),
        'isa'   =>  canGet(6),
        'gos'   =>  canGet(6),
        'dvo'   =>  canGet(6),
        'vit'   =>  canGet(3),
        'sen'   =>  canGet(3),
        'vla'   =>  canGet(4),
        'let'   =>  canGet(6),
        'teh'   =>  canGet(3)
    ),
    'teh'   =>  array(
        'pet'   =>  canGet(10),
        'chk'   =>  canGet(10),
        'gor'   =>  canGet(3),
        'vas'   =>  canGet(10),
        'kre'   =>  canGet(5),
        'spo'   =>  canGet(3),
        'nov'   =>  canGet(5),
        'ras'   =>  canGet(7),
        'isa'   =>  canGet(6),
        'gos'   =>  canGet(6),
        'dvo'   =>  canGet(6),
        'vit'   =>  canGet(3),
        'sen'   =>  canGet(3),
        'vla'   =>  canGet(4),
        'let'   =>  canGet(6),
        'teh'   =>  canGet(3)        
    )
);

	if (!is_array($way)){
		$way=array();
		$way[]=$from;
	}

echo "<hr>";

print_r($way);

echo "<hr>";
	
	echo "<br>\n<br>\n<br>\nФУНКЦИЯ(".$pointNames[$from]."; ".$pointNames[$where]."; ".implode("=>",$way).")<br>\n";

	$current=$way[count($way)-1]; //на какой мы сейчас станции
	echo "Текущая станция: ".$current."<br>\n";

	if(array_key_exists($where,$paths[$current])){
		$way[]=$where;
		echo "		ОДИН ИЗ ПУТЕЙ: ".implode("=>",$way)."<br>\n";
		$GLOBALS['ways'][]=$way; //Добавляем вариант прохода в возвращаемый функцией массив
	}
	else{
		foreach ($paths[$current] as $k=>$v){
			$next=$k;
			if(!in_array($next,$way)){
		echo "Станции ".$next." нет в пути ".implode("=>",$way)."<br>\n";
		echo "	Вот какие у станции ".$next." выходы: ";		
				//---implode для ключей
				$stringImplode='';
				foreach($paths[$next] as $key=>$val)
					$stringImplode.=$key.", ";
		echo $stringImplode."<br>\n";;
				//---
				$way[]=$next;
				find_way($from,$where,$way);
				array_pop($way);
			}
			else{
				echo "Станция ".$next." уже есть в пути ".implode("=>",$way).";<br>\n";
			}
		}
	}
	if (isset($GLOBALS['ways']))
		return ($GLOBALS['ways']);
}
////////////////////////////////////
$ways=find_way('sen','sen',null);
echo "<br><br>Способы достижения цели: <br><br><br>\n";
foreach($ways as $k=>$v){
	echo implode("=>",$ways[$k]).";<br>\n";

for($rtr = 0; $rtr < count($ways[$k]); $rtr++){

	$lol = $ways[$k][$rtr];
	$eee = $pointNames[$lol] .";";
	$route_ex = explode(";", $eee);
	$new_route = array();
    foreach($route_ex as $key => $value) { 
	$new_route[] = '<input type="text" name="route[]" value="' . $value . '">';  
	if($key == 0){
		echo implode("<br>", $new_route);
	}

    }

}

}

?>

s88s · 13.06.2016, 00:08

Не кто не поможет разобратся?

03.06.2016, 10:47	#1
s88s Форумчанин Регистрация: 02.01.2014 Сообщений: 369	Написание алгоритма на php (поиск пути между точками) Доброго времени суток! Помогите понять как можно написать алгоритм поиска пути самому ? задача есть скажем так 5 точек А, Б, В, Г, Д. и мне нужно найти путь между ними risunok.jpg За рисунок сори нарисовал как мог ... Мне надо что бы при выборе точки допустим точка старта А и точка прибытия Д мне выдало все маршруты то есть вывод был таким 1. А - Б - Д 2 А - В - Д 3 А - Г - Д 4 А- Б - В - Г - Д или же мне надо попасть от тачки А до точки Г Вывод 1 А - Г 2. А - Б - В - Г я просто не могу понять как это реализовать самому с нуля. "Я не волшебник, я только учусь" Последний раз редактировалось Serge_Bliznykov; 03.06.2016 в 10:50.

10.06.2016, 16:30	#6
s88s Форумчанин Регистрация: 02.01.2014 Сообщений: 369	Помогите с решением вопроса с поиска пути ... не как не могу догнать как сделать ? У меня есть скрипт который ищет путь вот как мне сделать так что бы скрипт искал все пути прохода . вот сам скрипт "Я не волшебник, я только учусь"

13.06.2016, 00:08	#10
s88s Форумчанин Регистрация: 02.01.2014 Сообщений: 369	Не кто не поможет разобратся? "Я не волшебник, я только учусь"

Похожие темы
Тема	Автор	Раздел	Ответов	Последнее сообщение
Поиск расстояния между двумя точками	owl1n	C# (си шарп)	8	02.11.2013 12:47
Расстояние между точками	tatiana2472	Помощь студентам	14	02.06.2013 23:22
Поиск кратчайшего пути между N-м числом точек на плоскости	Shpuntik=)	Помощь студентам	8	10.01.2013 09:46
Поиск путей между 2 точками 10 пар на поле 36 клетках	Aerowalk	Фриланс	1	09.05.2011 06:08

03.06.2016, 10:52	#2
Serge_Bliznykov Старожил Регистрация: 09.01.2008 Сообщений: 26,229	Гуглите теорию графов. Помимо точек должна быть ещё заданы связи между ними (см. например, матрица смежности).

03.06.2016, 12:02	#4
Serge_Bliznykov Старожил Регистрация: 09.01.2008 Сообщений: 26,229	не совсем. матрица смежности описывает - какие есть точки (это размер матрицы) и какие между этими точками связи (на пересечении I-й строки и J-го столбца заносится информация о наличии (и свойстве) связи между I-й и J-й точками.