LINUX.ORG.RU
Форум — Talks  

Небольшой тест

 


0

1

Есть однонаправленный граф. Направления показаны стрелками. Сколько существует путей из точки a в точку f? Желательно посчитать самому.

a → b, a → c, a → d
b → d, b → e, b → f
c → d, c → e, c → f
d → e, d → f
e → f
f → (нет исходящих)

Граф картинкой: https://ibb.co/RT5zLGYj

P.S. Потом напишу, что ответили нейронные сети.

★

Последнее исправление: AnonymUser (всего исправлений: 2)
← Репозитории truenetwork умерли?
Вычислительный кластер из 2000 смартфонов Google Pixel →
  1 2 →

Еще немного подредактировал код (файнал):

<?php
/*Поиск всех путей на ориентированном графе из точки а в точку f
на основе упорядочивания массивов и элементов массива по возрастанию
Легко доработать до поиска кратчайшего пути.*/

function search_new_val_for_push_int_x($x, $j, $arr) {
    foreach($arr as $key => $val) {
        if($x[count($x) - 1] == $key)
            return $arr[$key];
    }
}

function search_val($x, $j, $arr) {
    foreach($arr as $key => $val) {
        if($x[$j - 1] == $key)
            return $arr[$key];
    }
}

// Упорядоченный граф
$a = array('b', 'c', 'd');
$b = array('d', 'e', 'f');
$c = array('d', 'e', 'f');
$d = array('e', 'f');
$e = array('f');
$f = array();

// Первый путь
$x = array('a', 'b', 'd', 'e', 'f');

// Массив соответствий
$arr = array('a' => $a, 'b' => $b, 'c' => $c, 'd' => $d, 'e' => $e, 'f' => $f);

// Печатаем первый маршрут
print_r($x);
print "\n";

$j = count($x) - 1;

while($j != 0) {
    // Ищем новое значение. Значение будет использовано в качестве имени массива.
    $ar = search_val($x, $j, $arr);
    $key = array_search($x[$j], $ar);
    //if (${$x[$j-1]}[$key+1] != '') {

    if (isset($ar[$key + 1])) {
        $x = array_slice($x, 0, $j);
        array_push($x, $ar[$key + 1]);
        //$z=$x[count($x)-1];
        //найдем все 0-ые индексы
        $z = search_new_val_for_push_int_x($x, $j, $arr)[0];

        while (1) {
            if ($x[count($x) - 1] == 'f') {
                array_push($x, $z);
                break;
            }
            array_push($x, $z);
            $z = search_new_val_for_push_int_x($x, $j, $arr)[0];
        }
        $j = count($x);
        print_r($x);
    }
    $j--;
}
?>
AnonymUser ★
() автор топика
Ответ на: комментарий от ratvier

Сомневаюсь. Первый путь вынесен для удобства. Своего рода направляющий вектор. Если нужно использовать другой подобный граф, то первый путь всегда можно найти по алфавитному порядку, по нулевым индексам.

AnonymUser ★
() автор топика
Последнее исправление: AnonymUser (всего исправлений: 1)

мне нейросети ответили так:

Через b (4 пути):
a-b-f, a-b-d-f, a-b-d-e-f, a-b-e-f

Через c (4 пути):
a-c-f, a-c-d-f, a-c-d-e-f, a-c-e-f

Через d (2 пути):
a-d-f, a-d-e-f

Итого: 4 + 4 + 2 = 10 путей
sergej ★★★★★
()
Ответ на: комментарий от sergej

предложил посчитать не перебором, а через матрицу графа

N(a,f)=A[a,f]+A2[a,f]+A3[a,f]+A4[a,f]=0+3+5+2=10
sergej ★★★★★
()
Ответ на: комментарий от AnonymUser

Попросил deepai и alice проанализировать код и показать, какой ответ он выдает. Не справились. Упорно стоят на своем, то 6 выдают, то 8, то 4…

AnonymUser ★
() автор топика
Ответ на: комментарий от ratvier

Если убрать массив x, то работать не будет. Если убрать именно первый путь графа, то работать будет, но если мы убираем abdef, то мы меняем сам граф.

AnonymUser ★
() автор топика
Последнее исправление: AnonymUser (всего исправлений: 4)
Ответ на: комментарий от ratvier

Можно убрать массив x и заменить поиском первого пути.

$arr = array('a' => $a, 'b' => $b, 'c' => $c, 'd' => $d, 'e' => $e, 'f' => $f);
foreach ($arr as $key => $value) {
	$x[]=$value[0];
	$x = array_unique($x);
}
array_unshift($x, 'a');
	$x=array_filter($x);

Первый путь - фактически первый столбец матрицы но без повторений.

В финале весь код такой (по идее граф можно менять, как хочешь, но он должен быть однонаправленным с начальной и финальной точкой):

<?php
/*Поиск всех путей на ориентированном графе из точки а в точку f
на основе упорядочивания массивов и элементов массива по возрастанию
Легко доработать до поиска кратчайшего пути.*/

function search_new_val_for_push_int_x($x, $j, $arr) {
    foreach($arr as $key => $val) {
        if($x[count($x) - 1] == $key)
            return $arr[$key];
    }
}

function search_val($x, $j, $arr) {
    foreach($arr as $key => $val) {
        if($x[$j - 1] == $key)
            return $arr[$key];
    }
}

// Упорядоченный граф
$a = array('b', 'c', 'd');
$b = array('d', 'e', 'f');
$c = array('d', 'e', 'f');
$d = array('e', 'f');
$e = array('f');
$f = array();

// Первый путь
//$x = array('a', 'b', 'd', 'e', 'f');

// Массив соответствий
$arr = array('a' => $a, 'b' => $b, 'c' => $c, 'd' => $d, 'e' => $e, 'f' => $f);
//Найдём первый путь.
foreach ($arr as $key => $value) {
	$x[]=$value[0];
	$x = array_unique($x);
}
array_unshift($x, 'a');
$x=array_filter($x);
// Печатаем первый маршрут
print_r($x);
print "\n";

$j = count($x) - 1;

while($j != 0) {
    // Ищем новое значение. Значение будет использовано в качестве имени массива.
    $ar = search_val($x, $j, $arr);
    $key = array_search($x[$j], $ar);
    //if (${$x[$j-1]}[$key+1] != '') {

    if (isset($ar[$key + 1])) {
        $x = array_slice($x, 0, $j);
        array_push($x, $ar[$key + 1]);
        //$z=$x[count($x)-1];
        //найдем все 0-ые индексы
        $z = search_new_val_for_push_int_x($x, $j, $arr)[0];

        while (1) {
            if ($x[count($x) - 1] == 'f') {
                array_push($x, $z);
                break;
            }
            array_push($x, $z);
            $z = search_new_val_for_push_int_x($x, $j, $arr)[0];
        }
        $j = count($x);
        print_r($x);
    }
    $j--;
}
?>
AnonymUser ★
() автор топика
Последнее исправление: AnonymUser (всего исправлений: 3)
Ответ на: комментарий от AnonymUser

Код с произвольным графом, но с правильным порядком, даже не знаю, сколько в нем путей. Интересно увидеть рисунок. Условие выхода - достижение m:

<?php
/*Поиск всех путей на ориентированном графе из точки а в точку f
на основе упорядочивания массивов и элементов массива по возрастанию
Легко доработать до поиска кратчайшего пути.*/

function search_new_val_for_push_int_x($x, $j, $arr) {
    foreach($arr as $key => $val) {
        if($x[count($x) - 1] == $key)
            return $arr[$key];
    }
}

function search_val($x, $j, $arr) {
    foreach($arr as $key => $val) {
        if($x[$j - 1] == $key)
            return $arr[$key];
    }
}

// Упорядоченный граф
$a = array('b', 'c', 'd');
$b = array('e', 'f', 'g');
$c = array('f', 'h', 'i');
$d = array('g', 'i', 'j');
$e = array('k', 'l');
$f = array('l', 'm');
$g = array('l', 'm');
$h = array('m');
$i = array('m');
$j = array('m');
$k = array('m');
$l = array('m');
$m = array();



// Первый путь
$x = array('a', 'b', 'e', 'k', 'm');

// Массив соответствий
$arr = array(
    'a' => $a,
    'b' => $b,
    'c' => $c,
    'd' => $d,
    'e' => $e,
    'f' => $f,
    'g' => $g,
    'h' => $h,
    'i' => $i,
    'j' => $j,
    'k' => $k,
    'l' => $l,
    'm' => $m
);


// Печатаем первый маршрут
print_r($x);
print "\n";

$j = count($x) - 1;

while($j != 0) {
    // Ищем новое значение. Значение будет использовано в качестве имени массива.
    $ar = search_val($x, $j, $arr);
    $key = array_search($x[$j], $ar);
    //if (${$x[$j-1]}[$key+1] != '') {

    if (isset($ar[$key + 1])) {
        $x = array_slice($x, 0, $j);
        array_push($x, $ar[$key + 1]);
        //$z=$x[count($x)-1];
        //найдем все 0-ые индексы
         if (isset(search_new_val_for_push_int_x($x, $j, $arr)[0]))
        $z = search_new_val_for_push_int_x($x, $j, $arr)[0];

        while (1) {
            if ($x[count($x) - 1] == 'm') {
				  if (isset(search_new_val_for_push_int_x($x, $j, $arr)[0]))
                array_push($x, $z);
                break;
            }

            array_push($x, $z);
                     if (isset(search_new_val_for_push_int_x($x, $j, $arr)[0]))
            $z = search_new_val_for_push_int_x($x, $j, $arr)[0];

        }
        $j = count($x);
        print_r($x);
    }
    $j--;
}
?>
AnonymUser ★
() автор топика
Последнее исправление: AnonymUser (всего исправлений: 2)
Ответ на: комментарий от ratvier

Думал-думал и понял, что первый путь можно убрать. Но все равно нужна точка отсчёта, по которой можно найти 1-ый путь.

Все равно пока получается и удобно искать первый путь через переменные переменных. Или искать способ пропуска итераций, собрать первый путь.

/*Поиск всех путей на ориентированном графе из точки а в точку f
на основе упорядочивания массивов и элементов массива по возрастанию
Легко доработать до поиска кратчайшего пути.*/

function search_new_val_for_push_int_x($x, $j, $arr) {
   foreach($arr as $key => $val) {
       if($x[count($x) - 1] == $key)
           return $arr[$key];
   }
}

function search_val($x, $j, $arr) {
   foreach($arr as $key => $val) {
       if($x[$j - 1] == $key)
           return $arr[$key];
   }
}

// Упорядоченный граф
$a = array('b', 'c', 'd');
$b = array('e', 'f', 'g');
$c = array('f', 'h', 'i');
$d = array('g', 'i', 'j');
$e = array('k', 'l');
$f = array('l', 'm');
$g = array('l', 'm');
$h = array('m');
$i = array('m');
$j = array('m');
$k = array('m');
$l = array('m');
$m = array();



// Первый путь
//$x = array('a', 'b', 'e', 'k', 'm');

// Массив соответствий
$arr = array(
   'a' => $a,
   'b' => $b,
   'c' => $c,
   'd' => $d,
   'e' => $e,
   'f' => $f,
   'g' => $g,
   'h' => $h,
   'i' => $i,
   'j' => $j,
   'k' => $k,
   'l' => $l,
   'm' => $m
);
//Первая точка
$first_point=array('a');
$last_point='m';
$add_new_point=$first_point[0];
$first_way[] = $first_point[0];
$i=0;
//Поиск первого маршута
while(1) {
	if(!isset(${$add_new_point}[0]))
	break;
$add_new_point=${$add_new_point}[0];
$first_way[] = $add_new_point;
if ($first_way[$i] == $last_point || $i >=  count($first_way)) {
	break;
}
$i++;
}
// Печатаем первый маршрут
print_r($first_way);
print "\n";


$x=$first_way;
$j = count($x) - 1;

while($j != 0) {
   // Ищем новое значение. Значение будет использовано в качестве имени массива.
   $ar = search_val($x, $j, $arr);
   $key = array_search($x[$j], $ar);
   //if (${$x[$j-1]}[$key+1] != '') {

   if (isset($ar[$key + 1])) {
       $x = array_slice($x, 0, $j);
       array_push($x, $ar[$key + 1]);
       //$z=$x[count($x)-1];
       //найдем все 0-ые индексы
        if (isset(search_new_val_for_push_int_x($x, $j, $arr)[0]))
       $z = search_new_val_for_push_int_x($x, $j, $arr)[0];

       while (1) {
           if ($x[count($x) - 1] == $last_point) {
				  if (isset(search_new_val_for_push_int_x($x, $j, $arr)[0]))
               array_push($x, $z);
               break;
           }
    if (isset(search_new_val_for_push_int_x($x, $j, $arr)[0]))
           array_push($x, $z);
                if (isset(search_new_val_for_push_int_x($x, $j, $arr)[0]))
           $z = search_new_val_for_push_int_x($x, $j, $arr)[0];

       }
       $j = count($x);
       print_r($x);
   }
   $j--;
}
?>
AnonymUser ★
() автор топика
Последнее исправление: AnonymUser (всего исправлений: 2)
Ответ на: комментарий от ratvier

Или если совсем от «переменных переменных» избавиться и находить первый путь в авто режиме, то так.

Первый вариант с нахождением первого пути закомментировал:

<?php
/*Поиск всех путей на ориентированном графе из точки а в точку f
на основе упорядочивания массивов и элементов массива по возрастанию
Легко доработать до поиска кратчайшего пути.*/

function search_new_val_for_push_int_x($x, $j, $arr) {
    foreach($arr as $key => $val) {
        if($x[count($x) - 1] == $key)
            return $arr[$key];
    }
}

function search_val($x, $j, $arr) {
    foreach($arr as $key => $val) {
        if($x[$j - 1] == $key)
            return $arr[$key];
    }
}

// Упорядоченный граф
$a = array('b', 'c', 'd');
$b = array('e', 'f', 'g');
$c = array('f', 'h', 'i');
$d = array('g', 'i', 'j');
$e = array('k', 'l');
$f = array('l', 'm');
$g = array('l', 'm');
$h = array('m');
$i = array('m');
$j = array('m');
$k = array('m');
$l = array('m');
$m = array();



// Первый путь
//$x = array('a', 'b', 'e', 'k', 'm');

// Массив соответствий
$arr = array(
    'a' => $a,
    'b' => $b,
    'c' => $c,
    'd' => $d,
    'e' => $e,
    'f' => $f,
    'g' => $g,
    'h' => $h,
    'i' => $i,
    'j' => $j,
    'k' => $k,
    'l' => $l,
    'm' => $m
);

//Доп.массив
$arr2 = array(
     $a,
     $b,
     $c,
     $d,
     $e,
     $f,
     $g,
     $h,
     $i,
     $j,
     $k,
     $l,
     $m
);
//Массив для нахождения первого пути
$arr3 = array(
    'a',
    'b',
    'c',
    'd',
    'e',
    'f',
    'g',
    'h',
    'i',
    'j',
    'k',
    'l',
    'm'
);
//Первый путь находим в первом столбце матрицы по 0 индексам, от a  до m
$first_way[]='a';
$last_point='m';
$x=$arr2[0];
$z=$x[0];
//Запишем вторую вершину
$first_way[]=$z;
//Найдем остальные
for($i = 0; $i < count($arr3); $i++){

	for($i; $arr3[$i] != $z; $i++);
	$x=$arr2[$i];
	if(isset($x[0])) {
	$z=$x[0];
	$first_way[]=$z[0];
	}
}


/*
//Первая точка
$first_point=array('a');
$last_point='m';
$add_new_point=$first_point[0];
$first_way[] = $first_point[0];
$i=0;
//Поиск первого маршута
while(1) {
	if(!isset(${$add_new_point}[0]))
	break;
$add_new_point=${$add_new_point}[0];
$first_way[] = $add_new_point;
if ($first_way[$i] == $last_point || $i >=  count($first_way)) {
	break;
}
$i++;
}
*/
// Печатаем первый маршрут
print_r($first_way);
print "\n";


$x=$first_way;
$j = count($x) - 1;

while($j != 0) {
    // Ищем новое значение. Значение будет использовано в качестве имени массива.
    $ar = search_val($x, $j, $arr);
    $key = array_search($x[$j], $ar);
    //if (${$x[$j-1]}[$key+1] != '') {

    if (isset($ar[$key + 1])) {
        $x = array_slice($x, 0, $j);
        array_push($x, $ar[$key + 1]);
        //$z=$x[count($x)-1];
        //найдем все 0-ые индексы
         if (isset(search_new_val_for_push_int_x($x, $j, $arr)[0]))
        $z = search_new_val_for_push_int_x($x, $j, $arr)[0];

        while (1) {
            if ($x[count($x) - 1] == $last_point) {
				  if (isset(search_new_val_for_push_int_x($x, $j, $arr)[0]))
                array_push($x, $z);
                break;
            }
     if (isset(search_new_val_for_push_int_x($x, $j, $arr)[0]))
            array_push($x, $z);
                 if (isset(search_new_val_for_push_int_x($x, $j, $arr)[0]))
            $z = search_new_val_for_push_int_x($x, $j, $arr)[0];

        }
        $j = count($x);
        print_r($x);
    }
    $j--;
}
?>
AnonymUser ★
() автор топика
Последнее исправление: AnonymUser (всего исправлений: 1)
Закрыто добавление комментариев для недавно зарегистрированных пользователей (со score < 50)
  1 2 →
← Репозитории truenetwork умерли?
Talks
Вычислительный кластер из 2000 смартфонов Google Pixel →