Помощ за алгоритъм, търсещ рекурсивни извиквания


4

Здравейте,

Имам да реша следния проблем: Имам списък от елементи. Един елемент може да извика някой или няколко от другите елементи. А те пък може да извикат същия елемент или други. Може да се получи рекурсивно извикване на елемент, т.е един елемент да извика втори елемент, втория да извика трети, а третия пак да извика първия. От мен се иска да намеря всички такива рекурсивни извиквания на всичките елементи от списъка и да запазя пътя на извикванията, т.е. през кои елементи е минал пътя за да стигне пак до началния елемент. Някакви идея как мога да реша този проблем?

Забравих да кажа, че обхождането продължава докато се намери елемент, който не вика никакъв друг елемент или елемент, който вика вече обходен елемент, т.е. получило се е рекурсивно извикване.
 

Поздрави,
Ахмед Караибрахимов


в Algo Academy (C++) от westsiderz (0 точки)


Отговори



1
От така зададения ти въпрос само не разбрах кога свършва "обхождането" на елементите. Иначе мисля, че най-лесно е да ги слагаш в опашка, а пътя да записваш в масив.
Алгоритамът е следния:
Взимаш първия елемент и го слагаш в опашката
Докато имаш елементи в опашката
Взимаш първия елемент от опашката и го слагаш в масива, който пази пътя
Проверяваш, кои елементи вика текущия и ги добавяш в опашката
Ако съм те разбрал правилно това би трябвало да ти свърши работа :)

от wnvko (3123 точки)


1
Извинявам се че съм забравил да кажа, че обхождането продължава докато се намери елемент, който не вика никакъв друг елемент или елемент, който вика вече обходен елемент, т.е. получило се е рекурсивно викане.
Не съм сигурен дали съм разбрал алгоритъма ти правилно - Да речем, че почна с 0. Слагам го в опашката. В опашката имам 0 а в масива нищо. Вземам първия елемент от опашката и го слагам в масива. Проверявам и виждам, че той вика 5, 6 и 7. Слагам ги и тях в опашката. Сега в масива имам 0 а в опашката - 5, 6 и 7. В опашката все още има елементи. Вземам първия елемент от опашката, тоест 5 и го слагам в масива. Виждам че той вика 2 и 3. Слагам ги и тях в опашката. В момента в масива имам 0 и 5 а в опашката 6, 7, 2 и 3. Ако продължа - в опашката все още имам елементи, затова вземам първия елемент - тоест 6 и го слагам в масива, виждам че той вика 0 и 1. Слагам ги и тях в опашката. В момента в масива, който трябва да пази пътя имам 0 - 5 - 6, което не е правилен път, трябва да бъде примерно 0 - 5 - 2. Бъркам ли нещо тук?

от westsiderz (0 точки)

0
Така задачата е малко по-ясна :) За да запазиш "пътя" ще трябва всеки елемент да помни кой го е извикал. Това може да го реализираш с проста структура от два еднакви елемента - елемент/родител. Ползваш пак същия алгоритъм, но леко коригиран, ще ползвам твоя пример: Слагаш в опашката 0 с родител null, т.е. 0/null. В опашката имаш 0/null масива е празен. Взимаш първия елемент от опашката и го слагаш в масива. Той вика 5, 6 и 7. Нова стъпка - проверяваш дали вика 0 - ако е така спираш цикъла, тук не е така.. Слагаш ги в опашката. Сега в масива имаш 0/null, а в опашката 5/0, 6/0 и 7/0. В опашката все още има елементи. Взимаш първия елемент от опашката, т.е. 5/0 и го слагаш в масива. Виждаш че той вика 2 и 3 - слагаш ги в опашката. Пак проверяваш дали вика 0 - тук не е така, продължаваш. В момента в масива има 0/null и 5/0, а в опашката 6/0, 7/0, 2/5 и 3/5. Взимаш първия елемент от опашката, т.е. 6/0 и го слагаш в масива. Виждаш, че той вика 0 и 1. Проверяваш дали вика 0 - да вика 0, следователно спираш цикъла. В масива имаш 0/null; 5/0 и 6/0. Взимаш последния елемент и му търсиш родителя в масива от зад на пред. Намираш му родителя и търсиш и неговия родител и така стигаш до елемента 0 и пътя ти е готов :)
п.п. сега видях, че горе има още една корекция - ако се търси докато се стигне до елемент, който вика вече извикан елемент или до елемент, който не вика друг елемент ще ти трябват две проверки - едната дали извикания елемент е вече викан - аз бих слагал всички елементи в един hashset и ще проверявам елемента дали е вътре, ако да цикъла спира; и втората проверка дали извикания елемент вика други - тази би трябвало да е лесна

от wnvko (3123 точки)


1
Здравей,
Запазваш си кой ти е първия посетен елемент в някаква променлива, а в 1 List си вкарваш според зависи точно какво ще рече това с пътя (дали да запазиш пътя като индексите на елементите или да запазиш самите елементи, то няма да има разлика като цяло). И с един while цикъл би трябвало да излезне това което ти трябва, докато текущия посетен елемент е различен от първия посетен, който си си запазил някъде, продължаваш да добавяш в List - а.
Ако няма право на повтаряне на елементи, може в един булев масив да отбелязваш кои елементи са посетени и ако уцелиш пак посетен елемент да свършва цикъла, ако има такова условие де, защото от това, което си написал не ми стана на 100 % ясно.
Поздрави. : )

от mbelev (2312 точки)


1
Благодаря за бързия отговор. Ще пробвам и ще пиша дали ми решава проблема

от westsiderz (0 точки)


1
Не съм сигурен, че разбирам много проблема, но примерно ако имаш граф с върхове 1,2,3 и избереш 1 за начален то имаш възможните извиквания(това без цикли в графа)
1 2 1
1 3 1
1 2 3 1
1 3 2 1
Или формулата е ако В е броя върхове => В+Vв-1
където V ти е вариацията без повторение от останалите два върха 2 и 3
Респективно ако имаш граф с върхове 1,2,3,4 ще имаш В+Vв-1+Vв-2
където Vв-1 е вариацията на сета {2,3,4} за три елемента и
Vв-2е вариацията на сета {2,3,4} за два елемента.



2

Това може да се сведе до задача за намиране на всички цикли в граф. За жалост не се сещам за някоя конкретна имплементация на алгоритъма, но има един Алгоритъм, който отчасти би ти свършил работа. Клик! Това е алгоритъм за намиране на силно свързани компоненти в граф или казано по-конкретно, за намиране на всички подможества елементи от списъка ти, които циклят помежду си. Мисля, че след като намериш тези силно свързани компоненти, ще ти е по-лесно да намериш всички цикли в списъка


от TaoTao (599 точки)


1

 Вчера решавах подобна задача, намиране на най-кратък път в лабиринт. Разликата е, че си пазех на кое поле съм стъпвал, за да не стъпя повторно. Но мога да ти предложа следния вариант:

 Вместо опашка, можеш да използваш списък. Създаваш един клас, за елементите. В този клас всеки елементи си има някакви координати(или както там го достъпваш и РОДИТЕЛ, отново тип елемент).

 Създаваш инстанция на класа за първия елемент, на който ще стъпиш.

Подаваш на основния ти метод(пр. TraverseElements) първия елемент. Добавяш го към списъка. Пускаш един цикъл, който да върти докато в списъка има елементи. В началото на цикъла взимаш елемента от списъка на индекс 0. Махаш го от списъка и проверяваш, дали обхождането ти не трябва да спре. Ако трябва да спре, тръгваш по елементите наобратно за да намериш пътя на извикванията(по-късно ще кажа как).

 В тялото на цикъла, ако условието за крайн на обхожданията не е изпълнено, почваш да проверяваш всички съседи на текущия елемент.

Ако на съответния съсед не е стъпвано, създаваш от него нов обект и го добавяш в списъка. Правиш родителя на новосъздадения обект, да е текущия. После цикъла се завърта отново и вземаш първия обект от списъка. 

 Така последователно ще обходиш най-близките елементи до началния, после по-далечните и тн. И когато стигнеш до момента, в който възможностите са изчерпани чрез родителите ще можеш да проследиш елементите на обратно.

 Незнам колко добре го обясних, ето кода с задачката за лабиринта:

http://pastebin.com/AdtvWLx4

Би трябвало твоя проблем да може да се реши по сходен метод, някои изменения.


от ivan.mihov1 (4988 точки)


1
Благодаря на всички за помощта. Изпробвах идеята на wnvko като я нагласих според нуждите си и изглежда, че тя ще работи а и изглежда по-лесна за имплементиране.

от westsiderz (0 точки)