Простая рекурсивная функция для определения транзитивности двух элементов

Question

новичок здесь. Еще новее рекурсии. Я пишу функцию для своей программы на C++, и, как вы сможете сказать, я немного незнаю, когда речь идет о рекурсивных алгоритмах. Я был бы очень признателен, если бы кто-то мог исправить мою функцию, чтобы я мог заставить ее работать и, возможно, лучше подумал о том, как обращаться с рекурсией позже.

Моя функция принимает двумерный квадратный массив булевых чисел и целое число i и целочисленное значение array_size в качестве параметров. Функция возвращает логическое значение.

Массив - матрица смежности, которую я использую для представления набора условных обозначений. Например, если значение в [0] [3] истинно, то 0 -> 3 (если 0, то 3). Если [3] [7] истинно, то 3 -> 7 (если 3, то 7). По транзитивному свойству 0 -> 7 (если 0, то 7).

Целое число i является частным элементом в множестве условных обозначений. Функция вернет true, если этот элемент транзитивно связан с последним элементом массива. Последним элементом в массиве является целое число (array_size - 1),

Целое число array_size - размер каждого измерения квадратного массива. Если array_size равно 20, массив равен 20x20.

Идея этой функции состоит в том, чтобы определить, существует ли какой-либо логический «путь» от первого целочисленного элемента к последнему целочисленному элементу транзитивным свойством. Когда путь существует, функция возвращает true, иначе возвращается false. Рекурсивный вызов должен позволять ему перемещаться по всем возможным путям, возвращая true, как только он наконец достигнет последнего элемента, и false, если все пути не пройдут.

Например, если i = 0 и array_size = 10, тогда функция вернет, действительно ли 0 -> 9 действует в соответствии с условиями, предоставляемыми матрицей и транзитивным свойством.

Это мой код до сих пор:

bool checkTransitivity(bool **relations, int i, int array_size){ 
bool isTransitive = false; 

if (i == array_size - 1) 
{ 
    isTransitive = true; 
} 
else 
{ 
    for (int j = i; j < array_size; j++){ 
     if (relations[i][j]) 
     { 
      isTransitive = checkTransitivity(relations, j, array_size); 
     } 
    } 
} 

return isTransitive; 

В настоящее время, функция возвращает истину для всех входных данных.

Любая помощь вообще оценивается. Заранее спасибо!

Answer 1

EDIT: Эта первая часть не нужна из-за вашего оператора if-else. Перейдите к END OF EDIT.

Давайте начнем с того, что базовый случай в рекурсивной функции:

if (i == array_size - 1) 
{ 
    isTransitive = true; 
} 

Ну у вас есть базовый случай, но ничего не возвращается. Вы просто устанавливаете флаг в true. Что вы хотите сделать:

if (i == array_size - 1) { 
    return true; 
} 

Теперь функция пробивается вверх по рекурсивному стеку, чтобы вернуть true. КОНЕЦ РЕДАКТИРОВАНИЯ.

Но нам еще нужно исправить рекурсивный случай:

else { 
    for (int j = i; j < array_size; j++) { 
     if (relations[i][j]) { 
      isTransitive = isTransitive || checkTransitivity(relations, j, array_size); 
     } 
    } 
} 

return isTransitive; 

|| означает бинарный OR. Итак, у вас есть логика права. Вы хотите проверить каждый возможный путь, чтобы увидеть, может ли он туда попасть, но, установив isTransitive к результату каждой проверки, isTransitive будет установлен только на последний вызов. Выполняя isTransitive = isTransitive || recursive call, isTransitive будет истинным, если один из вызовов приводит к истинному значению.

Последнее, что я хочу сказать, это предостережение: если relations[i][j] == true и relations[j][i] == true, ваш код по-прежнему будет в бесконечном цикле. Вы должны найти способ устранить потенциальный откат. Один из способов сделать это - создать еще один массив, в котором хранятся те пути, которые вы уже проверили, чтобы вы не бесконечно зацикливались.

Более подробную информацию можно найти здесь: Depth First Search

Answer 2

I думаю все, что вам нужно, это условие, чтобы прекратить продолжение цикла, когда вы сталкиваетесь с непереходным элементом. См. Ниже (не проверено)

bool checkTransitivity(bool **relations, int i, int array_size){ 
bool isTransitive = false; 

if (i == array_size - 1) 
{ 
    isTransitive = true; 
} 
else 
{ 
    for (int j = i; j < array_size; j++){ 
     isTransitive = relations[i][j] && checkTransitivity(relations, j, array_size); 
     if (!isTransitive) 
      break; 
    } 
} 

return isTransitive; 
}