Что нового

[Все] Полный путь в графе

Yashied

Модератор
Команда форума
Глобальный модератор
Сообщения
5,379
Репутация
2,724
Есть следующий граф (дерево):

post_img_087.png

Из каждого узла может выходить максимум две ветки. Т.е. максимальное количество узлов (N) на каждом следующем уровне (i) удваивается по сравнению с предыдущим:

Код:
Ni = 2 ^ (i - 1)

Задается такой граф в виде последовательности строк, определяющих каждый уровень дерева, например:

Уровень 1: A
Уровень 2: B, C
Уровень 3: D, E, F, G
Уровень 4: H, I, J, K, L, M, N, O

и т.д.

A, B, C, ... - это просто названия узлов (могут быть произвольными).

Для полного описания графа используется массив:

$aGraph[15] = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O']

Длина массива всегда равна максимально возможному количеству узлов в графе, в данном случае:

Код:
1 + 2 + 4 + 8 = 15

Если какие-нибудь узлы отсутствуют, то используются пустые строки, например:

Код:
$aGraph[15] = ['A', 'B', 'C', 'D', 'E', 'F', 'G', '', 'H', '', '', 'I', 'J', 'K', '']


post_img_088.png

Самый верхний узел A (1-ый уровень) всегда должен присутствовать.

Задание

Написать алгоритм (функцию) для нахождения полного пути от вершины A до требуемого узла в таком дереве. Например, полный путь до узла J в предыдущем графе будет выглядеть так:

post_img_089.png

В качестве исходных данных есть только сам граф ($aGraph) и название узла в нем, например "J", путь до которого необходимо определить. Результат должен представлять из себя строку вида (для данного примера):

Код:
A-C-F-J

Примечание

Исходный граф может иметь произвольное количество уровней, начиная с 1, и произвольное количество отсутствующих вершин, но всегда имеет описанную выше древовидную структуру.
 

C2H5OH

AutoIT Гуру
Сообщения
1,473
Репутация
333
Код тут выкладывать или в личку?
 

C2H5OH

AutoIT Гуру
Сообщения
1,473
Репутация
333
Хотя, вообще-то рекурсию очень уважаю...

Код:
#include <Array.au3>

Dim $aGraph[15] = ['A', 'B', 'C', 'D', 'E', 'F', 'G', '', 'H', '', '', 'I', 'J', 'K', '']
$Uzel = "J"

$N = UBound($aGraph)
Dim $Derevo[$N]

For $i=1 to $N -1
	$Derevo[$i] = Floor( ($i-1) / 2 )
Next

$iIndex = _ArraySearch($aGraph, $Uzel)
If @error Then
    MsgBox(0, "Узел не найден", 'Узел "' & $Uzel & '" в дереве отсутствует.')
	Exit
EndIf

$sRes = ""

While $iIndex > 0
	$sRes = "-" & $aGraph[$iIndex] & $sRes
	$iIndex = $Derevo[$iIndex]
WEnd

$sRes = $aGraph[0] & $sRes

MsgBox(0, "Ответ", 'Путь : "' & $sRes & '"')
 

kaster

Мой Аватар, он лучший самый
Команда форума
Глобальный модератор
Сообщения
4,020
Репутация
626
вот для этой задачи ассоциативные массивы не помешали бы. ну по крайней мере для того решения, которое я вижу
 
Автор
Yashied

Yashied

Модератор
Команда форума
Глобальный модератор
Сообщения
5,379
Репутация
2,724
Ладно, раз больше никого нет, то вот мой вариант. Немного сложнее, но зато с рекурсией.

Код:
;~         A
;~       /   \
;~     B       C
;~   /   \       \
;~ D       E       F
;~       /       /   \
;~     G       H       I
;~           /   \
;~         J       K

Dim $aGraph[31] = ['A', 'B', 'C', 'D', 'E', '', 'F', '', '', 'G', '', '', '', 'H', 'I', '', '', '', '', '', '', '', '', '', '', '', '', 'J', 'K', '', '']

Func _Path(ByRef $aGraph, $sItem, $iIndex = 0, $sPath = '')
	If Not $aGraph[$iIndex] Then
		Return ''
	EndIf
	$sPath = StringRegExpReplace($sPath & '-' & $aGraph[$iIndex], '\A-+', '')
	If $aGraph[$iIndex] = $sItem Then
		Return $sPath
	EndIf
	$iIndex = 2 ^ Ceiling(Log($iIndex + 2) / Log(2)) + 2 * ($iIndex - 2 ^ (Ceiling(Log($iIndex + 2) / Log(2)) - 1) + 1) - 1
	If $iIndex < UBound($aGraph) - 1 Then
		For $i = 0 To 1
			Local $Path = _Path($aGraph, $sItem, $iIndex + $i, $sPath)
			If $Path Then
				Return $Path
			EndIf
		Next
	EndIf
	Return ''
EndFunc   ;==>_Path

ConsoleWrite(_Path($aGraph, 'K') & @CR)
 

C2H5OH

AutoIT Гуру
Сообщения
1,473
Репутация
333
Не понимаю...
Код:
$iIndex = 2 ^ Ceiling(Log($iIndex + 2) / Log(2)) + 2 * ($iIndex - 2 ^ (Ceiling(Log($iIndex + 2) / Log(2)) - 1) + 1) - 1

:shok:

Почему не взять просто
Код:
$iIndex = 2 * $iIndex + 1

???
 
Верх