1 Тема от Karagiozis (изменено: Karagiozis, 2018-05-14 04:15:11)

  • Karagiozis
  • Участник
  • Неактивен

Тема: AHK: Алгоритм поиска пути. Убрать gui из готового кода.

Доброй ночи.
Нашел алгоритм поиска пути, но не могу разобраться как убрать этот гуи.
Хотел бы без gui и получить результат пути в виде массива []
https://rosettacode.org/wiki/Dijkstra%2 … AutoHotkey
P.S. в data надо заносить данные через таб, а не пробел.

2 Ответ от Karagiozis (изменено: Karagiozis, 2018-05-14 22:37:49)

  • Karagiozis
  • Участник
  • Неактивен

Re: AHK: Алгоритм поиска пути. Убрать gui из готового кода.

Разобрался.
Но возникла непонятная проблема.
Если в data вносить дистанцию через переменую, то почему-то путь показывает ACE, хотя ближе ABE.


global d := {"A": [0,0], "B": [1,1], "C": [-2,2], "E": [2,3]}
AB := round(points_dist("A","B"), 2)
AC := round(points_dist("A","C"), 2)
BE := round(points_dist("B","E"), 2)
CE := round(points_dist("C","E"), 2)
msgbox, AB: %AB%`nAC: %AC%`nBE: %BE%`nCE: %CE%
data =
(
A	B	'%AB%'
A	C	'%AC%'
B	E	'%BE%'
C	E	'%CE%'
)
nodes:=[], Distance := []
for each, line in StrSplit(data, "`n" , "`r")
{
    field := StrSplit(line,"`t"), nodes[field.1] := 1, nodes[field.2] := 1
    , Distance[field.1,field.2] := field.3  , Distance[field.2,field.1] := field.3
}
 
for node, v in nodes
    nodeList .= (nodeList?"|":"") node (A_Index=1?"|":"")

Gosub, Routing
Gosub, result
return

Routing:
arr := []
From := "A"
To := "E"
arr.Push(To)
res := Dijkstra(data, From)
Loop % objCount(nodes)
{
    for xTo , xFrom in res.2
	{
		if (xTo = To)
        {
			arr.insertAt(1, xFrom)
			To := xFrom
            if (xFrom = From)
				return
        }
	}
}
return

result:
for k, v in arr
{
	msgbox % v
}
return

Dijkstra(data, start){
	nodes := [], dist := [], Distance := [], dist := [], prev := [], Q := [], min := "x"
	for each, line in StrSplit(data, "`n" , "`r")
	{
		field := StrSplit(line,"`t"), nodes[field.1] := 1, nodes[field.2] := 1
		, Distance[field.1,field.2] := field.3, Distance[field.2,field.1] := field.3
	}
	dist[start] := 0, prev[start] := ""
 
	for node in nodes {
		if (node <> start)
			dist[node] := "x"
			, prev[node] := ""
		Q[node] := 1
	}
 
	while % ObjCount(Q) {
		u := MinDist(Q, dist).2
		for node, val in Q
			if (node = u) {
				q.Remove(node)
				break
			}
 
		for v, length in Distance[u] {
			alt := dist[u] + length
			if (alt < dist[v])
				dist[v] := alt	
				, prev[v] := u
		}
	}
	return [dist, prev]
}
;-----------------------------------------------
MinDist(Q, dist){
	for node , val in Q
		if A_Index=1
			min := dist[node], minNode := node
		else
			min := min < dist[node] ? min : dist[node]	, minNode := min < dist[node] ? minNode : node		
	return [min,minNode]
}
ObjCount(Obj){
	for key, val in Obj
		count := A_Index
	return count
}

getDist(pos1,pos2) {
	if(!pos1 || !pos2)
		return 0
    return Sqrt((pos1[1]-pos2[1])*(pos1[1]-pos2[1])+(pos1[2]-pos2[2])*(pos1[2]-pos2[2]))
}

points_dist(p1, p2)
{
	return getDist([d[p1][1],d[p1][2]],[d[p2][1],d[p2][2]])
}

Если дистанцию записать в ручную так, то нормально выводить результат ABE


data =
(
A	B	1.41
A	C	2.83
B	E	2.24
C	E	4.12
)
nodes:=[], Distance := []
for each, line in StrSplit(data, "`n" , "`r")
{
    field := StrSplit(line,"`t"), nodes[field.1] := 1, nodes[field.2] := 1
    , Distance[field.1,field.2] := field.3  , Distance[field.2,field.1] := field.3
}
 
for node, v in nodes
    nodeList .= (nodeList?"|":"") node (A_Index=1?"|":"")

Gosub, Routing
Gosub, result
return

Routing:
arr := []
From := "A"
To := "E"
arr.Push(To)
res := Dijkstra(data, From)
Loop % objCount(nodes)
{
    for xTo , xFrom in res.2
	{
		if (xTo = To)
        {
			arr.insertAt(1, xFrom)
			To := xFrom
            if (xFrom = From)
				return
        }
	}
}
return

result:
for k, v in arr
{
	msgbox % v
}
return

Dijkstra(data, start){
	nodes := [], dist := [], Distance := [], dist := [], prev := [], Q := [], min := "x"
	for each, line in StrSplit(data, "`n" , "`r")
	{
		field := StrSplit(line,"`t"), nodes[field.1] := 1, nodes[field.2] := 1
		, Distance[field.1,field.2] := field.3, Distance[field.2,field.1] := field.3
	}
	dist[start] := 0, prev[start] := ""
 
	for node in nodes {
		if (node <> start)
			dist[node] := "x"
			, prev[node] := ""
		Q[node] := 1
	}
 
	while % ObjCount(Q) {
		u := MinDist(Q, dist).2
		for node, val in Q
			if (node = u) {
				q.Remove(node)
				break
			}
 
		for v, length in Distance[u] {
			alt := dist[u] + length
			if (alt < dist[v])
				dist[v] := alt	
				, prev[v] := u
		}
	}
	return [dist, prev]
}
;-----------------------------------------------
MinDist(Q, dist){
	for node , val in Q
		if A_Index=1
			min := dist[node], minNode := node
		else
			min := min < dist[node] ? min : dist[node]	, minNode := min < dist[node] ? minNode : node		
	return [min,minNode]
}
ObjCount(Obj){
	for key, val in Obj
		count := A_Index
	return count
}

getDist(pos1,pos2) {
	if(!pos1 || !pos2)
		return 0
    return Sqrt((pos1[1]-pos2[1])*(pos1[1]-pos2[1])+(pos1[2]-pos2[2])*(pos1[2]-pos2[2]))
}

points_dist(p1, p2)
{
	return getDist([d[p1][1],d[p1][2]],[d[p2][1],d[p2][2]])
}

Помогите пожалуйста.

3 Ответ от serzh82saratov

  • serzh82saratov
  • Разработчик
  • Неактивен

Re: AHK: Алгоритм поиска пути. Убрать gui из готового кода.

'%AB%'

Надо убрать кавычки.

По вопросам возмездной помощи пишите на E-Mail: serzh82saratov@mail.ru Telegram: https://t.me/sergiol982
Win10x64 AhkSpy, Hotkey, ClockGui

4 Ответ от Karagiozis

  • Karagiozis
  • Участник
  • Неактивен

Re: AHK: Алгоритм поиска пути. Убрать gui из готового кода.

serzh82saratov пишет:
'%AB%'

Надо убрать кавычки.

Спасибо огромное!!!